数据结构 AVL树

基本概念

普通的二叉搜索树的缺陷

对于普通的二叉搜索树，如果添加元素时，恰好按照元素的大小顺序进行添加，那么二叉搜索树就会退化为链表，同样的，删除元素时也可能导致二叉搜索树的退化，此时 BST 的添加、删除、查找的时间复杂度将上升至 $ O(N) $，例如对于如下 BST

BST退化1

删除 2，8，9，11 节点将导致 BST 的退化

BST退化2

平衡

如何防止二叉搜索树退化成链表？让添加、删除、搜索的复杂度维持在 $ O(logn) $？这里提出平衡的概念，对于一棵二叉树，当节点总数固定时，左右子树的高度越接近，那么这棵树就越平衡，树的高度就越低

二叉树的平衡

最理想的平衡，就是想完全二叉树一样，树的高度达到最小

改进 BST

首先，作为数据结构的设计者，我们是无法规定用户以什么样的顺序添加或删除元素，可以认为这是一个随机的过程，所以一个改进方案就是在完成某个节点的添加或删除操作后，想办法让 BST 趋于平衡，即尽量降低树的高度，但是如果让树恢复到完全平衡，可能需要耗费很多性能，反而增加的事件复杂度，所以，合理的改进方案是用尽量少的调整次数达到适度平衡即可

平衡二叉搜索树 Balanced Binary Search Tree

BBST 是在 BST 的基础上的改进，有时也称它们为自平衡二叉搜索树（Self-balancing Binary Search Tree），常见的平衡二叉搜索树有

  1. AVL 树，在Windows NT 内核中广泛使用
  2. 红黑树，JDK 的 TreeMap、TreeSet、HashMap、HashSet 中都有使用

AVL 树

AVL 树是最早发明的平衡二叉搜索树之一，其名字来自发明者的名字，首先引入平衡因子的概念

平衡因子

平衡因子是指树中某节点的左右子树的高度差

AVL 树的特点

  • AVL 树的每个节点的平衡因子只可能是 -1、0、1（绝对值 ≤ 1，如果超过 1，称之为 “失衡”），即每个节点的左右子树高度差不超过 1
  • 查找，添加，删除的时间复杂度是 $ O(logn) $

例如左边的树不是 AVL 树，而右边的树每个节点的平衡因子绝对值都小于等于1，因此是一棵 AVL 树

AVL树

失衡与恢复平衡

添加导致失衡

AVL添加导致失衡

  • 最坏的情况下，添加一个节点可能导致其所有祖先节点（除了父节点）（14，15，9）都失衡
  • 但是其父节点（12）和所有非祖先节点（4，6，8）都不可能失衡
  • 我们可以将不同的失衡情况总结抽象为四种：LL、RR、LR、RL

LL 失衡-右旋转

如下图，是一棵 AVL 树的局部（g 并不是整棵树的根节点），n 代表某个节点，p 代表 parent，g 代表 grandparent，T0、T1、T2、T3 都是抽象出来的子树，长度就代表高度，假设添加新节点之前树是平衡的，也就是说所有子树的高度差都不超过 1

AVLLL1

如果此时在 n 节点的左子树 T0 或者右子树 T1 中添加一个节点，也就是 g.left.left （LL）节点的子树中，那么节点 g 就会失去平衡（导致 g 失衡的原因是 LL）

AVLLL2

对于 LL，只需要一次右旋转即可恢复平衡

AVL右旋转

具体过程为

  • g.left = p.right，即 g 的左指针指向 p 的右子树
  • p.right = g，即 p 的右指针指向 p
  • 同时维护好 T2、p 和 g的 parent 属性
  • 先后更新 g 和 p的高度属性（p 的高度需要 g 的高度）
  • 最终 p 成为这棵（局部）子树的根节点

注意

  • 右旋之后，这棵（局部）子树仍然是一棵二叉搜索树：T0 < n < T1 < p < T2 < g < T3
  • 这棵（局部）子树达到平衡，所有子树都回到红线之上

RR 失衡-左旋转

如下图，n 节点是 g.right.right（RR），如果此时向 n 节点的左或右子树中添加一个节点，那么节点 g 就会失去平衡（导致 g 失衡的原因是 RR）

AVLRR1

对于 RR，只需要一次右旋转即可恢复平衡

