Version: Next

平衡二叉搜索树

二叉搜索树的复杂度分析

方法	复杂度
添加二分搜索	O(树高) = O(logn)
删除二分搜索	O(树高) = O(logn)
搜索二分搜索	O(树高) = O(logn)

info

极端情况：

如果树上节点除了根节点以外，全部为左节点或全部为右节点，则树退化为线性表，那么搜索的复杂度上升为O(n)

应当采取一种办法，防止二叉搜索树退化为线性表，让添加、删除、搜索的时间复杂度维持在O(logn)水平

平衡（Balance）

当节点的数量固定时，左右子树高度越接近，则称这颗二叉树越平衡，也即树高度越低

理想平衡

最理想的平衡，就是像完全二叉树、满二叉树那样，树高度尽可能的小

平衡二叉搜索树

改进二叉搜素数

节点的添加、删除顺序是无法限制的，可以认为是随机的
故，在节点添加、删除操作之后，想办法让二叉搜索树恢复平衡，即减少树高度

问题

继续采用这种方式调整节点的位置，可以完全达到理想平衡，但付出的算力代价比较大
若调整次数过多，可能反而增加了时间复杂度
故，通常使用尽量少的调整次数，达到适度的平衡即可
一颗达到适度平衡的二叉搜索树，称为平衡二叉搜索树（Balanced Binary Search Tree）BBST

经典常见的平衡二叉树有
- AVL树——广泛应用于Windows NT内核中
- 红黑树
  - C++ STL库中的map、set等
  - Java中的TreeMap、TreeSet、HashMap、HashSet
  - Linux的进程调度
  - Nginx的timer管理
- 一般也称作：自平衡二叉搜索树（Self-Balancing Binary Search Tree）

AVL树

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

AVL取名子两名发明者的名字
- G. M. Adelson-Velsky和 E. M. Landis

平衡因子（Balance Factor）：某节点的左右子树的高度差，左h - 右h
为了计算平衡因子，需要在树节点类Node<E>中添加高度height属性

AVL树的特点
- 每个节点的平衡因子只可能是1、0、-1（绝对值≤1，如果超过1，称为失衡）
- 即每个节点的左右子树高度差不超过1
- 添加、删除、搜索操作的时间复杂度维持在O(logn)

添加导致的失衡

新添加13节点，导致14节点失衡，继而导致15节点失衡，再导致9节点失衡，接着9节点的父节点也会失衡
最坏情况：可能导致所有祖先节点（不包括父节点）都失衡
父节点、非祖先节点，不可能失衡

旋转

LL——右旋转（单旋）

n：node 节点
p：parent 父节点
g：grand parent 祖父节点
T0 ~ T3：子树

在节点n添加一颗子树
则，节点g发生失衡
由于n是g节点的left又left，所以称为LL
将节点g通过单次右旋转，可以恢复平衡

右旋转
g.left = p.right
p.right = g
令p成为这棵子树的根节点

最终：

仍然是一棵二叉搜索树：T0 < n < T1 < p < T2 < g < T3

还需要维护的内容——父节点

p的父节点变为原先g的父节点
g的父节点变为p
T2的父节点由p变为g

还需要维护的内容——节点高度

先后更新g、p节点的高度

RR——左旋转（单旋）

g.right = p.left
p.left = g
让p成为这颗子树的根节点

T1、p、g的父节点进行更新
先后更新g、p节点的高度

LR —— RR左旋转、LL右旋转（双旋）

先对p进行左旋转
再对g进行右旋转
让节点n称为子树的根节点

注意

注意维护节点的父节点、高度属性

RL —— LL右旋转、RR左旋转（双旋）

先对p进行右旋转
再对g进行左旋转
令节点n变为子树根节点

注意

注意维护节点的父节点、高度属性

平衡时机——适时调用afterAdd方法

在添加操作执行完时，进行平衡操作

修改MyBinarySearchTree，在其中添加afterAdd(Node<E> node)方法，什么也不写，延迟到子类中实现
修改MyBinarySearchTree中的add方法，在其中添加对afterAdd方法的调用

afterAdd方法，修改add方法

protected void afterAdd(Node<E> node) {
    // 外部不能访问，子类可以访问
}

