【数据结构与算法】手撕平衡二叉树

平衡二叉树

定义

• 动机：二叉查找树的操作实践复杂度由树高度决定，所以希望控制树高，左右子树尽可能平衡。

• 平衡二叉树（AVL树）：称一棵二叉查找树为高度平衡树，当且仅当或由单一外结点组成，或由两个子树形 Ta 和 Tb 组成，并且满足：

  • |h(Ta) - h(Tb)| <= 1，其中 h(T) 表示树 T 的高度
  • Ta 和 Tb 都是高度平衡树

即：每个结点的左子树和右子树的高度最多差 1 的 二叉查找树。

• 设 T 为高度平衡树中结点 q 的平衡系数为 q 的右子树高度减去左子树高度

• 高度平衡树所以结点的平衡系数只可能为：-1, 0, 1

结点结构

1️⃣ key：关键字的值
2️⃣ value：关键字的存储信息
3️⃣ height：树的高度（只有一个结点的树的高度为 1）
4️⃣ left：左子树根结点的的引用
5️⃣ right：右子树根结点的引用

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
java
class AVLNode<K extends Comparable<K>, V> {
    public K key;
    public V value;
    public int height;
    public AVLNode<K, V> left;
    public AVLNode<K, V> right;

    public AVLNode(K key, V value, int height) {
        this.key = key;
        this.value = value;
        this.height = height;
    }
}

查找算法

同二叉查找树的查找算法：【数据结构与算法】手撕二叉查找树

插入算法

AVL 树是一种二叉查找树，故可以使用二叉查找树的插入方法插入结点，但插入一个新结点时，有可能破坏 AVL 树的平衡性。

如果发生这种情况，就需要在插入结点后对平衡树进行调整，恢复平衡的性质。实现这种调整的操作称为“旋转”。

在插入一个新结点 X 后，应调整失去平衡的最小子树，即从插入点到根的路径向上找第一个不平衡结点 A。

平衡因子：该结点的左子树高度和右子树高度的差值。如果差值的绝对值小于等于 1，则说明该结点平衡，如果差值的绝对值为 2（不会出现其他情况），则说明该结点不平衡，需要做平衡处理。

造成结点 A 不平衡的的原因以及调整方式有以下几种情况。

LL 型

A 结点的平衡因子为 2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点左子结点的左子结点，所以为 LL 型。

扁担原理：右旋

• 将 A 的左孩子 B 提升为新的根结点；

• 将原来的根结点 A 降为 B 的右孩子；

• 各子树按大小关系连接(BL 和 AR 不变，BR 调整为 A 的左子树)。

• 高度调整：由于调整后 B 的高度依赖于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

复制代码
1
2
3
4
5
6
7
8
java
    private AVLNode<K, V> rightRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.left;
        a.left = b.right;
        b.right = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1;
        return b;
    }

RR 型

A 结点的平衡因子为 2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点右子结点的右子结点，所以为 RR 型。

扁担原理：左旋

• 将 A 的右孩子 B 提升为新的根结点；

• 将原来的根结点 A 降为 B 的左孩子；

• 各子树按大小关系连接(AL 和 BR 不变，BL 调整为 A 的右子树)。

• 高度调整：由于调整后 B 的高度依赖于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

复制代码
1
2
3
4
5
6
7
8
java
    private AVLNode<K, V> leftRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.right;
        a.right = b.left;
        b.left = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1;
        return b;
    }

LR 型

A 结点的平衡因子为 2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点左子结点的右子结点，所以为 LR 型。

• 从旋转的角度：对 B 左旋，然后对 A 右旋

• 将 B 的左孩子 C 提升为新的根结点；

• 将原来的根结点 A 降为 C 的右孩子；

• 各子树按大小关系连接(BL 和 AR 不变，CL 和 CR 分别调整为 B 的右子树和 A 的左子树)。

复制代码
1
2
3
4
java
    private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
        a.left = leftRotate(a.left);   // 对 B 左旋
        return rightRotate(a);         // 对 A 右旋
    }

RL 型

A 结点的平衡因子为 2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点右子结点的左子结点，所以为 RL 型。

• 从旋转的角度：对 B 右旋，然后对 A 左旋

• 将 B 的左孩子 C 提升为新的根结点；

• 将原来的根结点 A 降为 C 的左孩子；

• 各子树按大小关系连接(AL 和 BR 不变，CL 和 CR 分别调整为 A 的右子树和 B 的左子树)。

复制代码
1
2
3
4
java
    private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
        a.right = rightRotate(a.right);
        return leftRotate(a);
    }

插入方法

• 根结点默认高度为 1

• 某结点的左右子树高度差的绝对值为 2，则需要进行平衡处理

  • 左子树高

    • key 小于 root.left.key：LL型，进行右旋
      

    • key 大于 root.left.key：LR型，进行左右旋
      

  • 右子树高

    • key 大于 root.right.key：RR型，进行左旋
      

    • key 小于 root.right.key：RL型，进行右左旋
      

