平衡二叉树（Self-balancing binary search tree）之AVL树

傷城~ 2023-07-22 03:47 63阅读 0赞

**1.基础**

（基础）二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树

**2.AVL树出现的背景**

（AVL树出现的背景）问题分析：  
数组 \{1, 2, 3, 4, 5, 6\} ，对应的二叉排序树(BST)的问题所在  
（1）左子树全部为空，从形式上看，更像一个单链表  
（2）插入速度没有影响  
（3）查询速度明显降低(因为需要依次比较)，不能发挥BST的优势，因为每次还需要比较左子树，查询速度比单链表还慢

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70][]

**3.优化演变，解决BST查询带来的问题**

（由基础优化演变而来，解决BST查询带来的问题）AVL树（以发明者G.M.Adelson-Velsky和E.M.Landis的名字命名），又称平衡二叉搜索树（Self-balancing binary search tree），也称平衡二叉树  
AVL树特点：  
（1）本身是一棵二叉排序树  
（2）带平衡条件：每个结点的左右子树的高度差的绝对值不超过1，最多为1  
AVL树本质就是带平衡功能的二叉排序树

平衡二叉树的实现方式有红黑树（算法）、AVL（算法）、替罪羊树、Treap、伸展树等

**4.什么时候需要维护平衡二叉树的平衡？**

二叉树进行节点的 添加 与 删除 的时候，都会破坏平衡二叉树的平衡，所以在二叉树添加节点完毕之后 与 二叉树删除节点完毕之后，都需要重新维护平衡二叉树的平衡

**5.维护平衡二叉树平衡的方式之一**

单向旋转之左旋转

添加一个节点之后，如果存在二叉树的任意一个节点的右子树的高度 减去 左子树的高度 所得的差大于 1 ，则需要把当前的二叉树通过左旋转的方式维护成平衡二叉树，即AVL树（递归的方式保证了任意一个节点的左右子树的高度差的绝对值不超过1）

左旋转的步骤

（1）创建一个新节点 newNode ，新节点的值等于当前节点的值（由于添加节点的代码存在递归，注意分析 当前节点 会有不同的指向）  
（2）把新节点的左子树指向当前节点的左子树  
newNode.left = this.left  
（3）把新节点的右子树指向当前节点的右子树的左子树  
newNode.right = this.right.left  
（4）把当前节点的值设置为其右子节点的值  
this.value = this.right.value  
（5）把当前节点的右子树指向其右子树的右子树  
this.right = this.right.right  
（6）把当前节点的左子树指向新节点  
this.left = newNode

图解左旋转的步骤

使用数组 \{4, 3, 6, 5, 7, 8\} 构造平衡二叉树的过程中，在添加 8 之前，二叉树中的任意一个节点的左右子树的高度差的绝对值不超过 1 ，即为 AVL树，当 添加 8 之后，得到如下二叉树，此时以 4 作为当前节点，它的右子树高度为 3 ， 它的左子树高度为 1 ，即 3 - 1 = 2 > 1 ，该二叉树就不再是一棵平衡二叉树了，通过左旋转维护成平衡二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 1][]

（1）创建一个新节点 newNode ，新节点的值等于当前节点的值（由于添加节点的代码存在递归，注意分析 当前节点 会有不同的指向）

![20200404203249300.png][]

（2）把新节点的左子树指向当前节点的左子树  
newNode.left = this.left

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 2][]  
（3）把新节点的右子树指向当前节点的右子树的左子树  
newNode.right = this.right.left

![20200404203745450.png][]  
（4）把当前节点的值设置为其右子节点的值  
this.value = this.right.value

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 3][]  
（5）把当前节点的右子树指向其右子树的右子树  
this.right = this.right.right

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 4][]  
（6）把当前节点的左子树指向新节点  
this.left = newNode

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 5][]

最后通过左旋转得到的平衡二叉树，即AVL树，如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 6][]

**6.维护平衡二叉树平衡的方式之二**

单向旋转之右旋转

添加一个节点之后，如果存在二叉树的任意一个节点的左子树的高度 减去 右子树的高度 所得的差大于 1 ，则需要把当前的二叉树通过右旋转的方式维护成平衡二叉树，即AVL树（递归的方式保证了任意一个节点的左右子树的高度差的绝对值不超过1）

