《恋上数据结构与算法》笔记（十一）：平衡二叉搜索树 (AVL树)

妖狐艹你老母 2022-12-23 09:57 40阅读 0赞

# 目录 #

> 具体代码在 : [AVLTree][], 欢迎`star`

*  一、平衡二叉搜索树（Balance Binary Search Tree）
    
     *  1、退化成链表的二插搜索树
     *  2、平衡（Balance）
     *  3、如何改进二叉搜索树？
     *  4、常见的平衡二叉搜索树
 *  二、AVL树
 *  三、AVLTree失衡的几种情况
    
     *  1、添加导致的失衡
     *  2、添加失衡 LL - 右旋传（单旋）
     *  3、添加失衡 RR - 右旋传（单旋）
     *  4、添加失衡 LR - RR左旋转，LL右旋转（双旋）
     *  5、添加失衡 RL - LL右旋转，RR左旋转（双旋）
     *  6、删除导致的失衡
     *  7、删除失衡 LL - 右旋传（单旋）
 *  四、如何调整失衡
    
     *  添加- afterAdd()函数
        
         *  1、重写BST的afterAdd方法
         *   2、判断节点是否平衡 isBalanced
         *  3、更新节点的高度 updateHeight
         *  4、恢复平衡 rebalance）
         *  5、添加- rotateLeft(node) 和- rotateRight(node) 函数
     *  添加 -afterRemove(node) 函数
     *  AVLTree的内部类AVLNode
 *  五、AVLTree演变示例
 *  六、AVLTree总结

# 一、平衡二叉搜索树（Balance Binary Search Tree） #

跳转到目录

### 1、退化成`链表`的二插搜索树 ###

*  如果是按照`7、4、9、2、5、8、11`的顺序添加节点
    
    二叉搜索树的复杂度和树的`高度`有关, 如果是满二叉树, 其时间复杂度为`O(logn)`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center]
 *  如果是按照`2、4、5、7、8、9、11`的顺序添加节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 1]
 *  `删除节点`时，可能会导致二叉搜索树退化成`链表`, 如果删除`2，9，8，11`四个节点，就会导致`退化`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 2]  
    如何防止二叉搜素树退化成链表？让`添加，删除，搜索`的复杂度维持在`O(logn)`。

### 2、平衡（Balance） ###

跳转到目录

*  平衡：当节点数量`固定`时，左右子树的高度越接近，这棵二叉树就`越平衡`（高度越低）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 3]
 *  最理想的平衡，就是像`完全二叉树`，`满二叉树`那样，高度是最小的。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 4]

### 3、如何改进二叉搜索树？ ###

跳转到目录

*  节点的`添加`，`删除`顺序是无法限制的，也就是`随机`的。
 *  那么改进方案是：在节点的添加，删除操作之后，想办法让二叉搜索树`恢复平衡（减小树的高度）`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 5]
 *  如果接着继续调整节点的位置，完全可以达到`理想`平衡，但是付出的代价可能会比较大。如果`调整`次数太多，反而`增加`了时间复杂度。
 *  所以比较合适的方案是：用尽量少的调整次数达到`适度平衡`。
 *  一颗达到适度平衡的二叉搜索树，可以称之为：**`平衡二叉搜索树`**。

### 4、常见的平衡二叉搜索树 ###

跳转到目录  
经典常见的平衡二叉树 : `AVL树`、`红黑树`

*  AVL树：`Windows NT`内核中广泛使用。
 *  红黑树：java的`TreeMap`，`TreeSet`，`HashMap`，`HashSet`。

一般也称它们为：**自平衡的二叉搜索树（Self-balancing Binary Search Tree）**

# 二、AVLTree #

跳转到目录

*  什么是`平衡因子`：某节点的`左右子树`的`高度差`。
 *  AVL树的特点：
    
     *  每个节点的平衡因子只可能是`1，0，-1`。即`绝对值<=1`，如果超过`1`，称之为`失衡`。
     *  每个节点的左右子树`高度差`不超过`1`。
     *  `搜索，添加，删除`的时间复杂度是`O(logn)`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 7]

*  `AVL树`和`红黑树`，都是在`二叉搜索树`的基础上，增加了`自平衡`的功能。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 8]

# 三、AVLTree失衡的几种情况 #

跳转到目录