public void add(E element) {
    // 非空判断
    elementNotNullCheck(element);

    // 判断根节点是否存在
    if (this.rootNode == null) {
        this.rootNode = new Node<>(element, null);
        size++;
        afterAdd(rootNode); // 平衡
        return;
    }

    // 根节点已经存在
    // 1. 找到父节点
    Node<E> currentNode = rootNode; // 当前正在比较的树节点
    Node<E> parentNode = null; // 记录当前节点的父节点
    int compareResult = 0; // 比较大小的结果
    // 一直往下找
    while (currentNode != null) {
        compareResult = compare(element, currentNode.element); // 比较大小
        // 在currentNode向下迭代之前，先记录它，等current迭代之后，这个记录值就成了current的parent
        parentNode = currentNode;

        if (compareResult < 0) { // element < 当前节点
            // 找左节点
            currentNode = currentNode.leftNode;
        } else if (compareResult > 0) { // element > 当前节点
            // 找右节点
            currentNode = currentNode.rightNode;
        } else { // 相等 覆盖旧节点
            currentNode.element = element;
            return;
        }
    }
    // 跳出循环，已经走到了树的叶子节点，此时currentNode一定指向null，parent就是current的爸爸
    // 2. 创建新节点
    Node<E> newNode = new Node<>(element, parentNode);
    // 3. parent.left 或 parent.right指向创建的节点
    if (compareResult > 0) // 插入到父节点的右
        parentNode.rightNode = newNode;
    else // 插入到父节点的左
        parentNode.leftNode = newNode;

    size++;
    afterAdd(newNode); // 平衡
}

计算平衡因子

为了计算平衡因子，需要维护节点的高度属性，但该属性定义在普通的二叉树节点类中不合适，因为它不具有足够的普遍性
在AVL树的类中定义一个AVLNode类，继承二叉树的节点类，添加height属性，默认等于1
向AVL树中添加节点时，添加进去的新节点必定是叶子节点，而叶子节点的高度就是1
在AVL节点类中添加计算平衡因子的方法getBalanceFactor
在AVL树类中添加私有方法isBalanced(Node<E> node)，返回节点是否平衡
在BinarySearchTree类中，添加creatNode(E element, Node<E> parentNode)方法，供子类添加节点使用

AVLNode<E>，添加高度属性，计算平衡因子

/**
 * AVL树节点
 */
private static class AVLNode<E> extends Node<E> {
    int height = 1; // 添加的一定是叶子节点，叶子节点的高度就是1

    public AVLNode(E element, Node<E> parentNode) {
        super(element, parentNode);
    }

    /**
     * 获取某节点平衡因子
     * e
     *
     * @return 计算出的平衡因子
     */
    public int getBalanceFactor() { // 左子树高度 - 右子树高度
        int leftHeight = leftNode == null ? 0 : ((AVLNode<E>) leftNode).height;
        int rightHeight = rightNode == null ? 0 : ((AVLNode<E>) rightNode).height;
        return leftHeight - rightHeight;
    }
  
    public void updateHeight() {
      int leftHeight = leftNode == null ? 0 : ((AVLNode<E>) leftNode).height;
      int rightHeight = rightNode == null ? 0 : ((AVLNode<E>) rightNode).height;
      height = Math.max(leftHeight, rightHeight) + 1;
    }
}

传入节点，判断节点是否平衡

private boolean isBalanced(Node<E> node) {
    // 强制类型转换，绝对值小于等于1则平衡
    return Math.abs(((AVLNode<E>) node).getBalanceFactor()) <= 1; 
}

创建节点方法，给出默认实现，子类如AVL树类，可以重写创建AVL树节点

protected Node<E> createNode(E element, Node<E> parentNode) {
    return new Node<E>(element, parentNode);
}

AVL类，重写创建节点的方法，创建的节点从通用Node更换为AVLNode

@Override
protected Node<E> createNode(E element, Node<E> parentNode) {
    return new AVLNode<>(element, parentNode);
}

afterAdd方法

先搭建一个基本框架
添加新节点后，判断插入新节点的祖父节点是否平衡
平衡：维护节点高度（插入节点的所有父辈节点的高度）
失衡：尝试平衡
从叶子节点出发，找到最先失衡的节点（有可能添加后不失衡，那么会一路找到根节点）

afterAdd方法基本框架

@Override
protected void afterAdd(Node<E> newNode) {
    while ((newNode = newNode.parentNode) != null) {
        if (isBalanced(newNode)) { // 若节点平衡
           
        } else { // 若节点失衡

        }
    }
}

维护节点高度

维护高度：
高度 = max(左子树高度，右子树高度) + 1