右旋转的步骤

（1）创建一个新节点 newNode ，新节点的值等于当前节点的值（由于添加节点的代码存在递归，注意分析 当前节点 会有不同的指向）  
（2）把新节点的右子树指向当前节点的右子树  
newNode.right = this.right  
（3）把新节点的左子树指向当前节点的左子树的右子树  
newNode.left = this.left.right  
（4）把当前节点的值设置为其左子节点的值  
this.value = this.left.value  
（5）把当前节点的左子树指向其左子树的左子树  
this.left = this.left.left  
（6）把当前节点的右子树指向新节点  
this.right= newNode

图解右旋转的步骤

使用数组 \{10, 12, 8, 9, 7, 6\} 构造平衡二叉树的过程中，在添加 6 之前，二叉树中的任意一个节点的左右子树的高度差的绝对值不超过 1 ，即为 AVL树，当 添加 6 之后，得到如下二叉树，此时以 10 作为当前节点，它的左子树高度为 3 ， 它的右子树高度为 1 ，即 3 - 1 = 2 > 1 ，该二叉树就不再是一棵平衡二叉树了，通过右旋转维护成平衡二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 7][]

（1）创建一个新节点 newNode ，新节点的值等于当前节点的值（由于添加节点的代码存在递归，注意分析 当前节点 会有不同的指向）

![20200404220041201.png][]

（2）把新节点的右子树指向当前节点的右子树  
newNode.right = this.right

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 8][]

（3）把新节点的左子树指向当前节点的左子树的右子树  
newNode.left = this.left.right

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 9][]

（4）把当前节点的值设置为其左子节点的值  
this.value = this.left.value

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 10][]  
（5）把当前节点的左子树指向其左子树的左子树  
this.left = this.left.left

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 11][]  
（6）把当前节点的右子树指向新节点  
this.right= newNode

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 12][]

最后通过右旋转得到的平衡二叉树，即AVL树，如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 13][]

**7.维护平衡二叉树平衡的方式之三**

双向旋转之 先左 再右 旋转

添加一个节点之后，如果存在二叉树的任意一个节点的左子树的高度 减去 右子树的高度 所得的差大于 1 ，并且任意节点的左子树的右子树高度大于左子树高度，则需要把当前的二叉树通过双向旋转之 先左 再右 旋转的方式维护成平衡二叉树，即AVL树（递归的方式保证了任意一个节点的左右子树的高度差的绝对值不超过1）

先左再右旋转步骤

（1）当前二叉树任意一个节点符合右旋转条件时  
（2）并且如果任意一个节点的左子树的右子树高度大于左子树高度  
（3）先对当前节点的左子节点进行左旋转  
（4）再对当前节点进行右旋转

图解双向旋转之先左再右旋转的步骤

使用数组 \{10, 11, 7, 6, 8, 9\} 构造平衡二叉树的过程中，在添加 9 之前，二叉树中的任意一个节点的左右子树的高度差的绝对值不超过 1 ，即为 AVL树，当 添加 9 之后，得到如下二叉树，此时以 10 作为当前节点，它的左子树高度为 3 ， 它的右子树高度为 1，即 3 - 1 = 2 > 1 ，该二叉树就不再是一棵平衡二叉树了，并且 10 的 左子树（即为 7）的右子树高度（高度为 2）大于左子树高度（高度为 1），通过双向旋转之 先左 再右 旋转维护成平衡二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 14][]

（1）先对当前节点（即为 10）的左子节点（即为 7）进行左旋转

参考前面左旋转的规则即可

得到如下 二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 15][]

（2）再对当前节点（即为 10）进行右旋转

参考前面右旋转的规则即可

得到如下 平衡二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 16][]

双向旋转之 先右 再左 旋转

添加一个节点之后，如果存在二叉树的任意一个节点的右子树的高度 减去 左子树的高度 所得的差大于 1 ，并且任意节点的右子树的左子树高度大于右子树高度，则需要把当前的二叉树通过双向旋转之 先右 再左 旋转的方式维护成平衡二叉树，即AVL树（递归的方式保证了任意一个节点的左右子树的高度差的绝对值不超过1）

