本文假设读者已经知道:

  • 什么是二叉搜索树
  • 二叉搜索树不平衡时会带来的问题

AVL树的定义和性质

AVL是由两个苏联人 Georgy Adelson-Velsky 和 Evgenii Landis 发明的。

Wiki上没有查到上纲上线的定义,论文……毛子的文字一点都看不懂(搞得像英文版你看懂了一样……)。

我是这样定义的:

  • 空树是高度为0的AVL树
  • 左右两个子树都是AVL树,且两个子树间的高度差小于等于1的树是AVL树,其高度为两个子树高度中较大的那个+1

AVL的插入

大体上可以参照二叉搜索树的插入。

但是在一些情况下,插入可能导致树不再符合AVL的特性,需要进行一些调整。

情况1

向如下的树中插入值28:

origin

如二叉搜索树那样插入之后:

inserted

显然根节点的左右高度差大于1了,需要调整,因为这里整棵树完全是左偏(因为刚刚的节点插入的位置在不平衡出现的节点的左子树的左子树),这里的调整方法是右旋:

right-rotate1

右旋

所谓右旋,如下图,就是把连接new_rootold_root之间的连接线“右旋”。

right_rotate

在以old_root为根的这棵树左侧(以new_root为根)的子树高度比其右子树(C)高度大时,这样一转会得到一棵以new_root为根,左右高度相对较为平衡的新子树。

情况2

情况2是情况1的镜像:

向这里插入90:

origin-2

如二叉搜索树插入:

屏幕快照 2018-12-04 下午6.28.49

进行左旋:

left-totate1

左旋

左旋就是右旋的逆过程:

left_rotate

情况3

向这里插入45:

origin-3

如普通二叉搜索树插入,会得到:

inserted-3

此时43这个节点右侧显然比左侧高,此时我们能直接左旋吗?

显然不能,因为刚刚的节点插入的位置在不平衡出现的节点的右子树的左子树,如果直接左旋了,就会变成:

insert-bad-rotate

这里60左侧的子树高度为3,右侧的子树高度为1,这里直接的左旋不过是把一处的不平衡转移到了另外一侧,对让树变得平衡并没有任何帮助。

为了解决这个问题,我们要先在60(不平衡的位置的右子树)的位置上右旋一次:

insert-good-rotate-1

再在43处左旋一次,即可得到:

屏幕快照 2018-12-10 下午2.11.43

情况4

情况4就是情况3的镜像,即树是右偏,但刚刚的节点插入的位置在不平衡出现的节点的左子树的右子树。

处理方式也是镜像的,在不平衡的位置的左子树上左旋一次,再在不平衡的位置上右旋一次。

AVL树的删除

删除的方式大体上和普通二叉搜索树一样,即找到要删除的节点,然后找出其中序遍历中的后继节点,用其替换这个要删除的节点。

唯一的区别在于删除后需要重新平衡这棵树,删除之后树可能的情况和上面插入时一样,故也能用相似的方法进行调整,使得树平衡。

参考实现