之前在AVL节点类中，定义了维护节点高度的方法

public void updateHeight() {
    int leftHeight = leftNode == null ? 0 : ((AVLNode<E>) leftNode).height;
    int rightHeight = rightNode == null ? 0 : ((AVLNode<E>) rightNode).height;
    height = Math.max(leftHeight, rightHeight) + 1;
}

updateHeight(Node<E> node)方法，用于维护节点高度

/**
 * 维护高度
 */
private void updateHeight(Node<E> node) {
    ((AVLNode<E>) node).updateHeight();
}

平衡操作

到达这个位置的节点，可以认为是旋转操作中的g
找到p和n
p：g的左右子树中，高度最高的那个节点
n：p的左右子树中，高度最高的那个节点

判断某节点时其父节点的左子节点还是右子节点

public boolean isLeftChild() {
    return parentNode != null && this == parentNode.leftNode;
}

public boolean isRightChild() {
    return parentNode != null && this == parentNode.rightNode;
}

tallerChild方法，返回某节点左右子树中高度最高的节点

public AVLNode<E> tallerChild() {
    int leftHeight = leftNode == null ? 0 : ((AVLNode<E>) leftNode).height;
    int rightHeight = rightNode == null ? 0 : ((AVLNode<E>) rightNode).height;

    if (leftHeight > rightHeight)
        return (AVLNode<E>) leftNode;
    if (leftHeight < rightHeight)
        return (AVLNode<E>) rightNode;
    // 左右子树高度相等，返回同方向节点
    // 当前节点时父节点的左子节点，就返回当前节点的左子节点
    // 当前节点时父节点的右子节点，就返回当前节点的右子节点
    return isLeftChild() ? (AVLNode<E>) leftNode : (AVLNode<E>) rightNode;
}

判断旋转类型
LL——对g进行右旋
RR——对g进行左旋
LR——对p进行左旋，g进行右旋
RL——对p进行右旋，g进行左旋

在AVL中，重写二叉搜索树中定义的afterAdd方法，实现平衡操作

/**
 * 平衡
 *
 * @param grandParentNode 高度最低的不平衡节点
 */
private void rebalance(Node<E> grandParentNode) {
    AVLNode<E> g = (AVLNode<E>) grandParentNode; // aka grandParentNode
    AVLNode<E> p = g.tallerChild(); // aka parentNode
    AVLNode<E> n = p.tallerChild(); // aka current new insert node

    if (p.isLeftChild()) { // 左L
        if (n.isLeftChild()) { // 左左LL
            rotateRight(g);
        } else { // 左右LR
            rotateLeft(p);
            rotateRight(g);
        }
    } else { // 右R
        if (n.isLeftChild()) { // 右左RL
            rotateRight(p);
            rotateLeft(g);
        } else { // 右右RR
            rotateLeft(g);
        }
    }
}

平衡操作1——分离式旋转实现

维护节点左右关系
维护节点父节点
维护节点高度

左旋

当前节点的右子树指向右子节点的左子树（g.right = p.left）
子节点的左子树指向当前节点 （p.left = g）
让子节点成为这颗子树的根节点 (p成为子树根节点)
维护相关节点的父节点——T1、p、g的parent属性
维护相关节点的高度——先后更新g、p的高度

左旋

//旋转
private void rotateLeft(AVLNode<E> g) { // 可认为是g
    AVLNode<E> p = (AVLNode<E>) g.rightNode; // aka p
    g.rightNode = p.leftNode; // 1.
    p.leftNode = g; // 2.
    // 3. p 称为子树根节点
    if (g.isLeftChild())
        g.parentNode.leftNode = p;
    else if (g.isRightChild())
        g.parentNode.rightNode = p;
    else // 不是左也不是右，说明g.parentNode不存在，g是根节点，则p不是成为子树根节点
        rootNode = p;// 而是成为整棵树的根节点

    // 维护相关节点的父节点——`T1`、`p`、`g`的`parent`属性
    p.parentNode = g.parentNode;
    g.parentNode = p; // aka g.parent = p
    if (g.rightNode != null) // 防止空指针异常
        g.rightNode.parentNode = g;
    // 维护相关节点的高度——先后更新`g`、`p`的高度
    g.updateHeight(); // 先更新高度低的
    p.updateHeight(); // 再更新高度高的，因为高度高的会调用低节点高度来计算自己的高度
}

右旋

