【数据结构】平衡二叉搜索树、AVL树

清疚 2023-01-05 01:15 251阅读 0赞

### 目录 ###

*  二叉搜索树缺点分析
 *  改进二叉搜索树
 *   *  平衡（Balance）
     *  理想平衡
     *  如何改进二叉搜索树？
 *  平衡二叉搜索树（Balanced Binary Search Tree）
 *  AVL树
 *  BST 对比 AVLTree
 *  继承 BST
 *  AVL 树基础
 *   *  添加节点导致的失衡
     *   *  LL – 右旋转（单旋）
         *  RR – 左旋转（单旋）
         *  LR – 先左旋，再右旋（双旋）
         *  RL – 先右旋，再左旋（双旋）
         *  旋转之后维护的内容
         *  添加之后的修复图解
         *  添加之后的修复 - 代码实现
         *  统一所有的旋转操作
     *  删除节点导致的失衡
     *   *  LL – 右旋转（单旋）
         *  RR – 左旋转（单旋）
         *  LR – RR左旋转，LL右旋转（双旋）
         *  RL – LL右旋转，RR左旋转（双旋）
         *  删除之后的修复
     *  AVL树总结
 *  AVL树完整源码

# 二叉搜索树缺点分析 #

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

*  当 n 比较大时，两者的性能差异比较大
 *  比如 n = 1000000 时，二叉搜索树的最低高度是 20，最高高度是 1000000；

由此可见，二叉搜索树添加节点时可能会导致二叉搜索树退化成链表；  
而删除节点时也可能会导致二叉搜索树退化成链表；

有没有办法防止二叉搜索树退化成链表？  
让添加、删除、搜索的复杂度维持在 O(logn)？

# 改进二叉搜索树 #

## 平衡（Balance） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]

## 理想平衡 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]

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

首先，节点的添加、删除顺序是无法限制的，可以认为是随机的：

*  所以，改进方案是：在节点的添加、删除操作之后，想办法让二叉搜索树恢复平衡（减小树的高度）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]

如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大；

*  比如调整的次数会比较多，反而增加了时间复杂度；

总结来说，比较合理的改进方案是：

*  用尽量少的调整次数达到适度平衡即可；一棵达到适度平衡的二叉搜索树，可以称之为：平衡二叉搜索树

# 平衡二叉搜索树（Balanced Binary Search Tree） #

英文简称为：BBST

经典常见的平衡二叉搜索树有：

**- AVL树**  
Windows NT 内核中广泛使用

**- 红黑树**  
C++ STL（比如 map、set ）  
Java 的 TreeMap、TreeSet、HashMap、HashSet  
Linux 的进程调度  
Ngix 的 timer 管理

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

--------------------

# AVL树 #

AVL树是最早发明的自平衡二叉搜索树之一

AVL 取名于两位发明者的名字

*  G. M. Adelson-Velsky 和 E. M. Landis（来自苏联的科学家）

Something interesting

*  有人把AVL树念做“艾薇儿树”，加拿大女歌手，几首不错的歌：《Complicated》、《When You’re Gone》、《Innocence》

平衡因子（Balance Factor）：某结点的左右子树的高度差（左子树高度 减 右子树高度）

AVL树的特点：

*  每个节点的平衡因子只可能是 1、0、-1（绝对值 ≤ 1，如果超过 1，称之为 “失衡"）
 *  每个节点的左右子树高度差不超过1
 *  搜索、添加、删除的时间复杂度是  O ( l o g n ) O(logn) O(logn)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]

# BST 对比 AVLTree #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]

# 继承 BST #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]  
这里 AVLTree 要继承的 BST，与之前学习的 二叉搜索树 几乎一样，有点小区别；

*  在添加节点之后增加了 `afterAdd()` 用于调整平衡；
 *  在删除节点之后增加了 `afterRemove()` 用于调整平衡；

注意：BST 要继承 BinaryTree；