这个实现并不是最漂亮,但是功能应该都能用了:

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
172
173
174
namespace AVLTree {
template<typename T>
struct Node {
T data;
Node<T> *left;
Node<T> *right;
size_t m_height;

Node(T data_,
Node<T> *left_, Node<T> *right_, size_t height_) :
data(data_), left(left_), right(right_), m_height(height_) {
}

explicit Node(T data_) : Node(data_, nullptr, nullptr, 1) {}
};

template<typename T, typename Compare = std::less<T>>
class AVLTree {
private:
Node<T> *root;
Compare compare;
public:
AVLTree() : root(nullptr) {}

private:
size_t height(Node<T> *node) {
return node == nullptr ? 0 : node->m_height;
}

Node<T> *left_rotation(Node<T> *old_root) {
auto new_root = old_root->right;
old_root->right = old_root->right->left;
new_root->left = old_root;
old_root->m_height = std::max(height(old_root->left), height(old_root->right)) + 1;
return new_root;
}

Node<T> *right_rotation(Node<T> *old_root) {
auto new_root = old_root->left;
old_root->left = old_root->left->right;
new_root->right = old_root;
old_root->m_height = std::max(height(old_root->left), height(old_root->right)) + 1;
return new_root;
}

Node<T> *insert(Node<T> *old_root, T value) {
assert(old_root != nullptr);
Node<T> *new_root = old_root;
if (compare(value, old_root->data)) {
if (old_root->left == nullptr) {
old_root->left = new Node<T>(value);
} else {
old_root->left = insert(old_root->left, value);
}
if (height(old_root->left) - height(old_root->right) == 2) {
if (compare(value, old_root->left->data)) {
new_root = right_rotation(old_root);
} else {
old_root->left = left_rotation(old_root->left);
new_root = right_rotation(old_root);
}
}
} else if (compare(old_root->data, value)) {
if (old_root->right == nullptr) {
old_root->right = new Node<T>(value);
} else {
old_root->right = insert(old_root->right, value);
}
if (height(old_root->right) - height(old_root->left) == 2) {
if (compare(old_root->right->data, value)) {
new_root = left_rotation(old_root);
} else {
old_root->right = right_rotation(old_root->right);
new_root = left_rotation(old_root);
}
}
}
new_root->m_height = std::max(height(new_root->left), height(new_root->right)) + 1;
return new_root;
}

Node<T> *minimum(Node<T> *root) {
if (root->left != nullptr) {
return minimum(root->left);
}
return root;
}

Node<T> *maximum(Node<T> *root) {
if (root->right != nullptr) {
return minimum(root->right);
}
return root;
}

Node<T> *find(Node<T> *root, T value) {
if (root == nullptr) {
return nullptr;
}
if (compare(value, root->data)) {
return find(root->left, value);
} else if (compare(root->data, value)) {
return find(root->right, value);
} else {
return root;
}
}

Node<T> *remove(Node<T> *old_root, Node<T> *node) {
if (old_root == nullptr || node == nullptr) {
return old_root;
}
auto new_root = old_root;
if (compare(node->data, old_root->data)) {
old_root->left = remove(old_root->left, node);
old_root->m_height = std::max(height(old_root->left), height(old_root->right)) + 1;
if (height(old_root->right) - height(old_root->left) == 2) {
if (height(old_root->right->left) > height(old_root->right->right)) {
new_root->right = right_rotation(new_root->right);
new_root = left_rotation(new_root);
} else {
new_root = left_rotation(old_root);
}
}
} else if (compare(old_root->data, node->data)) {
old_root->right = remove(old_root->right, node);
old_root->m_height = std::max(height(old_root->left), height(old_root->right)) + 1;
if (height(old_root->left) - height(old_root->right) == 2) {
if (height(old_root->left->right) > height(old_root->left->left)) {
new_root->left = left_rotation(new_root->left);
new_root = right_rotation(new_root);
} else {
new_root = right_rotation(old_root);
}
}
} else {
if (old_root->left != nullptr && old_root->right != nullptr) {
if (height(old_root->left) >= height(old_root->right)) {
auto node_to_remove = maximum(old_root->left);
new_root->data = node_to_remove->data;
new_root->left = remove(old_root->left, node_to_remove);
} else {
auto node_to_remove = minimum(old_root->right);
new_root->data = node_to_remove->data;
new_root->left = remove(old_root->right, node_to_remove);
}
} else {
new_root = (old_root->left != nullptr) ? old_root->left : old_root->right;
delete old_root;
}
}
if (new_root != nullptr)
new_root->m_height = std::max(height(new_root->left), height(new_root->right)) + 1;
return new_root;
}

public:
void insert(T value) {
if (root == nullptr) {
root = new Node<T>(value);
} else {
root = insert(root, value);
}
}

void remove(T value) {
root = remove(root, find(root, value));
}

bool contains(T value) {
return find(root, value) == nullptr;
}
};
}

AVL树 vs 红黑树

AVL树比红黑树更平衡,因为:

  • 红黑树规定从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
  • AVL树两个子树间的高度差小于等于1

在最糟糕的情况下,红黑树上某条路径到叶子的路径长度会是约log2(n)的两倍,而AVL树则仍然高度平衡。

但是在大量插入和删除数据时,AVL会旋转很多次,拖慢速度,而红黑树的旋转次数较少。

故红黑树在大量插入删除,少量查找时较占优势,AVL树则在少量查找、大量插入删除时较有优势。