一、AVL 树
在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log(n))。插入和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
大多数 BST 操作（例如，搜索，最大，最小，插入，删除等）花费 O(h) 时间，其中 h 是 BST 的高度。对于偏斜的二叉树，这些操作的成本可能变为 O(n)。如果确保每次插入和删除后树的高度都保持 O(log2n)，则可以保证所有这些操作的 O(log2n)上限。AVL树的高度始终为 O(log2n)，其中 n 是树中的节点数。
二、AVL 树的旋转
AVL 树在普通的插入和删除节点时都会使得树失去平衡，这时我们需要一些操作来把树恢复平衡，这些操作叫做AVL树的旋转，分为左旋和右旋。
T1，T2 和 T3 是树 y(左边) 或 x(右边) 的子树：
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
以上两个树中的键都遵循以下顺序（二叉查找树的性质）：
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)。
1 /**
2 * 右旋转以y为根的子树
3 *
4 * @param y
5 * @return
6 */
7 private Node rightRoate(Node y) {
8 Node x = y.left;
9 Node T2 = x.right;
10
11 /* 执行旋转 */
12 x.right = y;
13 y.left = T2;
14
15 /* 更新高度 */
16 y.height = max(height(y.left), height(y.right)) + 1;
17 x.height = max(height(x.left), height(x.right)) + 1;
18
19 return x;
20 }
21
22 /**
23 * 左旋转以x为根的子树
24 *
25 * @param x
26 * @return
27 */
28 private Node leftRoate(Node x) {
29 Node y = x.right;
30 Node T2 = y.left;
31
32 /* 执行旋转 */
33 y.left = x;
34 x.right = T2;
35
36 /* 更新高度 */
37 x.height = max(height(x.left), height(x.right)) + 1;
38 y.height = max(height(y.left), height(y.right)) + 1;
39
40 return y;
41 }
三、AVL 树的插入操作
插入要遵循的步骤：
新插入的节点为 w
1）对 w 执行标准 BST 插入。
2）从 w 开始，向上移动并找到第一个不平衡节点。令 z 为第一个不平衡节点，y 为从 w 到 z 的路径中 z 的子代，x 为从 w 到 z 的路径中 z 的孙代。
3）通过对以 z 为根的子树执行适当的旋转来重新平衡树。可能有 4 种可能的情况需要处理，因为 x，y 和 z 可以 4 种方式排列。以下是可能的 4 种排列方式：
a）y 是 z 的左子代，x 是 y 的左子代（左案例）
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
b）y 是 z 的左子代，x 是 y 的右子代（左案例）
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
c）y 是 z 的右子代，x 是 y 的右子代（右右案例）
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
d）y 是 z 的右子代，x 是 y 的左子代（右左案例）
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
插入操作：
1 /**
2 * AVL树的插入
3 *
4 * @param node
5 * @param key
6 * @return
7 */
8 private Node insert(Node node, int key) {
9 /* 执行正常的BST插入 */
10 if (node == null)
11 return (new Node(key));
12
13 if (key < node.key)
14 node.left = insert(node.left, key);
15 else if (key > node.key)
16 node.right = insert(node.right, key);
17 else // 不允许重复的key
18 return node;
19
20 /* 更新此祖先节点的高度 */
21 node.height = 1 + max(height(node.left), height(node.right));
22
23 /* 获取此祖先的平衡因子以检查此节点是否变为不平衡 */
24 int balance = getBalance(node);
25
26 /* 如果此节点变得不平衡，则存在有4种情况 */
27 if (balance > 1 && key < node.left.key) {
28 return rightRoate(node);
29 }
30
31 if (balance < -1 && key > node.right.key) {
32 return leftRoate(node);
33 }
34
35 if (balance > 1 && key > node.left.key) {
36 node.left = leftRoate(node.left);
37 return rightRoate(node);
38 }
39
40 if (balance < -1 && key < node.right.key) {
41 node.right = rightRoate(node.right);
42 return leftRoate(node);
43 }
44
45 return node;
46 }
四、AVL 树的删除操作
删除要遵循的步骤：
令 w 为要删除的节点
1）对 w 执行标准BST删除。
2）从 w 开始，向上移动并找到第一个不平衡节点。令 z 为第一个不平衡节点，y 为 z 的较大孩子，x 为 y 的较大孩子。请注意，x 和 y 的定义与此处的插入不同。
3）通过对以 z 为根的子树执行适当的旋转来重新平衡树。有 4 种可能的情况需要处理，因为 x，y 和 z 可以 4 种方式排列。以下是可能的 4 种排列方式：
a）y 是 z 的左子代，x是y的左子代（左案例）
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
b）y 是 z 的左子代，x 是 y 的右子代（左案例）
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
c）y 是 z 的右子代，x 是 y 的右子代（右右案例）
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
d）y 是 z 的右子代，x 是 y 的左代子（右左案例）
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
与插入不同，在删除中，在 z 处进行旋转后，可能必须在 z 的祖先处进行旋转。因此，我们必须继续追踪路径，直到到达根为止。
删除操作：
1 /**
2 * AVL树的删除
3 *
4 * @param N
5 * @return
6 */
7 private Node deleteNode(Node root, int key) {
8 if (root == null)
9 return root;
10 /* 如果要删除的key小于root的key，则它位于左子树中 */
11 if (key < root.key)
12 root.left = deleteNode(root.left, key);
13
14 /* 如果要删除的key大于root的key，则它位于右子树中 */
15 else if (key > root.key)
16 root.right = deleteNode(root.right, key);
17
18 /* 如果key与root的key相同，则这个节点要被删除 */
19 else {
20 /* 只有一个孩子或没有孩子的节点 */
21 if ((root.left == null) || (root.right == null)) {
22 Node temp = null;
23 if (temp == root.left)
24 temp = root.right;
25 else
26 temp = root.left;
27
28 /* 没有孩子的情况 */
29 if (temp == null) {
30 temp = root;
31 root = null;
32 } else { // 只有一个孩子
33 root = temp; // 复制非空孩子的内容
34 }
35
36 } else {
37 /* 有两个子节点的节点：获取后继节点（在右侧子树中最小） */
38 Node temp = minValueNode(root.right);
39 /* 将后继节点的数据复制到此节点 */
40 root.key = temp.key;
41 /* 删除后继节点 */
42 root.right = deleteNode(root.right, temp.key);
43 }
44 }
45
46 /* 如果树只有一个节点，则返回 */
47 if (root == null)
48 return root;
49
50 /* 更新当前节点的高度 */
51 root.height = max(height(root.left), height(root.right)) + 1;
52 /* 获取此节点的平衡因素 */
53 int balance = getBalance(root);
54
55 /* 如果此节点变得不平衡，则有4种情况 */
56 if (balance > 1 && getBalance(root.left) >= 0) {
57 return rightRoate(root);
58 }
59
60 if (balance > 1 && getBalance(root.left) < 0) {
61 root.left = leftRoate(root.left);
62 return rightRoate(root);
63 }
64
65 if (balance < -1 && getBalance(root.right) <= 0) {
66 return leftRoate(root);
67 }
68
69 if (balance < -1 && getBalance(root.right) > 0) {
70 root.right = rightRoate(root.right);
71 return leftRoate(root);
72 }
73
74 return root;
75 }
本文源代码：
1 package algorithm;
2
3 /**
4 * 自平衡二叉树，左右子树的高度差不大于1
5 */
6 public class AVLTree {
7
8 private Node root;
9
10 /**
11 * 树高度
12 *
13 * @param N
14 * @return
15 */
16 private int height(Node N) {
17 if (N == null) {
18 return 0;
19 }
20 return N.height;
21 }
22
23 private int max(int a, int b) {
24 return Math.max(a, b);
25 }
26
27 /**
28 * 右旋转以y为根的子树
29 *
30 * @param y
31 * @return
32 */
33 private Node rightRoate(Node y) {
34 Node x = y.left;
35 Node T2 = x.right;
36
37 /* 执行旋转 */
38 x.right = y;
39 y.left = T2;
40
41 /* 更新高度 */
42 y.height = max(height(y.left), height(y.right)) + 1;
43 x.height = max(height(x.left), height(x.right)) + 1;
44
45 return x;
46 }
47
48 /**
49 * 左旋转以x为根的子树
50 *
51 * @param x
52 * @return
53 */
54 private Node leftRoate(Node x) {
55 Node y = x.right;
56 Node T2 = y.left;
57
58 /* 执行旋转 */
59 y.left = x;
60 x.right = T2;
61
62 /* 更新高度 */
63 x.height = max(height(x.left), height(x.right)) + 1;
64 y.height = max(height(y.left), height(y.right)) + 1;
65
66 return y;
67 }
68
69 /**
70 * 获取N结点的平衡
71 *
72 * @param N
73 * @return
74 */
75 private int getBalance(Node N) {
76 if (N == null)
77 return 0;
78
79 return height(N.left) - height(N.right);
80 }
81
82 /**
83 * AVL树的插入
84 *
85 * @param node
86 * @param key
87 * @return
88 */
89 private Node insert(Node node, int key) {
90 /* 执行正常的BST插入 */
91 if (node == null)
92 return (new Node(key));
93
94 if (key < node.key)
95 node.left = insert(node.left, key);
96 else if (key > node.key)
97 node.right = insert(node.right, key);
98 else // 不允许重复的key
99 return node;
100
101 /* 更新此祖先节点的高度 */
102 node.height = 1 + max(height(node.left), height(node.right));
103
104 /* 获取此祖先的平衡因子以检查此节点是否变为不平衡 */
105 int balance = getBalance(node);
106
107 /* 如果此节点变得不平衡，则存在有4种情况 */
108 if (balance > 1 && key < node.left.key) {
109 return rightRoate(node);
110 }
111
112 if (balance < -1 && key > node.right.key) {
113 return leftRoate(node);
114 }
115
116 if (balance > 1 && key > node.left.key) {
117 node.left = leftRoate(node.left);
118 return rightRoate(node);
119 }
120
121 if (balance < -1 && key < node.right.key) {
122 node.right = rightRoate(node.right);
123 return leftRoate(node);
124 }
125
126 return node;
127 }
128
129 /**
130 * 给定一个非空的二叉查找树，返回树中最小key值的结点（注意无需遍历整个树）
131 *
132 * @param node
133 * @return
134 */
135 private Node minValueNode(Node node) {
136 Node current = node;
137
138 while (current.left != null)
139 current = current.left;
140
141 return current;
142 }
143
144 /**
145 * AVL树的删除
146 *
147 * @param N
148 * @return
149 */
150 private Node deleteNode(Node root, int key) {
151 if (root == null)
152 return root;
153 /* 如果要删除的key小于root的key，则它位于左子树中 */
154 if (key < root.key)
155 root.left = deleteNode(root.left, key);
156
157 /* 如果要删除的key大于root的key，则它位于右子树中 */
158 else if (key > root.key)
159 root.right = deleteNode(root.right, key);
160
161 /* 如果key与root的key相同，则这个节点要被删除 */
162 else {
163 /* 只有一个孩子或没有孩子的节点 */
164 if ((root.left == null) || (root.right == null)) {
165 Node temp = null;
166 if (temp == root.left)
167 temp = root.right;
168 else
169 temp = root.left;
170
171 /* 没有孩子的情况 */
172 if (temp == null) {
173 temp = root;
174 root = null;
175 } else { // 只有一个孩子
176 root = temp; // 复制非空孩子的内容
177 }
178
179 } else {
180 /* 有两个子节点的节点：获取后继节点（在右侧子树中最小） */
181 Node temp = minValueNode(root.right);
182 /* 将后继节点的数据复制到此节点 */
183 root.key = temp.key;
184 /* 删除后继节点 */
185 root.right = deleteNode(root.right, temp.key);
186 }
187 }
188
189 /* 如果树只有一个节点，则返回 */
190 if (root == null)
191 return root;
192
193 /* 更新当前节点的高度 */
194 root.height = max(height(root.left), height(root.right)) + 1;
195 /* 获取此节点的平衡因素 */
196 int balance = getBalance(root);
197
198 /* 如果此节点变得不平衡，则有4种情况 */
199 if (balance > 1 && getBalance(root.left) >= 0) {
200 return rightRoate(root);
201 }
202
203 if (balance > 1 && getBalance(root.left) < 0) {
204 root.left = leftRoate(root.left);
205 return rightRoate(root);
206 }
207
208 if (balance < -1 && getBalance(root.right) <= 0) {
209 return leftRoate(root);
210 }
211
212 if (balance < -1 && getBalance(root.right) > 0) {
213 root.right = rightRoate(root.right);
214 return leftRoate(root);
215 }
216
217 return root;
218 }
219
220 /**
221 * 先序遍历
222 *
223 * @param node
224 */
225 private void preOrder(Node node) {
226 if (node != null) {
227 System.out.print(node.key + " ");
228 preOrder(node.left);
229 preOrder(node.right);
230 }
231 }
232
233 public static void main(String[] args) {
234
235 /* ---------------------------------------------------- */
236
237 AVLTree tree = new AVLTree();
238
239 /* 构造AVL树 */
240 tree.root = tree.insert(tree.root, 9);
241 tree.root = tree.insert(tree.root, 5);
242 tree.root = tree.insert(tree.root, 10);
243 tree.root = tree.insert(tree.root, 0);
244 tree.root = tree.insert(tree.root, 6);
245 tree.root = tree.insert(tree.root, 11);
246 tree.root = tree.insert(tree.root, -1);
247 tree.root = tree.insert(tree.root, 1);
248 tree.root = tree.insert(tree.root, 2);
249
250 /* 构造的AVL树：
251 9
252 / \
253 1 10
254 / \ \
255 0 5 11
256 / / \
257 -1 2 6
258 */
259 System.out.println("Preorder traversal of constructed tree is : ");
260 tree.preOrder(tree.root);
261
262 tree.root = tree.deleteNode(tree.root, 10);
263
264 /* 删除10后的AVL树：
265 1
266 / \
267 0 9
268 / / \
269 -1 5 11
270 / \
271 2 6
272 */
273 System.out.println();
274 System.out.println("Preorder traversal after "+
275 "deletion of 10 :");
276 tree.preOrder(tree.root);
277 }
278 }
279
280 class Node {
281 int key, height;
282 Node left, right;
283
284 Node(int d) {
285 key = d;
286 height = 1;
287 }
288
289 }
View Code