###### **`注意:`** 下来失衡通过旋转来恢复, 对`某个节点`进行旋转, 只需要关注`它的子树`的旋转, 空间想象出旋转后的样子! ######

### 1、添加导致的失衡 ###

*  示例：添加`13`导致失衡  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 9]
 *  最坏的情况，可能会导致所有`祖先节点 4，15，9`都失衡。
 *  但是`父节点12`，非祖先节点4，6，8，都不可能失衡

### 2、添加失衡 LL - 右旋传（单旋） ###

跳转到目录

*  `n`代表`node`，`p`代表`parent`，`g`代表`grandparent`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 10]
 *  如果在`T0`节点位置增加节点，那么`g`失去平衡。
 *  `LL`表示`失衡节点`与`添加节点`的关系，`添加节点`在`失衡节点`的`左边的左边`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 11]

*  因为是`g`左边的左边的节点使它失去`平衡`，所以这种情况称之为`LL`。
 *  `LL`的情况，一般需要`右旋转`(对 `g`)。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 12]
 *  思路：
    
     *  `g.left = p.right`
     *  `p.right = g`
     *  让`p`成为这颗子树的`根节点`。
     *  改变之后整棵树仍然是一颗二叉搜索树：`T0 < n < T1 < p < T2 < g < T3`。
     *  整棵树都达到平衡。
 *  还需要注意维护：
    
     *  `T2`，`p`，`g`的`parent`属性。
     *  先后更新`g`，`p`的高度属性。

### 3、添加失衡 RR - 左旋转（单旋） ###

跳转到目录

*  如果往`T2`或`T3`位置加入一个节点，则`g`会失衡。
 *  `RR`表示`失衡节点`与`添加节点`的关系，`添加节点`在`失衡节点`的`右边的右边`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 13]
 *  那么我们需要`左旋转`，使树达到平衡。
 *  思路：
    
     *  `g.right = p.left`
     *  `p.left = g`
     *  让`p`成为这颗子树的`根节点`。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 14]
 *  整棵树都达到了平衡。
 *  还需要注意维护：
    
     *  `T1`，`p`，`g`的`parent`属性。
     *  先后更新`g`，`p`的`高度`属性。

### 4、添加失衡 LR - RR左旋转，LL右旋转（双旋） ###

跳转到目录

*  `p`是`g`的`left`节点，`n`是`p`的`right`节点，此时往`n`添加节点，这种情况称为`LR`。
 *  `LR`表示`失衡节点`与`添加节点`的关系，`添加节点`在`失衡节点`的`左右`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 15]
 *  如果是`LR`，首先要进行一次`左旋转`，将二叉树变为`LL`。然后再进行一次`右旋转`，即可使树达到平衡。

### 5、添加失衡 RL - LL右旋转，RR左旋转（双旋） ###

跳转到目录

*  首先进行`右旋转`，使树变成`RR`，然后再进行`左旋转`，即可达到`平衡`。
 *  `RL`表示`失衡节点`与`添加节点`的关系，`添加节点`在`失衡节点`的`右边的左边`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 16]

### 6、删除导致的失衡 ###

跳转到目录

*  示例：删除`16`导致失衡
 *  `删除节点`可能会导致`父节点`或`祖先节点`失衡（只有一个节点会失衡），其他节点都不可能失衡。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 17]

### 7、删除失衡 LL - 右旋传（单旋） ###

跳转到目录

*  删除红色节点，`g`的平衡因子变为`2`，需要对`g`进行`右旋转`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 18]
 *  旋转后，整棵树是否平衡，取决于`旋转后`子树的`高度`是否发生变化。其实就取决于`绿色节点`是否存在。
 *  如果`绿色节点`不存在，那么在`右旋转`后，子树的高度减少`1`，可能会导致更高层的祖父节点失衡。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 19]
 *  更高层的祖先节点失衡，则需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡…
 *  极端情况下，所有`祖先节点`都需要进行`恢复平衡`的操作，共`O(logn)`次调整。

# 四、如何调整失衡 #

跳转到目录

*  **`注意:`** 首先要明白一个关系, `AVLTree` 继承 `BST`, `BST`继承`BinaryTree`。
 *  BST 和 BinaryTree的关系, 请参考[《恋上数据结构与算法》笔记（十）：二叉搜索树 III (重构二叉排序树)][III]
 *  在构建`AVLTree`的过程, 可能会对 `BST` 以及 `BinaryTree` 的代码进行`重构`