先右再左旋转步骤

（1）当前二叉树任意一个节点符合左旋转条件时  
（2）并且如果任意一个节点的右子树的左子树高度大于右子树高度  
（3）先对当前节点的右子节点进行右旋转  
（4）再对当前节点进行左旋转

图解双向旋转之先右再左旋转的步骤

使用数组 \{2, 1, 6, 5, 7, 3\} 构造平衡二叉树的过程中，在添加 3 之前，二叉树中的任意一个节点的左右子树的高度差的绝对值不超过 1 ，即为 AVL树，当 添加 3 之后，得到如下二叉树，此时以 2 作为当前节点，它的右子树高度为 3 ， 它的左子树高度为 1 ，即 3 - 1 = 2 > 1 ，该二叉树就不再是一棵平衡二叉树了，并且 2 的 右子树（即为 6）的左子树高度（高度为 2）大于右子树高度（高度为 1），通过双向旋转之 先右 再左 旋转维护成平衡二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 17][]

（1）先对当前节点（即为 2）的右子节点（即为 6）进行右旋转

参考前面右旋转的规则即可

得到如下 二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 18][]

（2）再对当前节点（即为 2）进行左旋转

参考前面左旋转的规则即可

得到如下 平衡二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 19][]

**8.代码实现**

包括 左旋转、右旋转、双向旋转 三种情况

