1. 简介
AVL树得名于它的发明者—前苏联的数学家G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。
2. 定义
AVL树其实是一棵高度平衡的二叉搜索树，它是依靠平衡因子来维持树的高度。
- 对于每个结点来说，它的左右子树高度差的绝对值（平衡因子）不会超过1。
- 它具有和二叉搜索树一样的性质，也就是说除了二叉搜索树中那些会改变树的高度的操作（插入，删除），其他的操作都可以用在AVL树中。
3. 实现
因为AVL树除了插入，删除这些可能改变树高度的操作之外，其他操作的与二叉搜索树无异，所以这里只讲插入和删除操作。
- 每个叶子结点的高度都为1
- 每个结点都有高度，其高度为左右孩子中最高孩子的高度加上1
- 每个结点的高度差为左子树的高度减去右子树的高度
- 每当插入或删除一个结点后，可能导致某个结点的平衡因子超过1，这时候就需要对以这个结点进行旋转操作来维持平衡。
旋转操作：
1. 左左旋转：
如上图，当插入一个0001这个结点后，导致0003的平衡因子超过1，此时0003结点需要通过左左旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的左孩子的左孩子上，取名左左旋转，旋转后的结果如下图：
代码实现：1
2
3
4
5
6
7
8//左左旋转
private Node rotationLeft(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
updateHeight(node);
return x;
}
2. 右右旋转：
如上图，当插入一个0003这个结点后，导致0001的平衡因子超过1，此时0003结点需要通过右右旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的右孩子的右孩子上，取名右右旋转，旋转后的结果如下图：
代码实现：1
2
3
4
5
6
7
8//右右旋转
private Node rotationRight(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
updateHeight(node);
return x;
}
3. 右左旋转：
如上图，当插入一个0002这个结点后，导致0001的平衡因子超过1，此时0001结点需要通过右左旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的右孩子的左孩子上，取名右左旋转，旋转后的结果如下图：
代码实现：1
2
3
4
5
6//右左旋转
private Node rotationRightLeft(Node node){
node.right = rotationLeft(node.right);
updateHeight(node.right);
return rotationRight(node);
}
4.左右旋转：
如上图，当插入一个0002这个结点后，导致0003的平衡因子超过1，此时0003结点需要通过左右旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的左孩子的右孩子上，取名左右旋转，旋转后的结果如下图：
代码实现：1
2
3
4
5
6//左右旋转
private Node rotationLeftRight(Node node){
node.left = rotationRight(node.left);
updateHeight(node.left);
return rotationLeft(node);
}
4. 时间复杂度
由于AVL树是一个高度平衡的二叉搜索树，所以树的高度几乎是lgN，所以无论查找，插入还是删除操作最坏情况的时间复杂度为O(lgN)。
5. 代码实现
其中的插入删除操作都是用递归来实现的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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
import java.util.*;
public class AVL <Key extends Comparable<Key>, Value>{
private class Node{
Key key;
Value value;
int height;
Node left;
Node right;
public Node(Key key, Value value, int height, Node left, Node right){
this.key = key;
this.value = value;
this.height = height;
this.left = left;
this.right = right;
}
}
private Node root;
private int size;
public int size(){
return size;
}
//获取树高度
public int height(Node node){
return node == null ? 0 : node.height;
}
//高度差
private int altitude(Node node){
return height(node.left) - height(node.right);
}
//更新树高度
private void updateHeight(Node node){
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
//右旋
private Node rotationRight(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
updateHeight(node);
return x;
}
//左旋
private Node rotationLeft(Node node){
Node x = node.left;
node.left = x.right;
x.right = node;
updateHeight(node);
return x;
}
//左右旋转
private Node rotationLeftRight(Node node){
node.left = rotationRight(node.left);
updateHeight(node.left);
return rotationLeft(node);
}
//右左旋转
private Node rotationRightLeft(Node node){
node.right = rotationLeft(node.right);
updateHeight(node.right);
return rotationRight(node);
}
//平衡
private Node balance(Node node, int altitude){
if (altitude == 2)
node = height(node.left.left) > height(node.left.right) ? rotationLeft(node) : rotationLeftRight(node);
else if (altitude == -2)
node = height(node.right.left) > height(node.right.right) ? rotationRightLeft(node) : rotationRight(node);
updateHeight(node);
return node;
}
//插入
public void put(Key key, Value value){
root = put(key, value, root);
++size;
}
private Node put(Key key, Value value, Node node) {
if (node == null)
return new Node(key, value, 1, null, null);
int cmp = key.compareTo(node.key);
if (cmp < 0)
node.left = put(key, value, node.left);
else if (cmp > 0)
node.right = put(key, value, node.right);
else {
node.value = value;
return node;
}
return balance(node, altitude(node));
}
private Node max(Node node){
if (node == null)
return null;
while (node.right != null)
node = node.right;
return node;
}
public Value max() {
return root == null ? null : max(root).value;
}
public void deleteMax(){
if (root != null) {
root = deleteMax(root);
--size;
}
}
private Node deleteMax(Node node){
if (node.right == null)
return node.left;
node.right = deleteMax(node.right);
return balance(node, altitude(node));
}
private Node deleteMin(Node node){
if (node.left == null)
return node.right;
node.left = deleteMin(node.left);
return balance(node, altitude(node));
}
public void deleteMin(){
if (root != null) {
root = deleteMin(root);
--size;
}
}
public Value delete(Key key){
Node node = delete(key, root);
if (node != null)
return node.value;
return null;
}
private Node delete(Key key, Node node){
if (node == null)
return null;
int cmp = key.compareTo(node.key);
if (cmp < 0)
node.left = delete(key, node.left);
else if (cmp > 0)
node.right = delete(key, node.right);
else {
--size;
if (node.left == null)
return node.right;
if (node.right == null)
return node.left;
Node x = max(node.right);
node.key = x.key;
node.value = x.value;
node.right = deleteMax(node.right);
}
return balance(node, altitude(node));
}
//中序遍历
private void inorderTraverse(Node node, Set<Key> keySet){
if (node == null)
return;
inorderTraverse(node.left, keySet);
keySet.add(node.key);
inorderTraverse(node.right, keySet);
}
//返回一个把键从小到大排序的迭代器
public Iterable<Key> keySet(){
Set<Key> keySet = new TreeSet<>();
inorderTraverse(root, keySet);
return keySet;
}
public static void main(String[] args){
AVL<Integer, String> tree = new AVL<>();
Random random = new Random();
for (int i = 0; i < 500; ++i)
tree.put(random.nextInt(), "naoko" + i);
tree.deleteMax();
tree.deleteMin();
for (int i : tree.keySet())
System.out.println(i);
System.out.println("符号表的大小：" + tree.size());
}
}