## 添加- afterAdd()函数 ##

跳转到目录

*  `失衡调整`应该在`添加节点`之后。
 *  所以我们需要对`BST`的`添加`方法进行改造，即在完成`添加节点`后，进行`失衡调整`。
 *  因为在`AVLTree`类中, 我们要`添加节点`, `删除节点`, 又因为BST中已经有`add`, `remove`的方法, 我们怎么复用父类中的这些方法, 同时再额外增加AVLTree的功能呢? `首先`在BST类中, 定义一个protected类型的`afterRemove(Node<E> node)`和`afterAdd(Node<E> node)`方法, 这两个方法都不用写`方法体`, 让继承BST的子类去重写这些方法即可, 只需要在BST的`add / remove`方法中, 调用这些方法就行, 到时候就会去加载`AVLTree`重写的方法了。

`BST 的 add方法:`

public void add(E element) { 
        ...
        // 添加第一个节点
        if (root == null) { 
            ...
            // 新添加节点之后的处理
            afterAdd(root);
        }
        // 添加的不是第一个节点
        else { 
            ...
            // 新添加节点之后的处理
            afterAdd(newNode);
        }
    }

### 1、重写BST的afterAdd方法 ###

跳转到目录

*  接下来我们再看如何实现`AVLTree`中这个`afterAdd(newNode)`函数。
 *  思路：通过`newNode`的`parent`属性，一路往上找，找到`高度最低`的那个`失衡节点`，然后对失衡节点进行调整。
 *  只要这个`高度最低`的`失衡节点`恢复平衡，那么所有的节点都恢复平衡了。

/** * 当添加新的节点的时候, 要判断添加的节点是否会导致树失衡 * * @param node 添加的节点 */
    @Override
    protected void afterAdd(Node<E> node) { 
        /* 从添加节点的父节点开始寻找失衡节点, 找到高度最低的祖父节点就是失衡节点, 将失衡节点旋转后, 让平衡因子 不超过 1 即可, 则失衡节点修复后, 整棵树就平衡了 */
        while ((node = node.parent) != null) { 
            // 判断node是否平衡
            if (isBalanced(node)) { 
                /* 因为即使添加完一个结点, 整棵树也是平衡的, 但是node的父节点高度 也发生了变化, 所以我们要更新它们的高度; 新添加的结点默认高度为1(height默认)了 */
                updateHeight(node);
            } else { 
                // 能到这里说明, node肯定不平衡, 且node是高度最小的节点
                // 恢复平衡
                rebalance(node);
                // 整棵树都平衡
                break;
            }
        }
    }

### 2、判断节点是否平衡 isBalanced ###

跳转到目录

*  在`afterAdd(newNode)`中，需要实现`isBalanced(node)`函数，用于`判断节点是否平衡`，从而决定是`更新高度`或`恢复平衡`。
 *  判断节点平衡的方式是`比较左右子节点高度`，所以需要给节点增加一个`高度`属性。
 *  如果节点是`平衡`的，只需要更新节点`高度`，通过获取`左右子树最大高度 + 1`即可。

/** * 判断节点是否平衡 * * @param node * @return */
    private boolean isBalanced(Node<E> node) { 
    	// balanceFactor() 为 AVLTree内部类AVLNode中的方法, 计算平衡因子; 看下面AVLNode类
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= ONE;
    }

### 3、更新节点的高度 updateHeight ###

跳转到目录

/** * 更新节点的高度 * * @param node */
    private void updateHeight(Node<E> node) { 
    	// updateHeight() 为 AVLTree内部类AVLNode中的方法, 计算节点高度; 看下面的AVLNode类
        ((AVLNode<E>) node).updateHeight();
    }

### 4、恢复平衡 rebalance ###

跳转到目录

*  最后我们还需要实现`rebalance(node)`函数。
 *  能够进入`rebalance(node)`函数，那么`node`即为上面分析的失衡的几种情况中的`g`，`g`代表`grandparent`。
 *  接下来还要拿到`p`和`n`节点。
 *  `p`是`g`左右子树`高度`最高的子节点。
 *  `n`是`p`左右子树`高度`最高的子节点。
 *  那么我们首先实现一个`获取较高子节点`的函数。