import java.util.Comparator;
    
    @SuppressWarnings("unchecked")
    public class BST<E> extends BinaryTree<E> {
        
        private Comparator<E> comparator;
    
        public BST() {
        
            this(null);
        }
    
        public BST(Comparator<E> comparator) {
        
            this.comparator = comparator;
        }
    
    
        // 添加元素
        public void add(E element) {
        
            elementNotNullCheck(element);
            // 添加第一个节点
            if (root == null) {
        
                //root = new Node<>(element, null);
                root = createNode(element, null);
                size++;
                afterAdd(root);// 新添加节点之后的处理
                return;
            }
            // 添加的不是第一个节点
            // 找到父节点
    
            // 假设当前节点为根节点，父节点也是跟节点
            Node<E> node = root;
            Node<E> parent = null;
            int cmp = 0; //记录最后一次比较结果
            do {
        
                cmp = compare(element, node.element); //记录最后一次比较结果
                parent = node; //记录父节点
                if (cmp > 0) {
         //插入的节点 大于 当前节点，就往当前节点的右节点走
                    node = node.right;
                } else if (cmp < 0) {
         //插入的节点 小于 当前节点，就往当前节点的左节点走
                    node = node.left;
                } else {
         // 插入的节点 等于 当前节点，就用插入节点的值替换当前节点的值
                    node.element = element;
                    return;
                }
                //当node==null退出循环，需要记录上一个节点，即父节点就是node==null之前的那个节点
            } while (node != null);
    
            // 当走到这里，说明已经退出循环，即当前节点node==null
            // 找到了要插入的位置，当前节点的位置就是要插入新节点的位置，所以用父节点指向新节点即可
            // 看看插入到父节点的哪个位置
            //Node<E> newNode = new Node<>(element, parent);
            Node<E> newNode = createNode(element, parent);
            if (cmp > 0) {
        
                parent.right = newNode;
            } else {
        
                parent.left = newNode;
            }
            size++;
            // 新添加节点之后的处理
            afterAdd(newNode);
        }
    
        // 删除元素
        public void remove(E element) {
        
            remove(getNode(element));
        }
    
        // 是否包含某元素
        public boolean contains(E element) {
        
            return getNode(element) != null;
        }
    
    
        // 删除该节点
        protected void remove(Node<E> node) {
        
            if (node == null) return;
    
            // 删除度为2的节点
            if (node.left != null && node.right != null) {
        
                // 找到该节点的前驱 或 后继节点
                Node<E> s = super.successor(node); //Node<E> s = predecessor(node);
                // 用后继节点的值覆盖度为2的节点的值
                node.element = s.element;
                // 删除后继节点（前驱、后继一定是度为0或1的节点）
                // 将node指向后继节点，删除node就相当于删除后继节点
                node = s;
            }
    
            // 删除node节点（node的度必然是1或者0）
            // child是删除的节点的子节点
            Node<E> child = node.left != null ? node.left : node.right;
    
            if (child != null) {
         // 度为1的节点
                // 更改child的parent
                child.parent = node.parent;
                // 更改parent的left、right的指向
                if (node.parent == null) {
         // node是度为1的节点并且是根节点
                    root = child;
                } else if (node == node.parent.left) {
         // node是度为1的节点，不是根节点
                    node.parent.left = child;
                } else {
         // node == node.parent.right
                    node.parent.right = child;
                }
                // 删除节点之后的处理
                afterRemove(node);
    
            } else if (node.parent == null) {
         // node是叶子节点并且是根节点
                root = null;
                // 删除节点之后的处理
                afterRemove(node);
            } else {
         // node是叶子节点，但不是根节点
                if (node == node.parent.left) {
        
                    node.parent.left = null;
                } else {
         // node == node.parent.right
                    node.parent.right = null;
                }
                // 删除节点之后的处理
                afterRemove(node);
            }
            size--; //节点个数减一
        }
    
        // 根据元素获取该节点
        private Node<E> getNode(E element) {
        
            Node<E> node = root;
            while (node != null) {
        
                // 传入的值与当前节点的值比较
                int cmp = compare(element, node.element);
                if (cmp == 0) return node; // 相等，返回当前节点
                if (cmp < 0) {
         // 往当前节点左子树找
                    node = node.left;
                } else {
         // 往当前节点右子树找
                    node = node.right;
                }
            }
            return null; // 没有找到该元素对应的节点
        }
    
        /**
         * 添加node之后的调整
         * @param node 新添加的节点
         */
        protected void afterAdd(Node<E> node) {
        
        }
    
        /**
         * 删除node之后的调整
         * @param node 被删除的节点
         */
        protected void afterRemove(Node<E> node) {
        
        }
    
        private void elementNotNullCheck(E element) {
        
            if (element == null) {
        
                throw new IllegalArgumentException("element must not be null");
            }
        }
    
        /**
         * 返回值等于0，代表e1和e2相等,
         * 返回值大于0，代表e1大于e2,
         * 返回值小于0，代表e1小于e2
         */
        private int compare(E e1, E e2) {
        
            if (this.comparator != null) {
        
                return comparator.compare(e1, e2);
            }
            // BST的节点元素必须具备可比较性
            // 如果强转失败，说明是BST的元素有问题，不具备可比较性
            return ((Comparable<E>) e1).compareTo(e2);
        }
    
    }

