平衡二叉树（AVL树）

拼搏现实的明天。 2024-04-18 21:24 7阅读 0赞

### 一、基本介绍 ###

1）平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以**保证查询效率较高。**  
　　2）具有以下特点：**它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。**

3）平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

### 二、左旋 ###

1）已知数列\{4,3,6,5,7,8\}

![1007094-20190911210458595-73194195.png][]

1     //左旋转方法
     2     private void leftRotate() {
     3         
     4         //创建新的结点，以当前根结点的值
     5         Node newNode = new Node(value);
     6         //把新的结点的左子树设置成当前结点的左子树
     7         newNode.left = left;
     8         //把新的结点的右子树设置成带你过去结点的右子树的左子树
     9         newNode.right = right.left;
    10         //把当前结点的值替换成右子结点的值
    11         value = right.value;
    12         //把当前结点的右子树设置成当前结点右子树的右子树
    13         right = right.right;
    14         //把当前结点的左子树(左子结点)设置成新的结点
    15         left = newNode;                
    16     }

### 三、右旋 ###

1）已知数列\{10,12,8,9,7,6\}

![1007094-20190911210549320-1509228648.png][]

1     //右旋转
    2     private void rightRotate() {
    3         Node newNode = new Node(value);
    4         newNode.right = right;
    5         newNode.left = left.right;
    6         value = left.value;
    7         left = left.left;
    8         right = newNode;
    9     }

### 四、双旋 ###

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列  
　　int\[\] arr = \{ 10, 11, 7, 6, 8, 9 \};  运行原来的代码可以看到，并没有转成 AVL树.  
　　int\[\] arr = \{2,1,6,5,7,3\}; // 运行原来的代码可以看到，并没有转成 AVL树

![1007094-20190911211935152-103225978.png][]

### 五、完整代码 ###