package com.zzb.datastructure.avl;
    
    import java.io.Serializable;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/4/4 15:31
     * @Description: 平衡二叉树之AVL树
     */
    public class AVLTreeDemo {
        public static void main(String[] args) {
            // 测试左旋转
    //        testLeftRotate();
    
            // 测试右旋转
    //        testRightRotate();
    
            // 测试双向旋转之先左再右
    //        testLeftAndRightRotate();
    
            // 测试双向旋转之先右再左
            testRightAndLeftRotate();
        }
    
        // 测试左旋转
        private static void testLeftRotate() {
            // 创建AVL树
            AVLTree avlTree = new AVLTree();
            // 产生左旋转的数组
            int[] array = {4, 3, 6, 5, 7, 8};
            for(int i = 0; i < array.length; i++) {
                avlTree.add(new Node(array[i]));
            }
            // 中序遍历
            avlTree.infixOrder();
            System.out.println("AVL树的高度 == " + avlTree.height());
            System.out.println("左子树的高度 == " + avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度 == " + avlTree.getRoot().rightHeight());
            /*
            Node{value=3}
            Node{value=4}
            Node{value=5}
            Node{value=6}
            Node{value=7}
            Node{value=8}
            AVL树的高度 == 3
            左子树的高度 == 2
            右子树的高度 == 2*/
        }
    
        // 测试右旋转
        private static void testRightRotate() {
            // 创建AVL树
            AVLTree avlTree = new AVLTree();
            // 产生右旋转的数组
            int[] array = {10, 12, 8, 9, 7, 6};
            for(int i = 0; i < array.length; i++) {
                avlTree.add(new Node(array[i]));
            }
            // 中序遍历
            avlTree.infixOrder();
            System.out.println("AVL树的高度 == " + avlTree.height());
            System.out.println("左子树的高度 == " + avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度 == " + avlTree.getRoot().rightHeight());
            /*
            Node{value=6}
            Node{value=7}
            Node{value=8}
            Node{value=9}
            Node{value=10}
            Node{value=12}
            AVL树的高度 == 3
            左子树的高度 == 2
            右子树的高度 == 2*/
        }
    
        // 测试双向旋转之先左再右
        private static void testLeftAndRightRotate() {
            // 创建AVL树
            AVLTree avlTree = new AVLTree();
            // 产生双向旋转之先左再右的数组
            int[] array = {10, 11, 7, 6, 8, 9};
            for(int i = 0; i < array.length; i++) {
                avlTree.add(new Node(array[i]));
            }
            // 中序遍历
            avlTree.infixOrder();
            System.out.println("AVL树的高度 == " + avlTree.height());
            System.out.println("左子树的高度 == " + avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度 == " + avlTree.getRoot().rightHeight());
            /*
            Node{value=6}
            Node{value=7}
            Node{value=8}
            Node{value=9}
            Node{value=10}
            Node{value=11}
            AVL树的高度 == 3
            左子树的高度 == 2
            右子树的高度 == 2*/
        }
    
        // 测试双向旋转之先右再左
        private static void testRightAndLeftRotate() {
            // 创建AVL树
            AVLTree avlTree = new AVLTree();
            // 产生双向旋转之先右再左的数组
            int[] array = {2, 1, 6, 5, 7, 3};
            for(int i = 0; i < array.length; i++) {
                avlTree.add(new Node(array[i]));
            }
            // 中序遍历
            avlTree.infixOrder();
            System.out.println("AVL树的高度 == " + avlTree.height());
            System.out.println("左子树的高度 == " + avlTree.getRoot().leftHeight());
            System.out.println("右子树的高度 == " + avlTree.getRoot().rightHeight());
            /*
            Node{value=1}
            Node{value=2}
            Node{value=3}
            Node{value=5}
            Node{value=6}
            Node{value=7}
            AVL树的高度 == 3
            左子树的高度 == 2
            右子树的高度 == 2*/
        }
    }
    
    /**
     * AVL树
     */
    class AVLTree {
    
        // 树根
        private Node root;
    
        /**
         * 二叉排序树添加节点
         *
         * @param node 待添加的节点
         */
        public void add(Node node) {
            // 根节点非空判断
            if(this.getRoot() == null) { // null
                this.setRoot(node);
            } else { // not null
                this.getRoot().add(node);
            }
        }
    
        // 二叉排序树删除节点
        /*有三种情况需要考虑
        （1）删除叶子节点 (比如：2, 5, 9, 12)
        （2）删除只有一颗子树的节点 (比如：1)
        （3）删除有两颗子树的节点(比如：7, 3, 10 )*/
        /*
        第一种情况:
        删除叶子节点 (比如：2, 5, 9, 12)
        思路
        (1) 需求先去找到要删除的结点 targetNode
        (2) 找到 targetNode 的 父结点 parent
        (3) 确定 targetNode 是 parent 的左子结点 还是右子结点
        (4) 根据前面的情况来对应删除
        左子结点 parent.left = null
        右子结点 parent.right = null
    
        第二种情况: 删除只有一颗子树的节点 （比如：1）
        思路
        (1) 需求先去找到要删除的结点 targetNode
        (2) 找到 targetNode 的 父结点 parent
        (3) 确定 targetNode 的子结点是左子结点还是右子结点
        (4) targetNode 是 parent 的左子结点还是右子结点
        (5) 如果 targetNode 有左子结点
            5.1） 如果 targetNode 是 parent 的左子结点
            parent.left = targetNode.left
            5.2） 如果 targetNode 是 parent 的右子结点
            parent.right = targetNode.left
        (6) 如果 targetNode 有右子结点
            6.1） 如果 targetNode 是 parent 的左子结点
            parent.left = targetNode.right
            6.2） 如果 targetNode 是 parent 的右子结点
            parent.right = targetNode.right
    
        情况三 ： 删除有两颗子树的节点. (比如：7, 3, 10 )
        思路
        (1) 需求先去找到要删除的结点 targetNode
        (2) 找到 targetNode 的 父结点 parent
        (3) 从 targetNode 的右子树找到最小的结点
        (4) 用一个临时变量，将 最小结点的值保存 temp
        (5) 删除该最小结点
        (6) targetNode.value = temp*/
        public void delOne(int value) {
            // 根节点非空判断
            if(this.getRoot() == null) {
                return;
            } else {
                // (1) 需求先去找到要删除的结点 targetNode
                Node targetNode = search(value);
                // 没有找到要删除的节点
                if(targetNode == null) {
                    return;
                }
                // 走到该位置，并且二叉排序树只有一个跟节点
                if(this.getRoot() != null
                        && this.getRoot().getLeft() == null
                        && this.getRoot().getRight() == null) {
                    this.setRoot(null);
                    return;
                }
                // (2) 找到 targetNode 的 父结点 parent
                Node parentNode = searchParent(value);
                // 情况一：要删除的节点时叶子节点
                if(targetNode.getLeft() == null && targetNode.getRight() == null) {
                    // 判断是左叶子节点、还是有叶子节点
                    if(parentNode.getLeft() != null && parentNode.getLeft().getValue() == value) { // 左子节点
                        parentNode.setLeft(null);
                    } else if(parentNode.getRight() != null && parentNode.getRight().getValue() == value) { // 右子节点
                        parentNode.setRight(null);
                    }
                    // 情况三：要删除的节点存在左、右子树
                } else if(targetNode.getLeft() != null && targetNode.getRight() != null) {
                    // 从 targetNode 的右子树找到最小的结点
                    Integer minVal = delRightTreeMin(targetNode.getRight());
                    targetNode.setValue(minVal);
                } else { // 情况二：要删除的节点存在一棵子树
                    if(targetNode.getLeft() != null) { // targetNode有左子节点
                        if(parentNode != null) {
                            if(parentNode.getLeft().getValue() == value) { // targetNode是parentNode的左子节点
                                parentNode.setLeft(targetNode.getLeft());
                            } else { // targetNode是parentNode的右子节点
                                parentNode.setRight(targetNode.getLeft());
                            }
                        } else {
                            this.setRoot(targetNode.getLeft());
                        }
                    } else { // targetNode有右子节点
                        if(parentNode != null) {
                            if(parentNode.getLeft().getValue() == value) { // targetNode是parentNode的左子节点
                                parentNode.setLeft(targetNode.getRight());
                            } else { // targetNode是parentNode的右子节点
                                parentNode.setRight(targetNode.getRight());
                            }
                        } else {
                            this.setRoot(targetNode.getRight());
                        }
                    }
                }
            }
        }
    
        // 找到要删除的结点 targetNode
        private Node search(Integer value) {
            if(this.getRoot() == null) {
                return null;
            } else {
                return this.getRoot().search(value);
            }
        }
    
        // 找到 targetNode 的 父结点 parentNode
        private Node searchParent(Integer value) {
            if(this.getRoot() == null) {
                return null;
            } else {
                return this.getRoot().searchParent(value);
            }
        }
    
        /**
         * 从 targetNode 的右子树找到最小的结点
         * @param node 传入的结点(当做二叉排序树的根结点)
         * @return 返回的 以node为根结点的二叉排序树的最小结点的值
         */
        private Integer delRightTreeMin(Node node) {
            Node target = node;
            // 循环遍历左子节点，就会找到最小值的节点
            while (target.getLeft() != null) {
                target = target.getLeft();
            }
            // 删除最小节点，就是删除叶子节点的情况
            delOne(target.getValue());
            return target.getValue();
        }
    
        /**
         * 获取平衡二叉树的高度
         *
         * @return 平衡二叉树的高度
         */
        public int height() {
            return this.getRoot().height();
        }
    
        // 二叉排序树中序遍历
        public void infixOrder() {
            if(this.getRoot() == null) {
                System.out.println("二叉树为空，无法遍历！");
            } else {
                this.getRoot().infixOrder();
            }
        }
    
        public Node getRoot() {
            return root;
        }
    
        public void setRoot(Node root) {
            this.root = root;
        }
    
    }
    
    /**
     * 节点类
     */
    class Node implements Serializable {
        private static final long serialVersionUID = -1256839472477162307L;
    
        // 节点值
        private Integer value;
        // 某个节点的左子节点
        private Node left;
        // 某个节点的右子节点
        private Node right;
    
        /**
         * 添加节点
         *
         * @param node 待添加的节点
         */
        public void add(Node node) {
            // 待添加节点的非空判断
            if(node == null) {
                return;
            }
            if(this.getValue() > node.getValue()) { // 当前节点大于添加节点
                if(this.getLeft() == null) { // 添加到当前节点的左边
                    this.setLeft(node);
                } else { // 递归判断
                    this.getLeft().add(node);
                }
            } else { // 当前节点小于添加节点
                if(this.getRight() == null) { // 添加到当前节点的右边
                    this.setRight(node);
                } else { // 递归调用
                    this.getRight().add(node);
                }
            }
    
            // 添加一个节点之后，如果存在二叉树的任意一个节点的右子树的高度 减去 左子树的高度 所得的差大于 1 ，
            // 则需要把当前的二叉树通过左旋转的方式维护成平衡二叉树，即AVL树（递归的方式保证了任意一个节点的左右子树的高度差的绝对值不超过1）
            if(this.rightHeight() - this.leftHeight() > 1) {
                // （1）当前二叉树任意一个节点符合左旋转条件时
                // （2）并且如果任意一个节点的右子树的左子树高度大于右子树高度
                if(this.getRight() != null && this.getRight().leftHeight() > this.getRight().rightHeight()) {
                    // （3）先对当前节点的右子节点进行右旋转
                    this.getRight().rightRotate();
                    // （4）再对当前节点进行左旋转
                    this.leftRotate();
                }else {
                    this.leftRotate();
                }
                return; // 必须要!!!
            }
    
            // 添加一个节点之后，如果存在二叉树的任意一个节点的左子树的高度 减去 右子树的高度 所得的差大于 1 ，
            // 则需要把当前的二叉树通过右旋转的方式维护成平衡二叉树，即AVL树（递归的方式保证了任意一个节点的左右子树的高度差的绝对值不超过1）
            if(this.leftHeight() - this.rightHeight() > 1) {
                // （1）当前二叉树任意一个节点符合右旋转条件时
                // （2）如果任意一个节点的左子树的右子树高度大于左子树高度
                if(this.getLeft() != null && this.getLeft().rightHeight() > this.getLeft().leftHeight()) {
                    // （3）先对当前节点的左子节点进行左旋转
                    this.getLeft().leftRotate();
                    // （4）再对当前节点进行右旋转
                    this.rightRotate();
                }else {
                    this.rightRotate();
                }
            }
        }
    
        /**
         * 左旋转
         */
        private void leftRotate() {
            // （1）创建一个新节点 newNode ，新节点的值等于当前节点的值（由于添加节点的代码存在递归，注意分析 当前节点 会有不同的指向）
            Node newNode = new Node(this.getValue());
            // （2）把新节点的左子树指向当前节点的左子树 newNode.left = this.left
            newNode.left = this.getLeft();
            // （3）把新节点的右子树指向当前节点的右子树的左子树 newNode.right = this.right.left
            newNode.right = this.getRight().getLeft();
            // （4）把当前节点的值设置为其右子节点的值 this.value = this.right.value
            this.value = this.getRight().getValue();
            // （5）把当前节点的右子树指向其右子树的右子树 this.right = this.right.right
            this.right = this.getRight().getRight();
            // （6）把当前节点的左子树指向新节点 this.left = newNode
            this.left = newNode;
        }
    
        /**
         * 右旋转
         */
        private void rightRotate() {
            // （1）创建一个新节点 newNode ，新节点的值等于当前节点的值（由于添加节点的代码存在递归，注意分析 当前节点 会有不同的指向）
            Node newNode = new Node(this.getValue());
            // （2）把新节点的右子树指向当前节点的右子树 newNode.right = this.right
            newNode.right = this.getRight();
            // （3）把新节点的左子树指向当前节点的左子树的右子树 newNode.left = this.left.right
            newNode.left = this.getLeft().getRight();
            // （4）把当前节点的值设置为其左子节点的值 this.value = this.left.value
            this.value = this.getLeft().getValue();
            // （5）把当前节点的左子树指向其左子树的左子树 this.left = this.left.left
            this.left = this.getLeft().getLeft();
            // （6）把当前节点的右子树指向新节点 this.right= newNode
            this.right = newNode;
        }
    
        // 查找要删除的节点
        public Node search(Integer value) {
            if(this.getValue() == value) { // 当前节点等于查找节点
                return this;
            } else if(this.getValue() > value) { // 当前节点大于查找节点
                if(this.getLeft() == null) {
                    return null;
                } else { // 左子树找
                    return this.getLeft().search(value);
                }
            } else { // 当前节点小于查找节点
                if(this.getRight() == null) {
                    return null;
                } else { // 右子树找
                    return this.getRight().search(value);
                }
            }
        }
    
        // 查找要删除节点的父节点
        public Node searchParent(Integer value) {
            if((this.getLeft() != null && this.getLeft().getValue() == value)
                    || (this.getRight() != null && this.getRight().getValue() == value)) {
                return this;
            } else {
                if(this.getValue() > value && this.getLeft() != null) { // 左子树找
                    return this.getLeft().searchParent(value);
                } else if(this.getValue() < value && this.getRight() != null) { // 右子树找
                    return this.getRight().searchParent(value);
                } else { // 没找到父节点
                    return null;
                }
            }
        }
    
        /**
         * 获取以某个节点作为根节点时二叉树的高度
         * 递归调用
         * @return 二叉树的高度
         */
        public int height() {
            // 某个节点的左右子树的高度求最大值加上某个节点自身为1的高度即为二叉树的高度
            return Math.max(this.getLeft() == null ? 0 : this.getLeft().height()
                    , this.getRight() == null ? 0 : this.getRight().height())
                    + 1;
        }
    
        /**
         * 某个节点的左子树高度
         *
         * @return 某个节点的左子树高度
         */
        public int leftHeight() {
            if(this.getLeft() == null) {
                return 0;
            }
            return this.getLeft().height();
        }
    
        /**
         * 某个节点的右子树高度
         *
         * @return 某个节点的右子树高度
         */
        public int rightHeight() {
            if(this.getRight() == null) {
                return 0;
            }
            return this.getRight().height();
        }
    
        /**
         * 中序遍历
         * 每个节点都会执行中序遍历方法中的三个动作，涉及到递归方法的压栈与弹栈
         */
        public void infixOrder() {
            // （1）判断如果当前节点的左子节点不为空，则当前节点的左子节点递归执行中序遍历方法进行中序遍历
            if(this.getLeft() != null) {
                this.getLeft().infixOrder();
            }
            // （2）输出当前节点（初始节点是根节点root节点）
            System.out.println(this);
            // （3）判断如果当前节点的右子节点不为空，则当前节点的右子节点递归执行中序遍历方法进行中序遍历
            if(this.getRight() != null) {
                this.getRight().infixOrder();
            }
        }
    
        public Node(Integer value) {
            this.value = value;
        }
    
        public Integer getValue() {
            return value;
        }
    
        public void setValue(Integer value) {
            this.value = value;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + "}";
        }
    }

9.删除节点后 左、右、双向 旋转

待续。。。。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70]: /images/20230528/7b227a6c73b84b1bbcedd2ffae6cf99d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 1]: /images/20230528/45b86b9db54e408aa7618a9e2c4bcd8f.png
[20200404203249300.png]: /images/20230528/d5a8a6b7deeb454d8d4294129dc40cf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 2]: /images/20230528/83c4334f3f4049bebed539b9ddf2d5fe.png
[20200404203745450.png]: /images/20230528/24d2b522933a4d3e85983c97c76aa7f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 3]: /images/20230528/31f602efcdb642279bf738df1e02f56e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 4]: /images/20230528/b7b5234c821a4992996036ece9c69c9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 5]: /images/20230528/079d18ef71ae44ba90ed923a0dfe718c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 6]: /images/20230528/4b23302149654332bbaba42f882446b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 7]: /images/20230528/20efce7b56d24e91bce7c0cdcedf8980.png
[20200404220041201.png]: /images/20230528/e10548b2040946f29432d23903d897f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 8]: /images/20230528/35bc3ceb2d3c4cb89da2b83a630e20fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 9]: /images/20230528/a3b74304c0004808a7456a06cc7d2bd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 10]: /images/20230528/f2a8a4c534cc4843bab7072da15e4e64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 11]: /images/20230528/02e49d4275fa48c1bd5ea0b528b25e3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 12]: /images/20230528/0b28d1063f9b47c8ab1c8bd3a7d35485.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 13]: /images/20230528/4f3e18c35a814f49ab0920c8bd0ac04e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 14]: /images/20230528/aecc481cbb5349799c40fdb9b3c4d26b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 15]: /images/20230528/796a42e1b7bc4697ad71437f33a33fc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 16]: /images/20230528/7fee28b8c1a84cdfa56654007c54fb90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 17]: /images/20230528/b442bc63af6b478b9d23722ef63eabcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 18]: /images/20230528/e094ee5f056846dfabc07fe11be2b31c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 19]: /images/20230528/293bbff731e9410a8981cc47d153dd0b.png