devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（13）：平衡二叉树（AVL）实现_平衡二叉树高度与结点

作者：Monodyee | 2024-04-26 17:02:07

赞

踩

平衡二叉树高度与结点

一、平衡二叉树定义

平衡二叉树定义，对于任意一个节点，左子树和右子树的高度差不能超过1.

特性：平衡二叉树的高度和节点数量之间的关系是O(logn)。

二、标注

1.平衡因子：左右两个子树的高度差。如果平衡因子绝对值>=2，则不是平衡二叉树,如下图

三、平衡基本操作

1.右旋转

（1）原始树
 
（2）右旋转：旋转为
 
（3）证明右旋转后，满足平衡二叉树和二分搜索树（节点，大于左孩子，小于右孩子）的性质。

2.左旋转

（1）原始树
 
（2）左旋转

3.LR


（1）原始树
 
（2）先将x左旋转，转换为LL
 
（3）再进行右旋转


4.RL

（1）原始树
 
（2）先堆X节点进行右旋转，为RR
 
（3）再对y进行左旋转

四、AVL实现代码

  1. package com.DataStructures._12AVL;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. /**
  6.  * Created by Administrator on 2019/11/23.
  7.  */
  8. public class AVLTree <K extends Comparable<K>, V> {
  9.  
  10.     private class Node{
  11.         public K key;
  12.         public V value;
  13.         public Node left, right;
  14.         public int height; //每个节点的高度值
  15.  
  16.         public Node(K key, V value){
  17.             this.key = key;
  18.             this.value = value;
  19.             left = null;
  20.             right = null;
  21.  
  22.             height=1;
  23.         }
  24.     }
  25.  
  26.     private Node root;
  27.     private int size;
  28.  
  29.     public AVLTree(){
  30.         root = null;
  31.         size = 0;
  32.     }
  33.  
  34.     public int getSize(){
  35.         return size;
  36.     }
  37.  
  38.     public boolean isEmpty(){
  39.         return size == 0;
  40.     }
  41.  
  42.     //=======================辅助函数 start=================================
  43.     //返回当前节点node的高度
  44.     private int getHeight(Node node){
  45.         if (node==null){
  46.             return 0;
  47.         }
  48.         return node.height;
  49.     }
  50.  
  51.     //计算每个节点的平衡因子
  52.     //平衡因子>=2或则<=-2时，则有问题
  53.     private int getBalanceFactor(Node node){
  54.         if(node==null){
  55.             return 0;
  56.         }
  57.         return  getHeight(node.left)-getHeight(node.right);
  58.     }
  59.  
  60.  
  61.     //判断当前树是否时二分搜索树：通过中序遍历，由小到打
  62.     //二分搜索树：所有节点满足，左子节点小于根节点，右子节点大于根节点
  63.     public boolean isBST(){
  64.         ArrayList<K> keys=new ArrayList<K>();
  65.         inOrder(root,keys);
  66.  
  67.         for (int i = 1; i < keys.size(); i++) {
  68.             if(keys.get(i-1).compareTo(keys.get(i))>0){
  69.                 return false;
  70.             }
  71.         }
  72.         return true;
  73.     }
  74.  
  75.     private void inOrder(Node node,ArrayList<K> keys){
  76.         if (node==null){
  77.             return;
  78.         }
  79.  
  80.         inOrder(node.left,keys);
  81.         keys.add(node.key);
  82.         inOrder(node.right,keys );
  83.     }
  84.  
  85.     //判断该二叉树，是否是一个平衡二叉树
  86.     public boolean isBalanced(){
  87.         return isBalanced(root);
  88.     }
  89.  
  90.     //判断以Node为根的二叉树是否是一个平衡二叉树，使用递归算法
  91.     public boolean isBalanced(Node node){
  92.  
  93.         if(node==null)
  94.             return true;
  95.  
  96.         int balanceFactor=getBalanceFactor(node);
  97.         if(Math.abs(balanceFactor)>1){
  98.             return false;
  99.         }
  100.         return isBalanced(node.left) && isBalanced(node.right);
  101.     }
  102.  
  103.     //=======================辅助函数 end=================================
  104.  
  105.     // 向二分搜索树中添加新的元素(key, value)
  106.     public void add(K key, V value){
  107.         root = add(root, key, value);
  108.     }
  109.  
  110.     // 向以node为根的二分搜索树中插入元素(key, value)，递归算法
  111.     // 返回插入新节点后二分搜索树的根
  112.     private Node add(Node node, K key, V value){
  113.  
  114.         if(node == null){
  115.             size ++;
  116.             return new Node(key, value);
  117.         }
  118.  
  119.         if(key.compareTo(node.key) < 0)
  120.             node.left = add(node.left, key, value);
  121.         else if(key.compareTo(node.key) > 0)
  122.             node.right = add(node.right, key, value);
  123.         else // key.compareTo(node.key) == 0
  124.             node.value = value;
  125.  
  126.         //1.更新height
  127.         node.height=1+Math.max(getHeight(node.left),getHeight(node.right));
  128.  
  129.         //2.计算平衡因子
  130.         int balanceFactor=getBalanceFactor(node);
  131. //        if(Math.abs(balanceFactor)>1){
  132. //            System.out.println("unbalanced : "+balanceFactor);
  133. //        }
  134.  
  135.         //3.如果平衡因子大于1，则维护平衡性
  136.         //情况1【LL】：左侧大于右侧，而且左子树的平衡因子大于等于0，进行右旋转
  137.         if(balanceFactor>1&&getBalanceFactor(node.left)>=0){
  138.             return rightRotate(node);
  139.         }
  140.         //情况2【RR】：右侧大于左侧，而且右子树平衡因子小于等于0，即向右倾斜，进行左旋转
  141.         if (balanceFactor<-1&&getBalanceFactor(node.right)<=0){
  142.             return leftRotate(node);
  143.         }
  144.         //情况3【LR】
  145.         if(balanceFactor>1&&getBalanceFactor(node.left)<0){
  146.             node.left=leftRotate(node.left);
  147.             return rightRotate(node);
  148.         }
  149.         //情况4【RL】
  150.         if (balanceFactor<-1&&getBalanceFactor(node.right)>0){
  151.             node.right=rightRotate(node.right);
  152.             return leftRotate(node);
  153.         }
  154.         return node;
  155.     }
  156.  
  157.     //右旋转
  158.     // 对节点y进行向右旋转操作，返回旋转后新的根节点x
  159.     //        y                              x
  160.     //       / \                           /   \
  161.     //      x   T4     向右旋转 (y)        z     y
  162.     //     / \       - - - - - - - ->    / \   / \
  163.     //    z   T3                       T1  T2 T3 T4
  164.     //   / \
  165.     // T1   T2
  166.     private Node rightRotate(Node y){
  167.  
  168.         Node x=y.left;
  169.  
  170.         Node T3=x.right;
  171.         //向右旋转
  172.         x.right=y;
  173.         y.left=T3;
  174.  
  175.         //更新x，y的height值
  176.         y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
  177.         x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;
  178.  
  179.         return x;
  180.     }
  181.  
  182.     //左旋转
  183.     // 对节点y进行向左旋转操作，返回旋转后新的根节点x
  184.     //    y                             x
  185.     //  /  \                          /   \
  186.     // T1   x      向左旋转 (y)       y     z
  187.     //     / \   - - - - - - - ->   / \   / \
  188.     //   T2  z                     T1 T2 T3 T4
  189.     //      / \
  190.     //     T3 T4
  191.     private Node leftRotate(Node y){
  192.  
  193.         Node x=y.right;
  194.         Node T2=x.left;
  195.  
  196.         //向左旋转
  197.         x.left=y;
  198.         y.right=T2;
  199.  
  200.         //更新height
  201.         y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
  202.         x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;
  203.  
  204.         return x;
  205.     }
  206.  
  207.     // 返回以node为根节点的二分搜索树中，key所在的节点
  208.     private Node getNode(Node node, K key){
  209.  
  210.         if(node == null)
  211.             return null;
  212.  
  213.         if(key.equals(node.key))
  214.             return node;
  215.         else if(key.compareTo(node.key) < 0)
  216.             return getNode(node.left, key);
  217.         else // if(key.compareTo(node.key) > 0)
  218.             return getNode(node.right, key);
  219.     }
  220.  
  221.     public boolean contains(K key){
  222.         return getNode(root, key) != null;
  223.     }
  224.  
  225.     public V get(K key){
  226.  
  227.         Node node = getNode(root, key);
  228.         return node == null ? null : node.value;
  229.     }
  230.  
  231.     public void set(K key, V newValue){
  232.         Node node = getNode(root, key);
  233.         if(node == null)
  234.             throw new IllegalArgumentException(key + " doesn't exist!");
  235.  
  236.         node.value = newValue;
  237.     }
  238.  
  239.     // 返回以node为根的二分搜索树的最小值所在的节点
  240.     private Node minimum(Node node){
  241.         if(node.left == null)
  242.             return node;
  243.         return minimum(node.left);
  244.     }
  245.  
  246.     // 删除掉以node为根的二分搜索树中的最小节点
  247.     // 返回删除节点后新的二分搜索树的根
  248.     private Node removeMin(Node node){
  249.  
  250.         if(node.left == null){
  251.             Node rightNode = node.right;
  252.             node.right = null;
  253.             size --;
  254.             return rightNode;
  255.         }
  256.  
  257.         node.left = removeMin(node.left);
  258.         return node;
  259.     }
  260.  
  261.     // 从二分搜索树中删除键为key的节点
  262.     public V remove(K key){
  263.  
  264.         Node node = getNode(root, key);
  265.         if(node != null){
  266.             root = remove(root, key);
  267.             return node.value;
  268.         }
  269.         return null;
  270.     }
  271.  
  272.     private Node remove(Node node, K key){
  273.  
  274.         if( node == null )
  275.             return null;
  276.  
  277.         //最终要返回的node
  278.         Node retNode;
  279.  
  280.         if( key.compareTo(node.key) < 0 ){
  281.             node.left = remove(node.left , key);
  282. //            return node;
  283.             retNode=node;
  284.         }
  285.         else if(key.compareTo(node.key) > 0 ){
  286.             node.right = remove(node.right, key);
  287. //            return node;
  288.             retNode=node;
  289.         }
  290.         else{   // key.compareTo(node.key) == 0
  291.  
  292.  
  293.             if(node.left == null){   // 待删除节点左子树为空的情况
  294.                 Node rightNode = node.right;
  295.                 node.right = null;
  296.                 size --;
  297. //                return rightNode;
  298.                 retNode=rightNode;
  299.             }else  if(node.right == null){  // 待删除节点右子树为空的情况
  300.                 Node leftNode = node.left;
  301.                 node.left = null;
  302.                 size --;
  303. //                return leftNode;
  304.                 retNode=leftNode;
  305.             }else {     // 待删除节点左右子树均不为空的情况
  306.  
  307.                 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
  308.                 // 用这个节点顶替待删除节点的位置
  309.                 Node successor = minimum(node.right);
  310. //            successor.right = removeMin(node.right);  //可能会引起删除值
  311.                 successor.right=remove(node.right,successor.key);//服用remove的调整方法
  312.                 successor.left = node.left;
  313.                 node.left = node.right = null;
  314. //            return successor;
  315.                 retNode=successor;
  316.             }
  317.  
  318.         }
  319.  
  320. //        当retNode为空的时候，则直接返回
  321.         if (retNode==null){
  322.             return null;
  323.         }
  324.  
  325.         //1.更新height
  326.         retNode.height=1+Math.max(getHeight(retNode.left),getHeight(retNode.right));
  327.  
  328.         //2.计算平衡因子
  329.         int balanceFactor=getBalanceFactor(retNode);
  330. //        if(Math.abs(balanceFactor)>1){
  331. //            System.out.println("unbalanced : "+balanceFactor);
  332. //        }
  333.  
  334.         //3.如果平衡因子大于1，则维护平衡性
  335.         //情况1【LL】：左侧大于右侧，而且左子树的平衡因子大于等于0，进行右旋转
  336.         if(balanceFactor>1&&getBalanceFactor(retNode.left)>=0){
  337.             return rightRotate(retNode);
  338.         }
  339.         //情况2【RR】：右侧大于左侧，而且右子树平衡因子小于等于0，即向右倾斜，进行左旋转
  340.         if (balanceFactor<-1&&getBalanceFactor(retNode.right)<=0){
  341.             return leftRotate(retNode);
  342.         }
  343.         //情况3【LR】
  344.         if(balanceFactor>1&&getBalanceFactor(retNode.left)<0){
  345.             retNode.left=leftRotate(retNode.left);
  346.             return rightRotate(retNode);
  347.         }
  348.         //情况4【RL】
  349.         if (balanceFactor<-1&&getBalanceFactor(retNode.right)>0){
  350.             node.right=rightRotate(retNode.right);
  351.             return leftRotate(retNode);
  352.         }
  353.         return retNode;
  354.  
  355.     }
  356.  
  357.     public static void main(String[] args){
  358.  
  359.         System.out.println("Pride and Prejudice");
  360.  
  361.         ArrayList<String> words = new ArrayList<>();
  362.         if(FileOperation.readFile("src/resources/pride-and-prejudice.txt", words)) {
  363.             System.out.println("Total words: " + words.size());
  364.  
  365.             AVLTree<String, Integer> map = new AVLTree<>();
  366.             for (String word : words) {
  367.                 if (map.contains(word))
  368.                     map.set(word, map.get(word) + 1);
  369.                 else
  370.                     map.add(word, 1);
  371.             }
  372.  
  373.             System.out.println("Total different words: " + map.getSize());
  374.             System.out.println("Frequency of PRIDE: " + map.get("pride"));
  375.             System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
  376.  
  377.             System.out.println("is BST : "+map.isBST());
  378.             System.out.println("is Balance : "+ map.isBalanced());
  379.  
  380.             for (String word : words) {
  381.                 map.remove(word);
  382.                 if(!map.isBST()||!map.isBalanced()){
  383. //                    System.out.println("");
  384.                     throw new RuntimeException("Error: 非BST，或者非平衡树");
  385.                 }
  386.             }
  387.         }
  388.  
  389.         System.out.println();
  390.     }
  391. }

