6.1 AVL 树与旋转
普通 BST 只维护顺序，不限制形状。本节给节点补上高度，从一棵被有序输入压弯的树开始，逐步推到四种旋转、完整 AVL 插入和不变量验证。
1. 有序输入为什么会把 BST 压成链
按顺序插入 1, 2, 3, 4, 5，每个非叶节点都只剩右孩子：
1 -> 2 -> 3 -> 4 -> 5第五章把操作成本归结为树高。这里改用节点数记录高度：
- 空树高度为
0； - 叶节点高度为
1； - 节点高度为
1 + max(左高, 右高)。
上一章用边数定义高度。对非空树，两种值相差 1，不会改变渐进复杂度。最容易出错的做法，是在同一份代码里混用两种约定。
顺序插入 n 个键后，普通 BST 的节点高度是 n，所以查找末尾键要走 n 个节点。AVL 给每个节点增加一条局部要求：
abs(height(left) - height(right)) <= 1为什么局部条件能限制整棵树？设高度为 h 的 AVL 树最少有 N(h) 个节点。为了在节点尽量少时达到高度 h，两棵子树分别取高度 h-1 和 h-2：
N(0) = 0, N(1) = 1
N(h) = 1 + N(h-1) + N(h-2) (h >= 2)
N(h): 0, 1, 2, 4, 7, 12, ...这个递推像斐波那契数列一样指数增长，所以高度只能随节点数对数增长。非空树上沿一条路径的操作因此是 O(log(n+1))，空树操作为常数成本。可结合 MIT 的 AVL 讲义继续推导。
2. 平衡因子告诉我们往哪边修
定义：
balance(node) = height(node.left) - height(node.right)| 平衡因子 | 含义 |
|---|---|
1 | 左边高一层，仍合法 |
0 | 两边等高 |
-1 | 右边高一层，仍合法 |
>= 2 | 左侧失衡 |
<= -2 | 右侧失衡 |
“左侧失衡”还不够决定旋转。新键可能落在左孩子的左侧，也可能落在左孩子的右侧；这就是 LL 与 LR 的区别。
3. 一次旋转改了哪些连接
右旋
y x
/ \ / \
x T3 --> T1 y
/ \ / \
T1 T2 T2 T3执行顺序：
- 保存
x.right，也就是T2。 - 让
x.right指向旧根y。 - 让
y.left接回T2。 - 先更新
y.height，再更新x.height。
第四步的顺序有依赖：旋转后 y 已是 x 的孩子。先算 x 会读到 y 的旧高度。
中序遍历可以证明旋转没有破坏 BST 顺序：
旋转前：T1, x, T2, y, T3
旋转后：T1, x, T2, y, T3左旋
左旋把上图镜像：提升右孩子，把它的左子树交给旧根的右指针。连接和高度更新的依赖关系相同。右旋要求左孩子存在，左旋要求右孩子存在；下面的内部方法由失衡分支保证这些前提。
4. 四种失衡逐个看
名称从失衡节点向下读两步。
LL：[30, 20, 10]
30 20
/ / \
20 --> 10 30
/
1030 左高两层，新键又在左孩子 20 的左侧。一轮右旋即可。
RR：[10, 20, 30]
10 20
\ / \
20 --> 10 30
\
30它与 LL 对称，一轮左旋即可。
LR：[30, 10, 20]
30 30 20
/ / / \
10 --> 20 --> 10 30
\ /
20 10先把左孩子内部的折角拉直，LR 就变成 LL；再右旋失衡节点。
RL：[10, 30, 20]
10 10 20
\ \ / \
30 --> 20 --> 10 30
/ \
20 30它与 LR 对称。
一个实用判断法：先看失衡节点偏左还是偏右，再看较高孩子内部偏向哪边。不要根据新键与根的一次比较猜名称。
5. 完整 AVL 插入
下面的实现保存唯一整数键。insert() 返回是否插入了新键；重复键返回 False。输入先检查 int 类型，避免 NaN 既不小于也不大于已有 key 时被误当成重复键。验证器递归检查上下界、存储高度和平衡因子；bool 在 Python 中也是 int 的子类，因此沿用 True == 1 的集合语义。
def require_int_key(key):
if not isinstance(key, int):
raise TypeError("key must be an integer")
class AVLNode:
def __init__(self, key):
require_int_key(key)
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
self.size = 0
@staticmethod
def _height(node):
return 0 if node is None else node.height
def _update(self, node):
node.height = 1 + max(self._height(node.left), self._height(node.right))
def _balance(self, node):
return self._height(node.left) - self._height(node.right)
def _rotate_right(self, old_root):
new_root = old_root.left
middle = new_root.right
new_root.right = old_root
old_root.left = middle
self._update(old_root)
self._update(new_root)
return new_root
def _rotate_left(self, old_root):
new_root = old_root.right
middle = new_root.left
new_root.left = old_root
old_root.right = middle
self._update(old_root)
self._update(new_root)
return new_root
def _insert(self, node, key):
if node is None:
return AVLNode(key), True
if key < node.key:
node.left, inserted = self._insert(node.left, key)
elif key > node.key:
node.right, inserted = self._insert(node.right, key)
else:
return node, False
self._update(node)
balance = self._balance(node)
if balance > 1:
if key > node.left.key: # LR
node.left = self._rotate_left(node.left)
return self._rotate_right(node), inserted # LL / LR
if balance < -1:
if key < node.right.key: # RL
node.right = self._rotate_right(node.right)
return self._rotate_left(node), inserted # RR / RL
return node, inserted
def insert(self, key):
require_int_key(key)
self.root, inserted = self._insert(self.root, key)
if inserted:
self.size += 1
return inserted
def inorder(self):
result = []
def walk(node):
if node is None:
return
walk(node.left)
result.append(node.key)
walk(node.right)
walk(self.root)
return result
def height(self):
return self._height(self.root)
def is_valid(self):
def check(node, low, high):
if node is None:
return True, 0
if (low is not None and node.key <= low) or (
high is not None and node.key >= high
):
return False, 0
left_ok, left_height = check(node.left, low, node.key)
right_ok, right_height = check(node.right, node.key, high)
expected = 1 + max(left_height, right_height)
valid = (
left_ok
and right_ok
and node.height == expected
and abs(left_height - right_height) <= 1
)
return valid, expected
valid, _ = check(self.root, None, None)
return valid
rotation_cases = {
"LL": [30, 20, 10],
"RR": [10, 20, 30],
"LR": [30, 10, 20],
"RL": [10, 30, 20],
}
for name, values in rotation_cases.items():
tree = AVLTree()
for value in values:
assert tree.insert(value)
assert tree.root.key == 20, name
assert tree.inorder() == [10, 20, 30], name
assert tree.height() == 2, name
assert tree.is_valid(), name
ordered = AVLTree()
for value in range(1, 101):
ordered.insert(value)
assert ordered.inorder() == list(range(1, 101))
assert ordered.height() == 7
assert ordered.is_valid()
assert ordered.insert(50) is False
assert ordered.size == 1006. 为什么插入修一次就够
递归插入从叶子返回根时，会逐个更新路径上的高度。遇到第一个失衡祖先后，单旋或双旋把这一小段子树恢复到插入前的高度。更高祖先看到的子树高度没有继续增长，因此不需要再旋转。
所以 AVL 插入的行为是：
- 沿路径搜索和更新，
O(h)； - 在一个失衡祖先处完成修复；
- 单旋用一次基础旋转，双旋用两次。
删除的修复范围不能照搬插入。删除会让子树变矮，修复后高度还可能继续下降，更高祖先也可能失衡。因此 AVL 删除可能在多个祖先处旋转，但总工作仍是 O(log n)。Amani、Lai 与 Tarjan 的论文讨论了这种旋转成本差异。
7. 验证器比看图可靠
一棵树看起来对称，不代表元数据和顺序都正确。is_valid() 要验证：
- 每个键都在祖先传下来的开区间中，而不只比较直接孩子。
- 实际算出的高度等于节点保存的
height。 - 每个节点的左右实际高度差不超过 1。
如果只检查第三项，错误的存储高度可能长期潜伏；如果只比较父子 key，深层节点越过祖先边界也会漏掉。
验证器假定左右链接无环，也没有共享孩子；它不会替任意损坏的对象图兜底。此外，本实现不在验证器中核对 size，需要另行检查 len(tree.inorder()) == tree.size。
8. 常见故障
T2 消失
旋转时直接覆盖孩子指针，没有先保存中间子树。中序遍历会少一段键。
高度更新次序反了
新根依赖旧根的新高度。先更新新根会把旧值带进后续平衡判断。
用新键判断删除后的旋转
插入时可以利用新键所在方向区分四种形状。删除后那个键已经不存在，应改为检查较高孩子自身的平衡因子。
重复键悄悄增加 size
本章沿用第五章的集合语义。递归层返回 inserted=False 后，公开方法不能增加计数。
9. 复杂度速查
| 操作 | 时间 | 额外空间 |
|---|---|---|
| 搜索 | O(log n) | 迭代 O(1)；递归 O(log n) |
| 插入 | O(log n) | 本实现递归栈 O(log n) |
| 一次旋转 | O(1) | O(1) |
| 中序遍历 | O(n) | 辅助栈 O(log(n+1))，另有 Θ(n) 输出列表 |
| 完整验证 | O(n) | O(h+1)，按待检树实际高度计 |
表中把 key 比较按常数成本计；大整数比较还要计入位数。对合法非空 AVL 树，h=O(log(n+1))；空树操作为常数成本。验证器面对失衡树时，递归栈却可能达到 O(n)，不能先假定待检对象已通过验证。
示例提供插入、遍历和验证；搜索可复用上一章的 BST 路径。height() 直接读取缓存，为 O(1)。删除的复杂度描述对应完整 AVL 算法，本页没有实现删除。
10. 动手验证旋转与高度
- 不看表格，画出
[50, 30, 40]的失衡类型和两次旋转。 - 给右旋图中的
T2放入键17，令x=15、y=20，验证旋转前后顺序。 - 手动把示例树根的
height加 1，确认is_valid()返回False。 - 解释为什么 AVL 插入最多修一个失衡祖先，而删除可能继续向上。
从精确高度转向颜色约束
下一种平衡树不保存精确高度，而用颜色与黑高度约束形状。继续进入红黑树。