# AVL 树基础 #

import java.util.Comparator;
    
    
    public class AVLT<E> extends BST<E> {
        
    
        public AVLT() {
        
            this(null);
        }
    
        public AVLT(Comparator<E> comparator) {
        
            super(comparator);
        }
    
        /**
         * 重写父类中的 createNode 方法
         *
         * @return AVLNode
         */
        @Override
        protected Node<E> createNode(E element, Node<E> parent) {
        
            return new AVLNode<>(element, parent);
        }
    
        /**
         * 判断传入节点是否平衡（平衡因子的绝对值 <= 1）
         */
        private boolean isBalanced(Node<E> node) {
        
            return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
        }
    
        /**
         * 更新高度
         */
        private void updateHeight(Node<E> node) {
        
            ((AVLNode<E>) node).updateHeight();
        }
    
        /**
         * AVL树的节点，需要计算平衡因子，因此比普通二叉树多维护一个height属性，
         * 如果将height放入普通二叉树里没有用处，浪费空间，
         * 所以新建AVLNode类继承Node类，进行功能扩展
         */
        private static class AVLNode<E> extends Node<E> {
        
            // 新增的节点 必定是叶子节点，所以默认叶子节点高度是1
            int height = 1;
    
            public AVLNode(E element, Node<E> parent) {
        
                super(element, parent);
            }
    
            // 获取节点的平衡因子：某结点的左右子树的高度差（左子树高度 减 右子树高度）
            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 = 1 + Math.max(leftHeight, rightHeight);
            }
    
            // 获取当前节点中，更高的子节点（左右子树更高的那个）
            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 + ")";
            }
        }
    
    }

## 添加节点导致的失衡 ##

示例：往下面这棵子树中添加 13

*  最坏情况：可能会导致所有祖先节点都失衡
 *  父节点、非祖先节点，都不可能失衡  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]

**修复平衡的操作：**

*  LL – 右旋转（单旋）
 *  RR – 左旋转（单旋）
 *  LR – 先左旋，再右旋（双旋）
 *  RL – 先右旋，再左旋（双旋）

有些教程里面：

*  把右旋转叫做 zig，旋转之后的状态叫做 zigged
 *  把左旋转叫做 zag，旋转之后的状态叫做 zagged

### LL – 右旋转（单旋） ###

让 `p` 成为这颗子树的根节点

*  `g.left = p.right`
 *  `p.right = g`

旋转后仍然是一颗 二叉搜索树：`T0 < n < T1 < p < T2 < g < T3`

还需要注意维护的内容

*  `T2`、`p`、`g` 的 `parent` 属性
 *  先后更新 `g`、`p` 的高度（先更新高度比较低的节点，再更新较高的节点）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]