AVL左旋转

具体过程为

  • g.right = p.left，即 g 的右指针指向 p 的左子树
  • p.left = g，即 p 的左指针指向 p
  • 同时维护好 T1、p 和 g的 parent 属性
  • 先后更新 g 和 p的高度属性
  • 最终 p 成为这棵（局部）子树的根节点

注意

  • 左旋之后，这棵（局部）子树仍然是一棵二叉搜索树：T0 < g < T1 < p < T2 < n < T3
  • 这棵（局部）子树达到平衡，所有子树都回到红线之上

LR 失衡-左旋转+右旋转

考虑这样一种情况：导致节点 g 失衡的原因是其 left.right （LR）节点添加了节点，这时需要先对 p 节点进行左旋，即将失衡状态改变到 LL，再对 g 节点进行一次右旋，最终恢复平衡

AVLLR

RL 失衡-右旋转+左旋转

与 LR 失衡类似，RL 是指导致节点 g 失衡的原因是其 right.left （RL）节点添加了节点，这时需要先对 p 节点进行右旋，即将失衡状态改变到 RR，再对 g 节点进行一次左旋，最终恢复平衡

AVLRL

删除导致失衡

删除可能导致删除节点的父节点或祖先节点失衡，但失衡节点只会存在一个，因为删除导致的失衡必然是删除了父节点高度较低的那个子树上的节点，而这棵树的高度并不会改变，例如，左边的树删除 16 会导致 15 失衡，右边的树删除 16 会导致 11 失衡，而其他节点并不会失衡

AVL删除导致失衡

删除导致的失衡，对于失衡节点来说依然会存在四种情况，LL、RR、LR、RL

LL 失衡-右旋转

这里需要注意，删除的节点是红色节点，但是节点 g 失衡依然可以看做是 n 子树中的某个节点引起的，方便统一进行恢复平衡操作，其次，虽然删除引起的失衡节点只会存在一个，但是，如果对失衡节点进行了旋转操作，从而导致以该失衡节点为根节点的子树高度变化，那么就可能会引起更高层的祖先节点失衡，例如在下面的示例中，如果没有绿色节点，那么 p 节点完成旋转后的高度就会减一，在最坏情况下，每一次恢复平衡的调整都会引起连锁反应，共需要 $ O(logN) $ 次调整

AVL删除LL

RR 失衡-左旋转

AVL删除RR

LR 失衡-左旋转+右旋转

AVL删除LR

RL 失衡-右旋转+左旋转

AVL删除RL

代码实现

注意，AVL 树是在 BST 基础上的优化，以下代码同样是在 BST 的代码上增加额外功能而来，并不是完整代码

基本属性和结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// AVL 节点内部类，除了存储的元素，还保存指针、高度等信息
    private static class AVLNode<E> {
        /**
        *   其他结构略，同 BST
        */

        // 高度，默认值为1，因为新节点肯定是叶子节点
        int height = 1;

        // 获取节点的平衡因子
        // 左子节点高度减去右子节点高度
        public int balanceFactor() {
            int leftHeight = left == null ? 0 : left.height;
            int rightHeight = right == null ? 0 : right.height;
            return leftHeight - rightHeight;
        }

        // 更新节点高度
        public void updateHeight() {
            int leftHeight = left == null ? 0 : left.height;
            int rightHeight = right == null ? 0 : right.height;
            // 高度等于左右子树最大高度 + 1
            height = 1 + Math.max(leftHeight, rightHeight);
        }

        // 判断该节点是父节点的左子节点
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        // 判断该节点是父节点的右子节点
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        // 返回两个子节点中较高的那一个
        private AVLNode<E> tallerChild() {
            int leftHeight = left == null ? 0 : left.height;
            int rightHeight = right == null ? 0 : right.height;
            if (leftHeight > rightHeight) return left;
            if (leftHeight < rightHeight) return right;
            // 如果高度一样，断该节点是父节点的左子节点，如果是，则返回left
            return isLeftChild() ? left : right;
        }
    }

基本方法准备

1
2
3
4
5
6
7
8
9
10
// 判断节点是否平衡
private boolean isBalanced(AVLNode<E> node) {
    // 比较该节点的左右节点的平衡因子，判断是否平衡。
    return Math.abs(node.balanceFactor()) <= 1;
}