/** * AVLNode内部的方法 * 返回节点中左右子树中高度最高的子树 * 若左右高度相同, 则根据节点属于其父节点的左/右, 返回节点的左/右 * * @return */
    public Node<E> tallerChild() { 
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        if (leftHeight > rightHeight) return left;
        if (leftHeight < rightHeight) return right;
        return isLeftChild() ? left : right;
    }
    
    // --------------------------------------
    
    // 在BinaryTree的内部类Node中添加两个判断方法
    /** * 判断自己是否左子树 * * @return */
    public boolean isLeftChild() { 
        return parent != null && this == parent.left;
    }
    
    /** * 判断自己是否左子树 * * @return */
    public boolean isRightChild() { 
        return parent != null && this == parent.right;
    }

*  那么`rebalance(node)`函数实现如下：

/** * 恢复平衡-分LL、LR、RL、RR来旋转 * * @param grand 高度最低的那个不平衡节点 */
    private void rebalance(Node<E> grand) { 
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) {  // L
            if (node.isLeftChild()) {  // LL
                rotateRight(grand);
            } else {  // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else {  // R
            if (node.isLeftChild()) {  // RL
                rotateRight(parent);
                rotateLeft(grand);
            } else {  // RR
                rotateLeft(grand);
            }
        }
    }

### 5、添加- rotateLeft(node) 和- rotateRight(node) 函数 ###

跳转到目录

*  最后我们实现`rotateLeft()`和`rotateRight()`函数。

/** * 对node进行左旋转 * * @param grand */
    private void rotateLeft(Node<E> grand) { 
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
    
        afterRotate(grand, parent, child);
    }
    
    /** * 对node进行右旋转 * * @param grand */
    private void rotateRight(Node<E> grand) { 
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
    
        afterRotate(grand, parent, child);
    }
    
    /** * 旋转之后, 更新它们的parent; 并且更新旋转后的高度 * * @param grand * @param parent * @param child */
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) { 
        // 让parent为子树的根节点
        parent.parent = grand.parent;
        // 如果grand是其父节点的left, 则将grand.parent.left = parent;
        if (grand.isLeftChild()) { 
            grand.parent.left = parent;
        } else if (grand.isRightChild()) { 
            grand.parent.right = parent;
            // grand是根节点
        } else { 
            root = parent;
        }
    
        // 更新child的parent
        if (child != null)
            child.parent = grand;
    
        // 更新grand的parent
        grand.parent = parent;
    
        // 更新高度(因为grand、parent的左右子树都变了, 先更新grand(矮的))
        updateHeight(grand);
        updateHeight(parent);
    }

## 添加 -afterRemove(node) 函数 ##

跳转到目录

*  在节点被删除后，可能导致失衡，所以需要调用`afterRemove`函数调整失衡。

private void remove(Node<E> node) { 
        ...
        if (node是度为1的节点) {  
            ...
            // 删除节点之后的处理
            afterRemove(node);
        } else if (node是叶子节点并且是根节点) {  
            ...
            // 删除节点之后的处理
            afterRemove(node);
        } else {  
            //node是叶子节点，但不是根节点
            ...
            // 删除节点之后的处理
            afterRemove(node);
        }
    }

*  其中`updateHeight`和`rebalance`在上面已经实现了。

protected void afterRemove(Node<E> node) { 
        while ((node = node.parent) != null) { 
            if (isBalanced(node)) { 
                // 更新高度
                updateHeight(node);
            } else { 
                // 恢复平衡
                rebalance(node);
            }
        }
    }

## AVLTree的内部类AVLNode ##

跳转到目录  
`AVLTree`的静态内部类`AVLNode`继承自`BST`的静态内部类`Node`, 为什么要单独为AVLTree写一个内部类呢? 因为在普通二叉树, 不需要`height`属性来判断节点的`平衡因子`。