/**
     * 右旋转
     * @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);
    }

### RR – 左旋转（单旋） ###

让 `p` 成为这颗子树的根节点

*  `g.right = p.left`
 *  `p.left = g`

旋转后仍然是一颗 二叉搜索树：`T0 < g < T1 < o < T2 < n < T3`

还需要注意维护的内容

*  `T1`、`p`、`g` 的 `parent` 属性
 *  先后更新 `g`、`p` 的高度（先更新高度比较低的节点，再更新较高的节点）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]

/**
     - 左旋转
     - @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);
    }

### LR – 先左旋，再右旋（双旋） ###

LR 就是：先对 `p` 进行 左旋转-RR，再对 `g` 进行 右旋转-LL；

*  先对 `p` 左旋转：`p.right = n.left`、`n.left = p`
 *  再对 `g` 右旋转：`g.left = n.right`、`n.right = g`

旋转后仍然是一颗 二叉搜索树：`T0 < p < T1 < n < T2 < g < T3`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]

### RL – 先右旋，再左旋（双旋） ###

RL 就是：先对 `p` 进行 右旋转-LL，再对 `g` 进行 左旋转-RR；

*  先对 `p` 右旋转：`p.left = n.right`、`n.right = p`
 *  再对 `g` 左旋转：`g.right = n.left`、`n.left = g`

### 旋转之后维护的内容 ###

/**
     * 公共代码：不管是左旋转、右旋转，都要执行的
     * @param grand 失衡节点
     * @param parent 失衡节点的tallerChild
     * @param child child g和p需要交换的子树(本来是p的子树, 后面会变成g的子树)
     */
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        
        // 维护T1、g、p的parent属性
        // 先让parent成为这颗子树的根节点
        parent.parent = grand.parent;
        // 并且判断grand是左子树,还有右子树
        if (grand.isLeftChild()) {
         // grand是左子树
            grand.parent.left = parent; // 将parent成为左子树
        } else if (grand.isRightChild()) {
        
            grand.parent.right = parent; // 将parent成为右子树
        } else {
         // 既不是左子树,也不是右子树,说明grand是root节点
            root = parent; // 将parent成为根节点
        }
    
        // 更新child的parent属性
        if (child != null) {
        
            child.parent = grand;
        }
        // 更新grand的parent属性
        grand.parent = parent;
    
        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
    }

### 添加之后的修复图解 ###

输入数据：13, 14, 15, 12, 11, 17, 16, 8, 9, 1

输入13：正常  
输入14：正常  
输入15：13失衡，RR，左旋转  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 12]  
输入12：正常  
输入11：13失衡，LL，右旋转  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 13]  
输入17：正常  
输入16：15失衡，RL，先右旋转、再左旋转  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 14]  
输入8：正常  
输入9：11失衡，LR，先左旋转、再右旋转  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 15]  
输入1：12失衡，LL，右旋转  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 16]

### 添加之后的修复 - 代码实现 ###

/**
     * 增加节点后的调整
     */
    @Override
    protected void afterAdd(Node<E> node) {
        
        while ((node = node.parent) != null) {
         //能进循环说明父节点不为空
            if (isBalanced(node)) {
        
                // 更新高度
                updateHeight(node);
            } else {
        
                // 恢复平衡
                rebalance(node);
                // 整棵树恢复平衡
                // 一旦整棵树恢复平衡，就不需要再向上访问它的父节点直接break即可
                break;
            }
        }
    }

/**
     * 恢复平衡
     * rotateLeft 左旋转
     * rotateRight 右旋转
     *
     * @param grand 高度最低的那个不平衡节点
     */
    private void rebalance2(Node<E> grand) {
        
        // parent就是，grand的最高的子节点（左或右）
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        // node就是，parent的最高的子节点（左或右）
        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);
            }
        }
    
    }

### 统一所有的旋转操作 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 17]

/**
     * 统一所有旋转
     *  * @param r             当前子树的根节点
     * @param a,b,c,d,e,f,g 从小到大一次排序的节点
     */
    private void rotate(
            Node<E> r,
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g) {
        
    
        // 让d成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
        
            r.parent.left = d;
        } else if (r.isRightChild()) {
        
            r.parent.right = d;
        } else {
        
            root = d;
        }
        // a-b-c
        b.left = a;
        if (a != null) a.parent = b;
    
        b.right = c;
        if (c != null) c.parent = b;
    
        updateHeight(b);
    
        // e-f-g
        f.left = e;
        if (e != null) e.parent = f;
    
        f.right = c;
        if (g != null) g.parent = f;
    
        updateHeight(f);
    
        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }

/**
     * 恢复平衡
     * 使用rotate方法，统一所有旋转
     *  * @param grand 高度最低的那个不平衡节点
     */
    private void rebalance(Node<E> grand) {
        
        // parent就是，grand的最高的子节点（左或右）
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        // node就是，parent的最高的子节点（左或右）
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
    
        if (parent.isLeftChild()) {
         // L
            if (node.isLeftChild()) {
         // LL
                rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
            } else {
         // LR
                rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
            }
        } else {
         // R
            if (node.isLeftChild()) {
         // RL
                rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
            } else {
         // RR
                rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
            }
        }
    }

## 删除节点导致的失衡 ##

示例：删除子树中的 16