// 右旋转
private void rotateRight(AVLNode<E> g) {
    AVLNode<E> p = (AVLNode<E>) g.leftNode;
    g.leftNode = p.rightNode;
    p.rightNode = g;
    // p 成为子树根节点
    if (g.isLeftChild())
        g.parentNode.leftNode = p;
    else if (g.isRightChild())
        g.parentNode.rightNode = p;
    else
        rootNode = p; // p成为整棵树的根节点
    // 维护父节点 T2、g、p
    p.parentNode = g.parentNode;
    g.parentNode = p;
    if (g.leftNode != null)// aka t2
        g.leftNode.parentNode = g;
    // 维护节点高度
    g.updateHeight();
    p.updateHeight();
}

抽离旋转公共代码

info

观察可以发现，左旋和右旋后半部分代码完全一致，我们可以将公共部分抽离成一个新方法afterRotate

afterRotate

private void afterRotate(AVLNode<E> g, AVLNode<E> p, AVLNode<E> child) {
    // p 成为子树根节点
    if (g.isLeftChild())
        g.parentNode.leftNode = p;
    else if (g.isRightChild())
        g.parentNode.rightNode = p;
    else
        rootNode = p; // p成为整棵树的根节点
    // 维护父节点 T2、g、p
    p.parentNode = g.parentNode;
    g.parentNode = p;
    if (child != null)// aka t2
        child.parentNode = g;
    // 维护节点高度
    g.updateHeight();
    p.updateHeight();
}

重构后的左右旋转

//旋转
private void rotateLeft(AVLNode<E> g) { // 可认为是g
    AVLNode<E> p = (AVLNode<E>) g.rightNode; // aka p
//        g.rightNode = p.leftNode; // 1.
    AVLNode<E> child = (AVLNode<E>) p.leftNode;
    g.rightNode = child; // 1.
    p.leftNode = g; // 2.
    afterRotate(g, p, child);
}

// 右旋转
private void rotateRight(AVLNode<E> g) {
    AVLNode<E> p = (AVLNode<E>) g.leftNode;
//        g.leftNode = p.rightNode;
    AVLNode<E> child = (AVLNode<E>) p.rightNode;
    g.leftNode = child;
    p.rightNode = g;
    afterRotate(g, p, child);
}

测试

向bst和avl中添加同样的元素，观察树结构的区别

private static void basicTest() {
    Integer[] data = new Integer[]{
            85, 19, 69, 3, 7, 99, 95, 2, 1, 70, 44, 58, 11, 21, 14, 93, 57, 4, 56
    };

    MyBinarySearchTree<Integer> bst = new MyBinarySearchTree<>();
    MyAVL<Integer> avl = new MyAVL<>();
    // 添加
    for (Integer d : data) {
        avl.add(d);
        bst.add(d);
    }

    BinaryTrees.println(bst);
    System.out.println("---------------");
    BinaryTrees.println(avl);
}

运行结果

            ┌────────85────────┐
            │                  │
    ┌──────19──────┐         ┌─99
    │              │         │
  ┌─3─┐          ┌─69─┐   ┌─95
  │   │          │    │   │
┌─2 ┌─7─┐     ┌─44─┐  70 93
│   │   │     │    │
1   4   11─┐ 21  ┌─58
           │     │
           14 ┌─57
              │
             56
----------------------------------------------
    ┌────────19────────┐
    │                  │
  ┌─7─┐         ┌──────69─────┐
  │   │         │             │
┌─2─┐ 11─┐   ┌─44─┐         ┌─95─┐
│   │    │   │    │         │    │
1   3─┐  14 21  ┌─57─┐   ┌─85─┐  99
      │         │    │   │    │
      4        56    58 70    93

Process finished with exit code 0

平衡操作2——统一式旋转操作

观察规律
a、b、c、d、e、f、g按从小到大排布，符合二叉搜索树的顺序
平衡后的结果，结构是高度一致的
a、b、c 会构成一棵独立左子树
e、f、g 会构成一棵独立右子树
d 成为子树根节点
存在不区分LL、LR、RL、RR的统一实现旋转方法

实现思路
找到a、b、c、d、e、f、g节点
确定原先子树的根节点，让d的父节点指向原先子树根节点的父节点；
根据原先子树根节点，是其父节点的左子节点还是右子节点，将d放置在父节点对应的左子节点或右子节点位置上；如果父节点不存在，则d成为整棵二叉树的根节点

