AVL 树 (Adelson-Velsky and Landis Tree)，属于平衡树 的一种。
在 AVL 树中，任一节点的左子树和右子树的高度差(平衡因子)都小于等于1，如果平衡因子大于 1，那么认为这个节点是不平衡的，需要重新通过旋转(rotate) 重新平衡这个节点。
AVL 树的增加、删除、查找的时间复杂度最差和平均都为 O(log n)
认识平衡二叉树#
1
2
3
4
5
6
7
8
9
10
11
|
+-------+-------------+---------+-----------+---------+
| Yes | Yes | No | No | No |
+-------+-------------+---------+-----------+---------+
| 4 | 5 | 4 | 4 | 4 |
| \ | / \ | / \ | / \ | \ |
| 5 | 3 7 | 2 6 | 2 6 | 6 |
| | / \ \ | \ | / | / \ |
| | 1 4 8 | 3 | 3 | 5 7 |
| | \ | | | |
| | 2 | | | |
+-------+-------------+---------+-----------+---------+
|
旋转(rotate)#
阶段一#
1
2
3
4
5
6
|
A: | B:
b | c
\ | / \
c | b d
\ |
d |
|
我们可以看到，A 中节点 b 的左子树的高度为 0，而右子树的高度为 2，说明这不是一个 AVL 树。由 b, c, d 组成的树应该是 B 的样子。
将 A 转换为 B 的过程:
- 将 b 的右子树设置为 空
- 将 c 的左子树设置为 b
1
2
3
4
|
step1: step2
b c | c
\ | / \
d | b d
|
阶段二#
👆实际操作的步骤看起来也不难，那么加大难度，现在这颗树变成了这样
1
2
3
4
5
6
|
A: | B:
b | d
\ | / \
d | b e
/ \ | \
c e | c
|
现在再来看 A，依然不是一个 ACL 树，理想中的 ACL 树还是应该是长成 B 的样子。
那么如何处理呢？🧐
- 将 b 的右子树设置为 d 的左子树 -> c
- 将 d 的左子树设置为 b
1
2
3
4
5
6
|
step1: step2
b d | d
\ \ | / \
c e | b e
| \
| c
|
上面的操作步骤，就是左旋的过程
右旋和左旋原理一样，只是方向不同而已，就不再举例了。
阶段三#
看到这里，好像很简单？还没完，我们再来看一种情况：
1
2
3
4
5
6
7
|
b
/ \
a e
/ \
c f
\
d
|
同样，这不是一棵 ACL 树。但是通过我们上面了解的知识，看起来只需要通过右旋就可以搞定了，好，试一试
1
2
3
4
5
6
7
|
e
/ \
b f
/ \
a c
\
d
|
😵💫 好了，现在是左侧节点不平衡了，是不是需要左旋了？左旋以后是什么样子
1
2
3
4
5
6
7
|
b
/ \
a e
/ \
c f
\
d
|
😵💫 看起来陷入了死循环了。遇到情况该如何解决呢？
当需要左旋时，root 节点的右子树 root.Right ，简称 B。如果 B 的左子树的高度大于右子树的高度，我们需要先对 B 做右旋操作，然后再对 root 做左旋操作
使用这个规则试试看
1
2
3
4
5
6
7
8
9
10
11
|
+-----------+-------------+-------------+
| 原始树 | b.e 右旋后 | b 左旋后 |
+-----------+-------------+-------------+
| b | b | c |
| / \ | / \ | / \ |
| a e | a c | b e |
| / \ | \ | / / \ |
| c f | e | a d f |
| \ | / \ | |
| d | d f | |
+-----------+-------------+-------------+
|
成功啦🎉
-
当节点左子树的高度比右子树的高度高出 2 时，节点需要右旋
-
当节点右子树的高度比左子树的高度高出 2 时，节点需要左旋
-
节点 A 左旋之前需要先检查 A 的右子树 (A.B) 的左子树是否比右子树的高度更高
- 如果 A.B 的左子树比右子树高，那么需要先将 A.B 右旋再将 A 左旋
-
节点 A 右旋之前需要先检查 A 的左子树 (A.B) 的右子树是否比左子树的高度更高
- 如果 A.B 的右子树比左子树高，那么需要先将 A.B 左旋再将 A 右旋
靠文字描述旋转的过程真的很难理解，我在 wiki 上看到了这张图，可以很直观的看到旋转的过程
By Bruno Schalch - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=64250599
Golang implementation#
Talk is cheap, show me the code#
直接看代码
Node#
1
2
3
4
5
6
7
8
9
10
11
12
|
// Node represend a node in AVL tree
type Node struct {
val int
left, right *Node
}
// NewNode create a Node
func NewNode(val int) *Node {
return &Node{
val: val,
}
}
|
Node - 实用方法#
前文中很多地方都提到了节点的高度，我们需要知道节点左子树的高度，右子树的高度，和最高的高度。
所以提供了一些方法，方便后续调用
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
|
// leftMaxHeight max height of left child node
func (n *Node) leftMaxHeight() int {
if n.left == nil {
return 0
}
return n.left.maxHeight() + 1
}
// rightMaxHeight max height of right child node
func (n *Node) rightMaxHeight() int {
if n.right == nil {
return 0
}
return n.right.maxHeight() + 1
}
// maxHeight calculate max height of node
func (n *Node) maxHeight() int {
if n.left == nil && n.right == nil {
return 0
}
if n.left == nil {
return n.right.maxHeight() + 1
}
if n.right == nil {
return n.left.maxHeight() + 1
}
return max(n.left.maxHeight()+1, n.right.maxHeight()+1)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
|
Node - 实现左旋和右旋逻辑#
前面聊旋转聊了那么多，但其实用代码表达起来特别简单，这么几行搞定
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func (n *Node) rightRotate() *Node {
root := n.left
n.left = root.right
root.right = n
return root
}
func (n *Node) leftRotate() *Node {
root := n.right
n.right = root.left
root.left = n
return root
}
|
* 这两个方法都返回了一个 Node 实例
a.b 旋转以后，a 就不应该指向 b 了，而是指向 b 旋转后新成为 b 这棵树上的 root 的节点，可以在下面的 autoRetate 方法中看到
Node - 添加元素#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Add an element into AVL tree
func (n *Node) Add(val int) {
if n.val == val {
return n
}
if n.val > val {
if n.left == nil {
n.left = NewNode(val)
} else {
n.left.Add(val)
}
} else {
if n.right == nil {
n.right = NewNode(val)
} else {
n.right.Add(val)
}
}
}
|
朴实无华的递归添加元素，还没有集成旋转，现在来写自动旋转的逻辑
Node - 实现自动旋转#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// autoRotate automate rotate Nodes
func (n *Node) autoRotate() *Node {
ld := n.leftMaxHeight()
rd := n.rightMaxHeight()
// 差值在 1 以内，不需要自旋
if math.Abs(float64(ld-rd)) <= 1 {
return n
}
// 左侧深度大于右侧深度，需要右旋
if ld > rd {
// 右旋之前先检查左侧节点的右子节点是否比左子节点更深
// 如果 true 的话，左侧节点需要先左旋
if n.left.rightMaxHeight() > n.left.leftMaxHeight() {
n.left = n.left.leftRotate()
}
return n.rightRotate()
} else {
// 同上
if n.right.leftMaxHeight() > n.right.rightMaxHeight() {
n.right = n.right.rightRotate()
}
return n.leftRotate()
}
}
|
让我们再来改造一下 Add 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func (n *Node) Add(val int) *Node {
if n.val == val {
return n
}
if n.val > val {
if n.left == nil {
n.left = NewNode(val)
} else {
n.left = n.left.Add(val)
}
} else {
if n.right == nil {
n.right = NewNode(val)
} else {
n.right = n.right.Add(val)
}
}
return n.autoRotate()
}
|
AVL#
大部分的工作都是由 Node 来做的, AVL 只是包装了一层
1
2
3
4
5
6
7
8
9
10
11
|
// AVL represent an AVL Tree
type AVL struct {
root *Node
}
// NewAVL create an AVL
func NewAVL() *AVL {
return &AVL{
root: NewNode(0),
}
}
|
AVL - Add#
1
2
3
4
|
// Add an element into AVL Tree
func (a *AVL) Add(val int) {
a.root = a.root.Add(val)
}
|
测试用例有点多，就不贴上来了，看一下测试结果
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
|
$ go test -v ./...
=== RUN TestNode_leftMaxHeight
=== RUN TestNode_leftMaxHeight/ok
=== RUN TestNode_leftMaxHeight/ok_-_1
=== RUN TestNode_leftMaxHeight/ok_-_2
=== RUN TestNode_leftMaxHeight/ok_-_3
=== RUN TestNode_leftMaxHeight/ok_-_4
--- PASS: TestNode_leftMaxHeight (0.00s)
--- PASS: TestNode_leftMaxHeight/ok (0.00s)
--- PASS: TestNode_leftMaxHeight/ok_-_1 (0.00s)
--- PASS: TestNode_leftMaxHeight/ok_-_2 (0.00s)
--- PASS: TestNode_leftMaxHeight/ok_-_3 (0.00s)
--- PASS: TestNode_leftMaxHeight/ok_-_4 (0.00s)
=== RUN TestNode_maxHeight
=== RUN TestNode_maxHeight/case_-_1
=== RUN TestNode_maxHeight/case_-_2
--- PASS: TestNode_maxHeight (0.00s)
--- PASS: TestNode_maxHeight/case_-_1 (0.00s)
--- PASS: TestNode_maxHeight/case_-_2 (0.00s)
=== RUN TestNode_rightMaxHeight
=== RUN TestNode_rightMaxHeight/ok
=== RUN TestNode_rightMaxHeight/ok_-_1
=== RUN TestNode_rightMaxHeight/ok_-_2
=== RUN TestNode_rightMaxHeight/#00
--- PASS: TestNode_rightMaxHeight (0.00s)
--- PASS: TestNode_rightMaxHeight/ok (0.00s)
--- PASS: TestNode_rightMaxHeight/ok_-_1 (0.00s)
--- PASS: TestNode_rightMaxHeight/ok_-_2 (0.00s)
--- PASS: TestNode_rightMaxHeight/#00 (0.00s)
=== RUN TestNode_autoRotate
=== RUN TestNode_autoRotate/right_rotate
=== RUN TestNode_autoRotate/left_rotate
=== RUN TestNode_autoRotate/no_rotate_performed
=== RUN TestNode_autoRotate/left-right_rotate
=== RUN TestNode_autoRotate/right-left_rotate
--- PASS: TestNode_autoRotate (0.00s)
--- PASS: TestNode_autoRotate/right_rotate (0.00s)
--- PASS: TestNode_autoRotate/left_rotate (0.00s)
--- PASS: TestNode_autoRotate/no_rotate_performed (0.00s)
--- PASS: TestNode_autoRotate/left-right_rotate (0.00s)
--- PASS: TestNode_autoRotate/right-left_rotate (0.00s)
PASS
ok github.com/ningzio/algorithm/avl 0.561s
|
写在最后#
论测试用例的重要性
又一次感受到了写测试用例带来的好处。
上面的代码是我改过一次的版本，最初的代码写完后发现测试用例根本过不了，又回过头来找问题然后重写有问题的部分。
如果没有测试用例来验证，这种复杂的结构真的很难发现，可能只会在出错的时候一脸懵逼的找问题。
所以，别忘了写测试用例～
2022-03-13 01:27 终于结束了，花了五六个小时学习 + 写文章，我可太能卷了😂