复制代码
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
java
    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) {
        if (t == null) {
            return new AVLNode<>(key, value, 1);
        } else if (key.compareTo(t.key) < 0) {
            t.left = insert(t.left, key, value);
            t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
            // 平衡因子判断
            if (getHeight(t.left) - getHeight(t.right) == 2) {
                if (key.compareTo(t.left.key) < 0) // 左左：右旋
                    t = rightRotate(t);
                else                                 // 左右：先左旋，再右旋
                    t = leftRightRotate(t);
            }
        } else if (key.compareTo(t.key) > 0) {
            t.right = insert(t.right, key, value);
            t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
            // 平衡因子判断
            if (getHeight(t.left) - getHeight(t.right) == -2) {
                if (key.compareTo(t.right.key) > 0) // 右右：左旋
                    t = leftRotate(t);
                else                                  // 右左：先右旋，再左旋
                    t = rightLeftRotate(t);
            }
        } else {
            t.value = value;
        }
        return t;
    }

删除算法

概述

• 可采用二叉查找树的删除算法进行删除。
  【数据结构与算法】手撕二叉查找树

• 删除某结点 X 后，沿从 X 到根节点的路径上考察沿途结点的平衡系数，若第一个不平衡点为 A，平衡以 A 为根的子树。

• 平衡后，可能使子树 A 高度变小。这样可能导致 A 的父节点不满足平衡性。

• 所以要继续向上考察结点的平衡性，最远可能至根结点，即最多需要做 O(logn) 次旋转。

• 对比“插入”操作：平衡 A 后，子树高度不变，A 子树以外的结点不受影响，即插入最多涉及 O(1) 次旋转。

实例分析

🌰 下面举个删除的例子：

删除以下平衡二叉树中的 16 结点

1️⃣ 16 为叶子，将其删除即可，如下图。

2️⃣ 指针 g 指向实际被删除节点 16 之父 25，检查是否失衡，25 节点失衡，用 g 、u 、v 记录失衡三代节点（从失衡节点沿着高度大的子树向下找三代），判断为 RL 型，进行 RL 旋转调整平衡，如下图所示。

3️⃣ 继续向上检查，指针 g 指向 g 的双亲 69，检查是否失衡，69 节点失衡，用 g 、u 、v 记录失衡三代节点，判断为 RR 型，进行 RR 旋转调整平衡，如下图所示。

代码

代码描述：

• 若当前结点为空， 则返回该节点

• 若关键值小于当前结点的关键值，则递归处理该结点的左子树

• 若关键值大于当前结点的关键值，则递归处理该结点的右子树

• 若关键值等于当前结点的关键值

  • 若当前结点的左子树为空，则返回该结点的右子树根节点

  • 若当前结点的右子树为空，则返回该结点的左子树根节点

  • 若当前结点左右子树都不为空，则找到该结点的中序前驱结点（该结点左子树的最右结点）或中序后继结点（该结点右子树的最左结点），将其值赋予该结点，然后递归删除中序前驱或后继结点。

• 更新结点高度

• 若该结点左子树高度更高，且处于不平衡状态

  • 若为 LL 型，进行右旋

  • 若为 LR 型，先左旋，再右旋

• 若该结点右子树高度更高，且处于不平衡状态

  • 若为 RL 型，先右旋，再左旋

  • 若为 RR 型，进行左旋

• 返回该结点

复制代码
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
java
    public void remove(K key) {
        this.root = delete(root, key);
    }

    public AVLNode<K, V> delete(AVLNode<K, V> t, K key) {
        if (t == null) return t;
        if (key.compareTo(t.key) < 0) {
            t.left = delete(t.left, key);
        }
        else if (key.compareTo(t.key) > 0) {
            t.right = delete(t.right, key);
        }
        else {
            if(t.left == null) return t.right;
            else if(t.right == null) return t.left;
            else {         // t.left != null && t.right != null
                AVLNode<K, V> pre = t.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                t.key = pre.key;
                t.value = pre.value;
                t.left = delete(t.left, t.key);
            }
        }
        if (t == null) return t;
        t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
        if(getHeight(t.left) - getHeight(t.right) >= 2) {
            if(getHeight(t.left.left) > getHeight(t.left.right)) {
                return rightRotate(t);
            } else {
                return leftRightRotate(t);
            }
        }
        else if(getHeight(t.left) - getHeight(t.right) <= -2) {
            if(getHeight(t.right.left) > getHeight(t.right.right)) {
                return rightLeftRotate(t);
            }
            else {
                return leftRotate(t);
            }
        }
        return t;
    }

完整代码

复制代码
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
java
class AVLNode<K extends Comparable<K>, V> {
    public K key;
    public V value;
    public int height;
    public AVLNode<K, V> left;
    public AVLNode<K, V> right;

    public AVLNode(K key, V value, int height) {
        this.key = key;
        this.value = value;
        this.height = height;
    }
}