*  可能会导致父节点 或 祖先节点失衡（只有1个节点会失衡），其他节点，都不可能失衡

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 19]

### LL – 右旋转（单旋） ###

*  如果绿色节点不存在，更高层的祖先节点可能也会失衡，需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡…
 *  极端情况下，所有祖先节点都需要进行恢复平衡的操作，共  O ( l o g n ) O(logn) O(logn) 次调整  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 20]

### RR – 左旋转（单旋） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 21]

### LR – RR左旋转，LL右旋转（双旋） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 22]

### RL – LL右旋转，RR左旋转（双旋） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 23]

### 删除之后的修复 ###

/**
     - 删除节点后的调整
     */
    @Override
    protected void afterRemove(Node<E> node) {
        
        while ((node = node.parent) != null) {
         //能进循环说明父节点不为空
            if (isBalanced(node)) {
        
                // 更新高度
                updateHeight(node);
            } else {
        
                // 恢复平衡
                rebalance(node);
            }
        }
    }

## AVL树总结 ##

**添加**

*  可能会导致所有祖先节点都失衡
 *  只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡 【仅需  O ( 1 ) O(1) O(1) 次调整】

**删除**

*  可能会导致父节点 或 祖先节点失衡（只有1个节点会失衡）
 *  恢复平衡后，可能会导致更高层的祖先节点失衡 【最多需要  O ( l o g n ) O(logn) O(logn) 次调整】

**平均时间复杂度**

*  搜索： O ( l o g n ) O(logn) O(logn)
 *  添加： O ( l o g n ) O(logn) O(logn)，仅需  O ( 1 ) O(1) O(1) 次的旋转操作
 *  删除： O ( l o g n ) O(logn) O(logn)，最多需要  O ( l o g n ) O(logn) O(logn) 次的旋转操作

# AVL树完整源码 #