五、基于AVL的集合和映射

1.集合

（1）接口

  1. package com.DataStructures._12AVL;
  2.  
  3. /**
  4.  * Created by Administrator on 2018/12/17.
  5.  */
  6. public interface Set<E> {
  7.     void add(E e);
  8.     void remove(E e);
  9.     boolean contains(E e);
  10.     int getSize();
  11.     boolean isEmpty();
  12. }

（2）实现

  1. package com.DataStructures._12AVL;
  2.  
  3. /**
  4.  * Created by Administrator on 2019/11/24.
  5.  */
  6. public class AVLSet <E extends Comparable<E>> implements Set<E> {
  8.     private AVLTree<E,Object> avl;
  9.  
  10.     public AVLSet(){
  11.         avl=new AVLTree<E, Object>();
  12.     }
  13.  
  14.     @Override
  15.     public void add(E e) {
  16.         avl.add(e,null);
  17.     }
  18.  
  19.     @Override
  20.     public void remove(E e) {
  21.         avl.remove(e);
  22.  
  23.     }
  24.  
  25.     @Override
  26.     public boolean contains(E e) {
  27. //        return false;
  28.         return avl.contains(e);
  29.     }
  30.  
  31.     @Override
  32.     public int getSize() {
  33. //        return 0;
  34.         return avl.getSize();
  35.     }
  36.  
  37.     @Override
  38.     public boolean isEmpty() {
  39. //        return false;
  40.         return avl.isEmpty();
  41.     }
  42.  
  43.  
  44. }