统一旋转方法

/**
 * 统一式旋转
 *
 * @param a       ~ g 按从小到大排列的二叉搜索树节点
 * @param oldRoot 原先子树的根节点
 */
private void uniRotate(AVLNode<E> a, AVLNode<E> b, AVLNode<E> c, // 结果左子树
                       AVLNode<E> d, // 结果子树根节点
                       AVLNode<E> e, AVLNode<E> f, AVLNode<E> g,  // 结果右子树
                       AVLNode<E> oldRoot) {
    d.parentNode = oldRoot.parentNode; // 新子树根节点的父节点为旧子树根节点的父节点
    // 令d成为新子树的根节点
    if (oldRoot.isLeftChild())
        oldRoot.parentNode.leftNode = d;
    else if (oldRoot.isRightChild())
        oldRoot.parentNode.rightNode = d;
    else
        rootNode = d; // 成为整棵树的根节点

    // 处理 a、b、c 独立子树
    b.leftNode = a;
    b.rightNode = c;
    if (a != null) a.parentNode = b;
    if (c != null) c.parentNode = b;
    b.updateHeight(); // 因为b的左右子树都发生了变化，因此需要更新b的高度

    // 处理 e、f、g 独立子树
    f.leftNode = e;
    f.rightNode = g;
    if (e != null) e.parentNode = f;
    if (g != null) g.parentNode = f;
    f.updateHeight(); // 因为f的左右子树都发生了变化，因此需要更新f的高度

    // 处理b、d、f
    d.leftNode = b;
    d.rightNode = f;
    b.parentNode = d;
    f.parentNode = d;
    d.updateHeight();
}

基于统一旋转的平衡方法

/**
 * 统一式平衡
 */
private void rebalance2(Node<E> grandParentNode) {
    AVLNode<E> g = (AVLNode<E>) grandParentNode; // aka grandParentNode
    AVLNode<E> p = g.tallerChild(); // aka parentNode
    AVLNode<E> n = p.tallerChild(); // aka current new insert node

    if (p.isLeftChild()) { // 左L
        if (n.isLeftChild()) { // 左左LL
            uniRotate((AVLNode<E>) n.leftNode,
                    n,
                    (AVLNode<E>) n.rightNode,
                    p,
                    (AVLNode<E>) p.rightNode,
                    g,
                    (AVLNode<E>) g.rightNode,
                    g);
        } else { // 左右LR
            uniRotate((AVLNode<E>) p.leftNode,
                    p,
                    (AVLNode<E>) n.leftNode,
                    n,
                    (AVLNode<E>) n.rightNode,
                    g,
                    (AVLNode<E>) g.rightNode,
                    g);
        }
    } else { // 右R
        if (n.isLeftChild()) { // 右左RL
            uniRotate((AVLNode<E>) g.leftNode,
                    g,
                    (AVLNode<E>) n.leftNode,
                    n,
                    (AVLNode<E>) n.rightNode,
                    p,
                    (AVLNode<E>) p.rightNode,
                    g);
        } else { // 右右RR
            uniRotate((AVLNode<E>) g.leftNode,
                    g,
                    (AVLNode<E>) p.leftNode,
                    p,
                    (AVLNode<E>) n.leftNode,
                    n,
                    (AVLNode<E>) n.rightNode,
                    g);
        }
    }
}

删除导致的失衡

删除树中的节点16
会导致父节点或者祖先节点失衡
只会导致1个节点失衡

LL左旋

旋转结束后，整棵子树的高度是否发生变化，取决于绿色子树是否存在，即取决于T2子树的具体高度
如果绿色节点不存在，更高层的祖先节点可能也会失衡，需要再次恢复平衡，之后有可能导致更高层的祖先节点失衡
极端情况下，所有祖先节点，直到根节点，都需要进行恢复平衡操作，共O(logn)次调整

RR右旋

LR 左旋——右旋

RL 右旋——左旋

afterRemove方法

在二叉搜索树类中，添加aftetRemove方法，延迟到子类实现

protected void afterRemove(Node<E> node) {
    
}

在二叉搜索树remove方法中，添加对afterRemove的调用

/**
 * 删除指定节点
 *
 * @param node 要删除的节点
 */