// 更新某节点高度
private void updateHeight(AVLNode<E> node) {
    node.updateHeight();
}

左旋与右旋方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 实现左旋转，注意，传入的节点是要进行左旋转操作的节点，其必定有左子节点
private void leftRotate(AVLNode<E> node) {
    AVLNode<E> child = node.right;
    // 可能为空
    AVLNode<E> childLeft = child.left;
    node.right = childLeft;
    child.left = node;

    // 更新各个节点的父节点以及局部子树的根节点为child
    afterRotate(node, child, childLeft);
}

// 右旋
private void rightRotate(AVLNode<E> node) {
    AVLNode<E> child = node.left;
    AVLNode<E> childRight = child.right;
    node.left = childRight;
    child.right = node;
    afterRotate(node, child, childRight);
}

// 旋转之后的统一操作
private void afterRotate(AVLNode<E> node, AVLNode<E> child, AVLNode<E> childLeftOrRight) {
    child.parent = node.parent;
    if(node.isLeftChild()) {
        node.parent.left = child;
    } else if(node.isRightChild()) {
        node.parent.right = child;
    }else {
        root = child;
    }
    if(childLeftOrRight!=null) childLeftOrRight.parent = node;
    node.parent = child;
    // 更新节点高度，只有node和child会发生变化
    updateHeight(node);
    updateHeight(child);
}

恢复平衡方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 这里的入参grand就是 g 节点，是需要做旋转操作恢复平衡的节点
private void rebalance(AVLNode<E> grand) {
    // 较高的子节点必然是在引起失衡的子树中
    AVLNode<E> parent = grand.tallerChild();
    AVLNode<E> node = parent.tallerChild();

    if(parent.isLeftChild()) { // L
        if(node.isLeftChild()) { // LL
            rightRotate(grand);
        } else { // LR
            leftRotate(parent);
            rightRotate(grand);
        }
    } else { // R
        if(node.isRightChild()) { // RR
            leftRotate(grand);
        } else { // RL
            rightRotate(parent);
            leftRotate(grand);
        }
    }
}

afterAdd

在添加节点后，可能会引起失衡，所以我们要在原始的 BST 添加操作后调用此方法，进行恢复平衡。对于新添加的节点，需要通过 parent 属性，一路往上找，直到找到第一个失衡的祖先节点，也就是高度最低的那个失衡节点，然后对失衡节点进行调整，只要这个高度最低的失衡节点恢复平衡，那么所有的节点都恢复平衡了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 添加节点后的操作
private void afterAdd(AVLNode<E> node) {
    //可能添加新节点之后，整个树没有失衡。
    //所以我们需要一直查找到node.parent == null为止。
    while ((node = node.parent) != null) {
        // 判断节点是否平衡
        if (isBalanced(node)) {
            // 如果是平衡的，更新节点高度，新添加的节点高度默认是1，无需更新，从node.parent开始更新
            updateHeight(node);
        } else {
            // 否则，恢复平衡
            rebalance(node);
            // 整棵树恢复平衡
            break;
        }
    }
}

afterRemove

在删除某个节点后，可能会引起某个祖先节点失衡，仅需要一次调整，但是该失衡节点调整后可能导致更上层的祖先节点失衡

1
2
3
4
5
6
7
8
9
10
11
12
13
// 删除节点后的操作
private void afterRemove(AVLNode<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢复平衡
            rebalance(node);
            // 注意这里不要break掉，因为调整完这个节点后，其祖先节点可能失衡，需要继续调整
        }
    }
}

在 add 和 remove 方法中调用

1
2
3
4
5
6
7
8
9
10
11
12
13
public void add(E ele) {
    /**
     * 之前 BST 添加的逻辑
     */
    afterAdd(newNode);
}

private void remove(AVLNode<E> node) {
    /**
     * 之前 BST 删除的逻辑
     */
    afterRemove(node);
}

总结

添加

添加操作可能会导致所有祖先节点都失衡，但是只要需要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡，所以

删除

删除可能会导致父节点或某个祖先节点失衡（只有一个节点会失衡），但是对失衡节点采取恢复平衡操作后，可能会导致更高层的祖先节点失衡，所以最多需要 $ O(logN) $ 次调整

平均时间复杂度

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

参考