/** * AVLNode * <p> * 因为在普通二叉树, 不需要height属性来判断节点的平衡因子, 所以 * 定义一个AVLNode的AVLTree节点, height只用于AVLTree * * @param <E> */
    private static class AVLNode<E> extends Node<E> { 
    
        /** * 节点的高度 = 节点到叶子节点路径上节点的总数量 * 通过节点的高度, 来判断该节点是否平衡, 因为添加的肯定是叶子节点, * 所以设置叶子节点的默认高度为1 */
        int height = ONE;
    
        public AVLNode(E element, Node<E> parent) { 
            super(element, parent);
        }
    
        /** * 节点的平衡因子 * * @return 左子树高度 - 右子树高度 */
        public int balanceFactor() { 
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            return leftHeight - rightHeight;
        }
    
        public void updateHeight() { 
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            height = ONE + Math.max(leftHeight, rightHeight);
        }
    
        /** * 返回节点中左右子树中高度最高的子树 * 若左右高度相同, 则根据节点属于其父节点的左/右, 返回节点的左/右 * * @return */
        public Node<E> tallerChild() { 
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            if (leftHeight > rightHeight) return left;
            if (leftHeight < rightHeight) return right;
            return isLeftChild() ? left : right;
        }
    
        @Override
        public String toString() { 
            String parentString = "null";
            if (parent != null) { 
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }

# 五、AVLTree演变示例 #

跳转到目录  
输入数据：`13，14，15，12，11，17，16，8，9，1`

*  输入`13，14`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 20]

*  输入`15`，导致`13`不平衡，需要`左旋转`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 21]
 *  输入`12`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 22]
 *  输入`11`, 导致`13`不平衡，需要`右旋转`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 23]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 24]
 *  输入`17`，`16`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 25]
 *  那么`15，16，17`形成`RL`，需要先对`17右旋转`，然后对`15 左旋转`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 26]
 *  输入`8，9`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 27]
 *  那么`11，8，9`形成`LR`，需要先对`8左旋转`，然后对`11右旋转`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 28]
 *  输入`1`，会导致`12`不平衡。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 29]
 *  `12，9，8`形成`LL`，需要对`12右旋转`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 30]
 *  `这就是AVLTree通过旋转来达到平衡的原理。`

# 六、AVLTree总结 #

跳转到目录

*  添加
    
     *  可能会导致所有`祖先节点`都失衡。
     *  但是只要让`高度最低`的失衡节点恢复平衡，整棵树就恢复平衡（仅需`O(1)`次调整）。
 *  删除
    
     *  可能会导致`父节点`或`祖先节点`失衡（只有一个节点会失衡）。
     *  恢复平衡后，可能会导致更高层的`祖先节点`失衡（最多需要`O(logn)`次调整）。
 *  平均时间复杂度
    
     *  搜索：`O(logn)`
     *  添加：`O(logn)`，仅需`O(1)`次旋转操作。
     *  删除：`O(logn)`，最多需要`O(logn)`次旋转操作。

Leetcode 算法

*  [平衡二叉树][Link 1]

[AVLTree]: https://github.com/coderZYGui/tree-structure.git
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/169b141ad48f4dad8645eead5bd59bb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/a277348d86734725aac7709a91a07d5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/8d2cded33ae14ba2b12ec42d1171070f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/e17fd55dbfc8496c981d7d6acc65b206.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/22bf49c7390a4dfbb154bdf97f5c32fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201124163430544.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201124164627961.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201124171337813.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201124164717645.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/202011241715211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201124181411543.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20201124203429109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20201124203443128.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 13]: https://img-blog.csdnimg.cn/20201124204010731.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 14]: https://img-blog.csdnimg.cn/20201124204107710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 15]: https://img-blog.csdnimg.cn/20201124204256569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 16]: https://img-blog.csdnimg.cn/20201124204412754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 17]: https://img-blog.csdnimg.cn/20201124204701182.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 18]: https://img-blog.csdnimg.cn/20201124205121129.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 19]: https://img-blog.csdnimg.cn/2020112420511749.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[III]: https://blog.csdn.net/m0_37989980/article/details/109733385
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 20]: https://img-blog.csdnimg.cn/20201124220552785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 21]: https://img-blog.csdnimg.cn/20201124220617959.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 22]: https://img-blog.csdnimg.cn/20201124220636553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 23]: https://img-blog.csdnimg.cn/20201124220702776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 24]: https://img-blog.csdnimg.cn/20201124220708980.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 25]: https://img-blog.csdnimg.cn/2020112422072614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 26]: https://img-blog.csdnimg.cn/20201124220806718.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 27]: https://img-blog.csdnimg.cn/20201124220825608.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 28]: https://img-blog.csdnimg.cn/20201124220848369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 29]: https://img-blog.csdnimg.cn/20201124220904614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 30]: https://img-blog.csdnimg.cn/20201124220926215.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[Link 1]: https://leetcode-cn.com/problems/balanced-binary-tree/