class AVLTree<K extends Comparable<K>, V> {

    public AVLNode<K, V> root;

    public int getHeight(AVLNode<K, V> t) {
        return t == null ? 0 : t.height;
    }

    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    public void remove(K key) {
        this.root = delete(root, key);
    }

    public AVLNode<K, V> delete(AVLNode<K, V> t, K key) {
        if (t == null) return t;
        if (key.compareTo(t.key) < 0) {
            t.left = delete(t.left, key);
        }
        else if (key.compareTo(t.key) > 0) {
            t.right = delete(t.right, key);
        }
        else {
            if(t.left == null) return t.right;
            else if(t.right == null) return t.left;
            else {         // t.left != null && t.right != null
                AVLNode<K, V> pre = t.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                t.key = pre.key;
                t.value = pre.value;
                t.left = delete(t.left, t.key);
            }
        }
        if (t == null) return t;
        t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
        if(getHeight(t.left) - getHeight(t.right) >= 2) {
            if(getHeight(t.left.left) > getHeight(t.left.right)) {
                return rightRotate(t);
            } else {
                return leftRightRotate(t);
            }
        }
        else if(getHeight(t.left) - getHeight(t.right) <= -2) {
            if(getHeight(t.right.left) > getHeight(t.right.right)) {
                return rightLeftRotate(t);
            }
            else {
                return leftRotate(t);
            }
        }
        return t;
    }


    private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) {
        if (t == null) {
            return new AVLNode<>(key, value, 1);
        }
        if (key.compareTo(t.key) < 0) {
            t.left = insert(t.left, key, value);
            // 平衡因子判断
            if (getHeight(t.left) - getHeight(t.right) == 2) {
                if (key.compareTo(t.left.key) < 0) // 左左：右旋
                    t = rightRotate(t);
                else                                  // 左右：先左旋，再右旋
                    t = leftRightRotate(t);
            }
        } else if (key.compareTo(t.key) > 0) {
            t.right = insert(t.right, key, value);
            // 平衡因子判断
            if (getHeight(t.left) - getHeight(t.right) == -2) {
                if (key.compareTo(t.right.key) > 0) // 右右：左旋
                    t = leftRotate(t);
                else                                   // 右左：先右旋，再左旋
                    t = rightLeftRotate(t);
            }
        } else {
            t.value = value;
        }
        t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
        return t;
    }

    private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
        a.right = rightRotate(a.right);
        return leftRotate(a);
    }

    private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
        a.left = leftRotate(a.left);
        return rightRotate(a);
    }

    private AVLNode<K, V> leftRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.right;
        a.right = b.left;
        b.left = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
        return b;
    }

    private AVLNode<K, V> rightRotate(AVLNode<K, V> a) {
        AVLNode<K, V> b = a.left;
        a.left = b.right;
        b.right = a;
        a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
        b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
        return b;
    }

    private void inorder(AVLNode<K, V> root) {
        if (root != null) {
            inorder(root.left);
            System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
            inorder(root.right);
        }
    }

    private void preorder(AVLNode<K, V> root) {
        if (root != null) {
            System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
            preorder(root.left);
            preorder(root.right);
        }
    }

    private void postorder(AVLNode<K, V> root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
        }
    }

    public void postorderTraverse() {
        System.out.print("后序遍历：");
        postorder(root);
        System.out.println();
    }

    public void preorderTraverse() {
        System.out.print("先序遍历：");
        preorder(root);
        System.out.println();
    }

    public void inorderTraverse() {
        System.out.print("中序遍历：");
        inorder(root);
        System.out.println();
    }
}

🐛 方法测试

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java
    public static void main(String[] args) {
        AVLTree<Integer, Integer> tree = new AVLTree<>();
        tree.insert(69, 1);
        tree.insert(25, 1);
        tree.insert(80, 1);
        tree.insert(16, 1);
        tree.insert(56, 1);
        tree.insert(75, 1);
        tree.insert(90, 1);
        tree.insert(30, 1);
        tree.insert(78, 1);
        tree.insert(85, 1);
        tree.insert(98, 1);
        tree.insert(82, 1);

        tree.remove(16);
        tree.preorderTraverse();
        tree.inorderTraverse();
        tree.postorderTraverse();
    }

输出

复制代码
1
2
3
java
先序遍历：(key: 80 , value: 1 , height: 4) (key: 69 , value: 1 , height: 3) (key: 30 , value: 1 , height: 2) (key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 85 , value: 1 , height: 2) (key: 82 , value: 1 , height: 1) (key: 98 , value: 1 , height: 1) 
中序遍历：(key: 25 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 56 , value: 1 , height: 1) (key: 69 , value: 1 , height: 3) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 80 , value: 1 , height: 4) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 90 , value: 1 , height: 3) (key: 98 , value: 1 , height: 1) 
后序遍历：(key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 69 , value: 1 , height: 3) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 98 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 80 , value: 1 , height: 4)