private void remove(Node<E> node) {
    if (node == null) return;
    // 3. 删除度为2的节点
    if (node.hasTwoChildren()) { // 度为2
        // 找到前驱节点
        Node<E> predecessor = predecessor(node);
        // 前驱节点的值覆盖到要删除节点
        node.element = predecessor.element;
        // 删除前驱节点，先让引用node指向前驱节点predecessor
        // 之后再删除node即可
        node = predecessor;
    }

    // 删除node节点，node度必然为0或1
    // 找到子节点
    Node<E> replacementNode = node.leftNode != null ? node.leftNode : node.rightNode;
    // 2. 删除度为1的节点
    if (replacementNode != null) {
        replacementNode.parentNode = node.parentNode; // 更改parent
        // 更改node.parent的左或右子节点
        if (node.parentNode == null) { // node为度为1 的 根 节点
            // 根节点指向replacement
            rootNode = replacementNode;
        } else if (node == node.parentNode.leftNode)
            node.parentNode.leftNode = replacementNode;
        else
            node.parentNode.rightNode = replacementNode;

        // afterRemove 删除平衡
        afterRemove(node);
    } else if (node.parentNode == rootNode) { // 是根节点的叶子节点
        rootNode = null;
        // afterRemove 删除平衡
        afterRemove(node);
    } else { // 1. 删除叶子节点 度为0, 但不是根节点
        if (node.parentNode.rightNode == node)
            node.parentNode.rightNode = null;
        else
            node.parentNode.leftNode = null;
        // afterRemove 删除平衡
        afterRemove(node);
    }

    size--;
}

在AVL类中，重写adterRemove方法

afterRemove

@Override
protected void afterRemove(Node<E> deleteNode) {
    // 从被删除节点出发，向上找到第一个失衡节点
    while ((deleteNode = deleteNode.parentNode) != null) {
        if (isBalanced(deleteNode)) { // 若节点平衡
            updateHeight(deleteNode); // 维护节点高度
        } else { // 若节点失衡
            rebalance(deleteNode); // aka node `G`
        }
    }
}

测试

测试代码：移除99，触发右旋

private static void removeTest() {
    Integer[] data = new Integer[]{
            85, 19, 69, 3, 7, 99, 95, 84
    };

    MyAVL<Integer> avl = new MyAVL<>();
    // 添加
    for (Integer d : data) {
        avl.add(d);
    }

    BinaryTrees.println(avl);
    System.out.println("---------------");

    avl.remove(99);
    BinaryTrees.println(avl);
}

运行结果

  ┌────69───┐
  │         │
┌─7─┐     ┌─95─┐
│   │     │    │
3   19 ┌─85    99
       │
      84
---------------
  ┌───69──┐
  │       │
┌─7─┐   ┌─85─┐
│   │   │    │
3   19 84    95

平均时间复杂度

搜索：O(logn)
添加：O(logn)，仅需O(1)次旋转操作
删除：O(logn)，最多需要O(logn)次旋转操作

平衡二叉搜索树#

info

平衡（Balance）#

理想平衡#

平衡二叉搜索树#

问题

AVL树#

添加导致的失衡#

旋转#

LL——右旋转（单旋）#

还需要维护的内容——父节点

还需要维护的内容——节点高度

RR——左旋转（单旋）#

LR —— RR左旋转、LL右旋转（双旋）#

注意

RL —— LL右旋转、RR左旋转（双旋）#

注意

平衡时机——适时调用afterAdd方法#

计算平衡因子#

afterAdd方法#

维护节点高度#

平衡操作#

平衡操作1——分离式旋转实现#

左旋#

右旋#

抽离旋转公共代码#

info

测试#

平衡操作2——统一式旋转操作#

删除导致的失衡#

LL左旋#

RR右旋#

LR 左旋——右旋#

RL 右旋——左旋#

afterRemove方法#

测试#

平均时间复杂度#

平衡二叉搜索树

平衡（Balance）

理想平衡

平衡二叉搜索树

AVL树

添加导致的失衡

旋转

LL——右旋转（单旋）

RR——左旋转（单旋）

LR —— RR左旋转、LL右旋转（双旋）

RL —— LL右旋转、RR左旋转（双旋）

平衡时机——适时调用afterAdd方法

计算平衡因子

afterAdd方法

维护节点高度

平衡操作

平衡操作1——分离式旋转实现

左旋

右旋

抽离旋转公共代码

测试

平衡操作2——统一式旋转操作

删除导致的失衡

LL左旋

RR右旋

LR 左旋——右旋

RL 右旋——左旋

afterRemove方法

测试

平均时间复杂度