1 public class AVLTreeDemo {
      2 
      3     public static void main(String[] args) {
      4         //int[] arr = {4,3,6,5,7,8};
      5         //int[] arr = { 10, 12, 8, 9, 7, 6 };
      6         int[] arr = { 10, 11, 7, 6, 8, 9 };  
      7         //创建一个 AVLTree对象
      8         AVLTree avlTree = new AVLTree();
      9         //添加结点
     10         for(int i=0; i < arr.length; i++) {
     11             avlTree.add(new Node(arr[i]));
     12         }
     13         
     14         //遍历
     15         System.out.println("中序遍历");
     16         avlTree.infixOrder();
     17         
     18         System.out.println("在平衡处理~~");
     19         System.out.println("树的高度=" + avlTree.getRoot().height()); //3
     20         System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
     21         System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
     22         System.out.println("当前的根结点=" + avlTree.getRoot());//8
     23         
     24         
     25     }
     26 
     27 }
     28 
     29 // 创建AVLTree
     30 class AVLTree {
     31     private Node root;
     32 
     33     public Node getRoot() {
     34         return root;
     35     }
     36 
     37     // 查找要删除的结点
     38     public Node search(int value) {
     39         if (root == null) {
     40             return null;
     41         } else {
     42             return root.search(value);
     43         }
     44     }
     45 
     46     // 查找父结点
     47     public Node searchParent(int value) {
     48         if (root == null) {
     49             return null;
     50         } else {
     51             return root.searchParent(value);
     52         }
     53     }
     54 
     55     // 编写方法:
     56     // 1. 返回的 以node 为根结点的二叉排序树的最小结点的值
     57     // 2. 删除node 为根结点的二叉排序树的最小结点
     58     /**
     59      * 
     60      * @param node
     61      *            传入的结点(当做二叉排序树的根结点)
     62      * @return 返回的 以node 为根结点的二叉排序树的最小结点的值
     63      */
     64     public int delRightTreeMin(Node node) {
     65         Node target = node;
     66         // 循环的查找左子节点，就会找到最小值
     67         while (target.left != null) {
     68             target = target.left;
     69         }
     70         // 这时 target就指向了最小结点
     71         // 删除最小结点
     72         delNode(target.value);
     73         return target.value;
     74     }
     75 
     76     // 删除结点
     77     public void delNode(int value) {
     78         if (root == null) {
     79             return;
     80         } else {
     81             // 1.需求先去找到要删除的结点 targetNode
     82             Node targetNode = search(value);
     83             // 如果没有找到要删除的结点
     84             if (targetNode == null) {
     85                 return;
     86             }
     87             // 如果我们发现当前这颗二叉排序树只有一个结点
     88             if (root.left == null && root.right == null) {
     89                 root = null;
     90                 return;
     91             }
     92 
     93             // 去找到targetNode的父结点
     94             Node parent = searchParent(value);
     95             // 如果要删除的结点是叶子结点
     96             if (targetNode.left == null && targetNode.right == null) {
     97                 // 判断targetNode 是父结点的左子结点，还是右子结点
     98                 if (parent.left != null && parent.left.value == value) { // 是左子结点
     99                     parent.left = null;
    100                 } else if (parent.right != null && parent.right.value == value) {
        // 是由子结点
    101                     parent.right = null;
    102                 }
    103             } else if (targetNode.left != null && targetNode.right != null) { // 删除有两颗子树的节点
    104                 int minVal = delRightTreeMin(targetNode.right);
    105                 targetNode.value = minVal;
    106 
    107             } else { // 删除只有一颗子树的结点
    108                 // 如果要删除的结点有左子结点
    109                 if (targetNode.left != null) {
    110                     if (parent != null) {
    111                         // 如果 targetNode 是 parent 的左子结点
    112                         if (parent.left.value == value) {
    113                             parent.left = targetNode.left;
    114                         } else { // targetNode 是 parent 的右子结点
    115                             parent.right = targetNode.left;
    116                         }
    117                     } else {
    118                         root = targetNode.left;
    119                     }
    120                 } else { // 如果要删除的结点有右子结点
    121                     if (parent != null) {
    122                         // 如果 targetNode 是 parent 的左子结点
    123                         if (parent.left.value == value) {
    124                             parent.left = targetNode.right;
    125                         } else { // 如果 targetNode 是 parent 的右子结点
    126                             parent.right = targetNode.right;
    127                         }
    128                     } else {
    129                         root = targetNode.right;
    130                     }
    131                 }
    132 
    133             }
    134 
    135         }
    136     }
    137 
    138     // 添加结点的方法
    139     public void add(Node node) {
    140         if (root == null) {
    141             root = node;// 如果root为空则直接让root指向node
    142         } else {
    143             root.add(node);
    144         }
    145     }
    146 
    147     // 中序遍历
    148     public void infixOrder() {
    149         if (root != null) {
    150             root.infixOrder();
    151         } else {
    152             System.out.println("二叉排序树为空，不能遍历");
    153         }
    154     }
    155 }
    156 
    157 // 创建Node结点
    158 class Node {
    159     int value;
    160     Node left;
    161     Node right;
    162 
    163     public Node(int value) {
    164 
    165         this.value = value;
    166     }
    167 
    168     // 返回左子树的高度
    169     public int leftHeight() {
    170         if (left == null) {
    171             return 0;
    172         }
    173         return left.height();
    174     }
    175 
    176     // 返回右子树的高度
    177     public int rightHeight() {
    178         if (right == null) {
    179             return 0;
    180         }
    181         return right.height();
    182     }
    183 
    184     // 返回 以该结点为根结点的树的高度
    185     public int height() {
    186         return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    187     }
    188     
    189     //左旋转方法
    190     private void leftRotate() {
    191         
    192         //创建新的结点，以当前根结点的值
    193         Node newNode = new Node(value);
    194         //把新的结点的左子树设置成当前结点的左子树
    195         newNode.left = left;
    196         //把新的结点的右子树设置成带你过去结点的右子树的左子树
    197         newNode.right = right.left;
    198         //把当前结点的值替换成右子结点的值
    199         value = right.value;
    200         //把当前结点的右子树设置成当前结点右子树的右子树
    201         right = right.right;
    202         //把当前结点的左子树(左子结点)设置成新的结点
    203         left = newNode;                
    204     }
    205     
    206     //右旋转
    207     private void rightRotate() {
    208         Node newNode = new Node(value);
    209         newNode.right = right;
    210         newNode.left = left.right;
    211         value = left.value;
    212         left = left.left;
    213         right = newNode;
    214     }
    215 
    216     // 查找要删除的结点
    217     /**
    218      * 
    219      * @param value
    220      *            希望删除的结点的值
    221      * @return 如果找到返回该结点，否则返回null
    222      */
    223     public Node search(int value) {
    224         if (value == this.value) { // 找到就是该结点
    225             return this;
    226         } else if (value < this.value) {
        // 如果查找的值小于当前结点，向左子树递归查找
    227             // 如果左子结点为空
    228             if (this.left == null) {
    229                 return null;
    230             }
    231             return this.left.search(value);
    232         } else { // 如果查找的值不小于当前结点，向右子树递归查找
    233             if (this.right == null) {
    234                 return null;
    235             }
    236             return this.right.search(value);
    237         }
    238 
    239     }
    240 
    241     // 查找要删除结点的父结点
    242     /**
    243      * 
    244      * @param value
    245      *            要找到的结点的值
    246      * @return 返回的是要删除的结点的父结点，如果没有就返回null
    247      */
    248     public Node searchParent(int value) {
    249         // 如果当前结点就是要删除的结点的父结点，就返回
    250         if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
    251             return this;
    252         } else {
    253             // 如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
    254             if (value < this.value && this.left != null) {
    255                 return this.left.searchParent(value); // 向左子树递归查找
    256             } else if (value >= this.value && this.right != null) {
    257                 return this.right.searchParent(value); // 向右子树递归查找
    258             } else {
    259                 return null; // 没有找到父结点
    260             }
    261         }
    262 
    263     }
    264 
    265     @Override
    266     public String toString() {
    267         return "Node [value=" + value + "]";
    268     }
    269 
    270     // 添加结点的方法
    271     // 递归的形式添加结点，注意需要满足二叉排序树的要求
    272     public void add(Node node) {
    273         if (node == null) {
    274             return;
    275         }
    276 
    277         // 判断传入的结点的值，和当前子树的根结点的值关系
    278         if (node.value < this.value) {
    279             // 如果当前结点左子结点为null
    280             if (this.left == null) {
    281                 this.left = node;
    282             } else {
    283                 // 递归的向左子树添加
    284                 this.left.add(node);
    285             }
    286         } else { // 添加的结点的值大于 当前结点的值
    287             if (this.right == null) {
    288                 this.right = node;
    289             } else {
    290                 // 递归的向右子树添加
    291                 this.right.add(node);
    292             }
    293 
    294         }
    295         
    296         //当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
    297         if(rightHeight() - leftHeight() > 1) {
    298             //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
    299             if(right != null && right.leftHeight() > right.rightHeight()) {
    300                 //先对右子结点进行右旋转
    301                 right.rightRotate();
    302                 //然后在对当前结点进行左旋转
    303                 leftRotate(); //左旋转..
    304             } else {
    305                 //直接进行左旋转即可
    306                 leftRotate();
    307             }
    308             return ; //必须要!!!
    309         }
    310         
    311         //当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
    312         if(leftHeight() - rightHeight() > 1) {
    313             //如果它的左子树的右子树高度大于它的左子树的高度
    314             if(left != null && left.rightHeight() > left.leftHeight()) {
    315                 //先对当前结点的左结点(左子树)->左旋转
    316                 left.leftRotate();
    317                 //再对当前结点进行右旋转
    318                 rightRotate();
    319             } else {
    320                 //直接进行右旋转即可
    321                 rightRotate();
    322             }
    323         }
    324     }
    325 
    326     // 中序遍历
    327     public void infixOrder() {
    328         if (this.left != null) {
    329             this.left.infixOrder();
    330         }
    331         System.out.println(this);
    332         if (this.right != null) {
    333             this.right.infixOrder();
    334         }
    335     }
    336 
    337 }

[1007094-20190911210458595-73194195.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/68f63f5b5ebb48dba5814ef2f9180ea0.png
[1007094-20190911210549320-1509228648.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/34b46390c8e14852b6ae402b852aae43.png
[1007094-20190911211935152-103225978.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b2b26195565f464194ea7b22561f3636.png