AVL的起源
AVL 并不是一个缩写词，而是取自它的两位前苏联发明者：G.M. Adelson-Velsky 和 E.M. Landis。他们在 1962 年的论文中首次提出了这种结构。这是历史上第一种自平衡二叉搜索树。在那个内存以 KB 计算的年代，如何高效利用存储空间和计算周期是生死攸关的大事。
要解决的核心问题：防止二叉树“降级”
我们在之前的二叉树中已经看到了：当插入数据趋于有序（如 1, 2, 3, 4）时，树会不可避免地退化成一个链表。这种普通 BST 的性能完全取决于输入数据的运气。AVL 的使命就是无论你按什么顺序输入，它都要通过 “强力整形”，即所谓的 旋转，确保查找的时间复杂度死死锁定在 $O(\log n)$。
核心原理：极度均衡的平衡因子
AVL 树的灵魂在于它对 “平衡” 的严苛定义。
① 平衡因子（Balance Factor, BF）
每一个节点现在多了一个属性，叫做平衡因子：$BF = \text{Height(Left Subtree)} - \text{Height(Right Subtree)}$
AVL 的铁律：每一个节点的 $|BF|$ 必须 $\le 1$。也就是说，左子树和右子树的高度差，最多只能是 1。一旦变成 2，树就会立刻触发 “警报”，开始自我调整。
② 四种失衡场景与四大招式
为了维持这个 $BF \le 1$ 的铁律，AVL 总结出了四种 “长歪” 的情况，并对应了四种手术方案：
AVL的优缺点
AVL 树就像一个有强迫症的整理控。它的最大优点是其构建的二叉树极度平衡，查找速度是所有BST中最快的。这种为了维持这种 “绝对平衡”，每次插入或删除节点时，都可能引发从下往上的一连串旋转，导致 写入性能 略有下降。这就是为什么后来出现了 “红黑树” 的原因，红黑树放宽了平衡的要求，在树的均衡和写入效率之间寻找到了最佳的平衡。
旋转的过程
想象三个节点：10 → 20 → 30（连成了一条向右下的直线）。
- 失衡感：10 觉得右边太沉了。
- 动作：我们抓住 20，把它往上提。
- 发生的位移：20 升官变成了新的最高领导；10 降级变成了 20 的左孩子；30 没动依然是 20 的右孩子，只是跟着 20 一起往上挪了一位。
结果原本 3 层的 “长棍子”，变成了以 20 为中心的 “人字形” 结构。
旋转里最容易让人糊涂的是：如果被提拔的那个孩子，原本就有自己的孩子怎么办？比如 20 原本有一个左孩子 15。现在 20 要晋升取代 10 的位置 15 该往哪放？解决方式如下：
- 20 要变成 10 的新领导，它的左手必须腾出来拉住 10。
- 20 就把 15 这个包袱甩给了 10。
为什么能甩呢？这是因为 15 本来就在 20 的左边（比 20 小），且在 10 的右边（比 10 大）。所以把它挂在 10 的右边，完美符合 “左小右大 ” 的规则。这就是代码里 x.right = y.left 的含义：原来父节点下台前，接手了新的父节点腾出手时丢下的子节点。你可以把旋转的过程总结成下面的四个字：
- 提：把重的那个孩子往上提。
- 降：把原来的父节点往下拉。
- 甩：把多出来的子树像包袱一样甩给降级的父节点。
- 平：原本倾斜的天平，瞬间就拉平了。
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
|
private TreeNode leftRotate(TreeNode x) {
TreeNode y = x.right;
TreeNode temp = y.left;
y.left = x;
x.right = temp;
updateHeight(x);
updateHeight(y);
return y;
}
private TreeNode rightRotate(TreeNode y) {
TreeNode x = y.left;
TreeNode temp = x.right;
x.right = y;
y.left = temp;
updateHeight(y);
updateHeight(x);
return x;
}
|
完整的代码实现
AVL 树的生成过程交互演示：
下面是一个完整的 ALV 插入、查找、遍历的示例：
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
|
public class MyAVL {
private TreeNode root;
public static class TreeNode {
int value;
int height;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.value = value;
this.height = 1;
}
}
private void updateHeight(TreeNode node) {
if (node != null) {
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
}
private int getHeight(TreeNode node) {
return node == null ? 0 : node.height;
}
private int getBalanceFactor(TreeNode node) {
return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
}
private TreeNode rightRotate(TreeNode y) {
TreeNode x = y.left;
TreeNode temp = x.right;
x.right = y;
y.left = temp;
updateHeight(y);
updateHeight(x);
return x;
}
private TreeNode leftRotate(TreeNode x) {
TreeNode y = x.right;
TreeNode temp = y.left;
y.left = x;
x.right = temp;
updateHeight(x);
updateHeight(y);
return y;
}
public void insert(int value) {
this.root = insert(this.root, value);
}
private TreeNode insert(TreeNode curRoot, int value) {
if (curRoot == null) {
return new TreeNode(value);
}
if (value < curRoot.value) {
curRoot.left = insert(curRoot.left, value);
} else if (value > curRoot.value) {
curRoot.right = insert(curRoot.right, value);
} else {
return curRoot;
}
updateHeight(curRoot);
int balance = getBalanceFactor(curRoot);
if (balance > 1 && value < curRoot.left.value) {
return rightRotate(curRoot);
}
if (balance < -1 && value > curRoot.right.value) {
return leftRotate(curRoot);
}
if (balance > 1 && value > curRoot.left.value) {
curRoot.left = leftRotate(curRoot.left);
return rightRotate(curRoot);
}
if (balance < -1 && value < curRoot.right.value) {
curRoot.right = rightRotate(curRoot.right);
return leftRotate(curRoot);
}
return curRoot;
}
public boolean search(int value) {
TreeNode curRoot = this.root;
while (curRoot != null) {
if (value == curRoot.value) return true;
curRoot = value < curRoot.value ? curRoot.left : curRoot.right;
}
return false;
}
public void printTree() {
printTree(root, 0);
}
private void printTree(TreeNode node, int level) {
if (node == null) {
return;
}
printTree(node.right, level + 1);
if (level == 0) {
System.out.println(node.value + "[" + node.height + "]");
} else {
String subPrefix = "| ".repeat(level - 1);
System.out.println(subPrefix + "|---" + node.value + "[" + node.height + "]");
}
printTree(node.left, level + 1);
}
public static void main(String[] args) {
MyAVL avl = new MyAVL();
int[] values = {10, 20, 30, 40, 50, 25};
for (int value : values) {
avl.insert(value);
}
avl.printTree();
System.out.println(avl.search(25));
System.out.println(avl.search(90));
}
}
|
测试结果：
1
2
3
4
5
6
7
8
| | |---50[1]
|---40[2]
30[3]
| |---25[1]
|---20[2]
| |---10[1]
true
false
|