import java.util.Comparator;
    
    
    public class AVLT<E> extends BST<E> {
        
    
        public AVLT() {
        
            this(null);
        }
    
        public AVLT(Comparator<E> comparator) {
        
            super(comparator);
        }
    
        /**
         * 增加节点后的调整
         */
        @Override
        protected void afterAdd(Node<E> node) {
        
            while ((node = node.parent) != null) {
         //能进循环说明父节点不为空
                if (isBalanced(node)) {
        
                    // 更新高度
                    updateHeight(node);
                } else {
        
                    // 恢复平衡
                    rebalance(node);
                    // 整棵树恢复平衡
                    // 一旦整棵树恢复平衡，就不需要再向上访问它的父节点直接break即可
                    break;
                }
            }
        }
    
        /**
         * 删除节点后的调整
         */
        @Override
        protected void afterRemove(Node<E> node) {
        
            while ((node = node.parent) != null) {
         //能进循环说明父节点不为空
                if (isBalanced(node)) {
        
                    // 更新高度
                    updateHeight(node);
                } else {
        
                    // 恢复平衡
                    rebalance(node);
                }
            }
        }
    
        /**
         * 恢复平衡
         * 使用rotate方法，统一所有旋转
         *
         * @param grand 高度最低的那个不平衡节点
         */
        private void rebalance(Node<E> grand) {
        
            // parent就是，grand的最高的子节点（左或右）
            Node<E> parent = ((AVLNode<E>) grand).tallerChild();
            // node就是，parent的最高的子节点（左或右）
            Node<E> node = ((AVLNode<E>) parent).tallerChild();
    
            if (parent.isLeftChild()) {
         // L
                if (node.isLeftChild()) {
         // LL
                    rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
                } else {
         // LR
                    rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
                }
            } else {
         // R
                if (node.isLeftChild()) {
         // RL
                    rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
                } else {
         // RR
                    rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
                }
            }
        }
    
        /**
         * 恢复平衡
         * rotateLeft 左旋转
         * rotateRight 右旋转
         *
         * @param grand 高度最低的那个不平衡节点
         */
        private void rebalance2(Node<E> grand) {
        
            // parent就是，grand的最高的子节点（左或右）
            Node<E> parent = ((AVLNode<E>) grand).tallerChild();
            // node就是，parent的最高的子节点（左或右）
            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);
                }
            }
    
        }
    
        /**
         * 统一所有旋转
         *
         * @param r             当前子树的根节点
         * @param a,b,c,d,e,f,g 从小到大一次排序的节点
         */
        private void rotate(
                Node<E> r,
                Node<E> a, Node<E> b, Node<E> c,
                Node<E> d,
                Node<E> e, Node<E> f, Node<E> g) {
        
    
            // 让d成为这棵子树的根节点
            d.parent = r.parent;
            if (r.isLeftChild()) {
        
                r.parent.left = d;
            } else if (r.isRightChild()) {
        
                r.parent.right = d;
            } else {
        
                root = d;
            }
            // a-b-c
            b.left = a;
            if (a != null) a.parent = b;
    
            b.right = c;
            if (c != null) c.parent = b;
    
            updateHeight(b);
    
            // e-f-g
            f.left = e;
            if (e != null) e.parent = f;
    
            f.right = c;
            if (g != null) g.parent = f;
    
            updateHeight(f);
    
            // b-d-f
            d.left = b;
            d.right = f;
            b.parent = d;
            f.parent = d;
            updateHeight(d);
        }
    
    
        /**
         * 左旋转
         * @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);
        }
    
        /**
         * 右旋转
         * @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);
        }
    
        /**
         * 公共代码：不管是左旋转、右旋转，都要执行的
         * @param grand 失衡节点
         * @param parent 失衡节点的tallerChild
         * @param child child g和p需要交换的子树(本来是p的子树, 后面会变成g的子树)
         */
        private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        
            // 维护T1、g、p的parent属性
            // 先让parent成为这颗子树的根节点
            parent.parent = grand.parent;
            // 并且判断grand是左子树,还有右子树
            if (grand.isLeftChild()) {
         // grand是左子树
                grand.parent.left = parent; // 将parent成为左子树
            } else if (grand.isRightChild()) {
        
                grand.parent.right = parent; // 将parent成为右子树
            } else {
         // 既不是左子树,也不是右子树,说明grand是root节点
                root = parent; // 将parent成为根节点
            }
    
            // 更新child的parent属性
            if (child != null) {
        
                child.parent = grand;
            }
            // 更新grand的parent属性
            grand.parent = parent;
    
            // 更新高度
            updateHeight(grand);
            updateHeight(parent);
        }
    
        /**
         * 重写父类中的 createNode 方法
         *
         * @return AVLNode
         */
        @Override
        protected Node<E> createNode(E element, Node<E> parent) {
        
            return new AVLNode<>(element, parent);
        }
    
        /**
         * 判断传入节点是否平衡（平衡因子的绝对值 <= 1）
         */
        private boolean isBalanced(Node<E> node) {
        
            return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
        }
    
        /**
         * 更新高度
         */
        private void updateHeight(Node<E> node) {
        
            ((AVLNode<E>) node).updateHeight();
        }
    
    
        /**
         * AVL树的节点，需要计算平衡因子，因此比普通二叉树多维护一个height属性，
         * 如果将height放入普通二叉树里没有用处，浪费空间，
         * 所以新建AVLNode类继承Node类，进行功能扩展
         */
        private static class AVLNode<E> extends Node<E> {
        
            // 新增的节点 必定是叶子节点，所以默认叶子节点高度是1
            int height = 1;
    
            public AVLNode(E element, Node<E> parent) {
        
                super(element, parent);
            }
    
            // 获取节点的平衡因子：某结点的左右子树的高度差（左子树高度 减 右子树高度）
            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 = 1 + Math.max(leftHeight, rightHeight);
            }
    
            // 获取当前节点中，更高的子节点（左右子树更高的那个）
            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 + ")";
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221119/8f4ccd0fdf07443bbfcfb9c579a43f86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210111101809355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210111102125882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210111102457412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210111110622793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2021011111082618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210111111025749.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210111155424674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20210111162134819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20210112113307819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2021011211444628.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20210112114828432.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20210112135011406.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20210112135138764.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20210112135447194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20210112135616618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20210112140033675.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20210112141924212.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 18]: https://img-blog.csdnimg.cn/20210112150057196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 19]: https://img-blog.csdnimg.cn/20210112150028341.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 20]: https://img-blog.csdnimg.cn/20210112150935825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 21]: https://img-blog.csdnimg.cn/20210112151154120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 22]: https://img-blog.csdnimg.cn/20210112151506624.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 23]: https://img-blog.csdnimg.cn/20210112151613963.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1,size_16,color_FFFFFF,t_70