2.映射map

（1）接口

  1. package com.DataStructures._12AVL;
  2.  
  3. /**
  4.  * Created by Administrator on 2018/12/17.
  5.  */
  6. public interface Map<K,V> {
  7.     void add(K key, V value);
  8.     V remove(K key);
  9.     boolean contains(K key);
  10.     V get(K key);
  11.     void set(K key, V value);
  12.     int getSize();
  13.     boolean isEmpty();
  14. }

（2）实现

  1. package com.DataStructures._12AVL;
  2.  
  3. /**
  4.  * Created by Administrator on 2019/11/24.
  5.  * AVLMap：基于AVL实现的Map
  6.  */
  7. public class AVLMap <K extends Comparable<K>,V> implements Map<K,V> {
  8.     private AVLTree<K,V> avl;
  9.  
  10.     public AVLMap(){
  11.         avl=new AVLTree<>();
  12.     }
  13.  
  14.     @Override
  15.     public int getSize(){
  16.         return avl.getSize();
  17.     }
  18.  
  19.     @Override
  20.     public boolean isEmpty(){
  21.         return avl.isEmpty();
  22.     }
  23.  
  24.     @Override
  25.     public void add(K key, V value){
  26.         avl.add(key, value);
  27.     }
  28.  
  29.     @Override
  30.     public boolean contains(K key){
  31.         return avl.contains(key);
  32.     }
  33.  
  34.     @Override
  35.     public V get(K key){
  36.         return avl.get(key);
  37.     }
  38.  
  39.     @Override
  40.     public void set(K key, V newValue){
  41.         avl.set(key, newValue);
  42.     }
  43.  
  44.     @Override
  45.     public V remove(K key){
  46.         return avl.remove(key);
  47.     }
  48. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/492130
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号