01先把问题说具体
普通 BST 连续插入 3、2、1 会变成链。怎样保持搜索顺序,同时把高度恢复到对数级?
02一步步得到方法
局部高度约束带来全局保证
AVL 要求每个节点左右子树高度差的绝对值≤1。本课空树高度 0,叶子 1,平衡因子 balance=h(left)−h(right)。插入先像 BST 一样落到叶子,再沿返回路径更新高度并修复。
高度为 h 的 AVL 至少包含 N(h)=1+N(h−1)+N(h−2) 个节点,按 Fibonacci 速度增长。反过来固定 n 时 h=O(log n),这才是对数查询的依据。
旋转移动连接,不改变中序
左侧太高且左孩子也左高时,对根右旋。设根 z、左孩子 y、y 的右子树 B;将 y 提为根,z 成为 y 的右孩子,B 接到 z 的左侧。键仍满足 A<y<B<z<C。
若左侧太高但新节点落在左孩子的右侧,先对左孩子左旋,把折线变直,再对根右旋。右侧情况镜像得到 RR、RL;四种情形是插入路径的两个方向组合。
高度更新顺序不能反
旋转后原根先变成孩子,因此先更新原根高度,再更新新根高度。调用者必须接住旋转返回的新子树根,否则结构虽然在局部变了,父节点仍指向旧根。删除也需沿路径修复,且可能持续影响多个祖先;本课代码聚焦完整插入。
03把一个小例子完全算清楚
依次插入 3、2、1。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 插入 3、2 | 根 3 高度 2,balance=1 | 仍合法 |
| 插入 1 | 根 3 的 balance=2 | 左左失衡 |
| 右旋 3 | 新根 2,左右孩子 1、3 | 中序仍 [1,2,3] |
| 更新高度 | 1、3 高度 1;2 高度 2 | 恢复平衡 |
窄屏可左右滑动表格,阅读完整计算与理由。
右旋不是交换两个值,而是重新连接整棵局部子树。
04为什么这个方法成立
- BST 插入保持键序,只可能改变插入路径上的高度。
- 旋转保留局部中序,因此保留搜索性质。
- 单旋或双旋修复当前失衡;回溯逐层检查后,每个节点均满足高度差约束。
05把推导翻译成代码
Python · 可独立运行的教学实现
class Node:
def __init__(self, key):
self.key, self.left, self.right, self.height = key, None, None, 1
def height(t):
return t.height if t else 0
def update(t):
t.height = 1 + max(height(t.left), height(t.right))
def rotate_right(z):
y, middle = z.left, z.left.right
y.right, z.left = z, middle
update(z); update(y)
return y
def rotate_left(z):
y, middle = z.right, z.right.left
y.left, z.right = z, middle
update(z); update(y)
return y
def insert(t, key):
if t is None:
return Node(key)
if key < t.key:
t.left = insert(t.left, key)
elif key > t.key:
t.right = insert(t.right, key)
else:
return t
update(t)
balance = height(t.left) - height(t.right)
if balance > 1:
if key > t.left.key:
t.left = rotate_left(t.left)
return rotate_right(t)
if balance < -1:
if key < t.right.key:
t.right = rotate_right(t.right)
return rotate_left(t)
return t逐个理解关键决定
update(z); update(y)- 先更新降下去的旧根,再更新升上来的新根。
t.left = rotate_left(t.left)- LR 先修孩子方向,再进行根右旋。
return rotate_right(t)- 旋转后的新根必须向上一层返回。
06时间、空间与实现范围
每个祖先做常数次检查和旋转,插入 O(log n),查询 O(log n)。
节点额外保存高度,树存储 O(n),递归插入栈 O(log n)。
07改变条件,检查哪里会出错
只把根的平衡因子检查一遍
内部子树也必须平衡;沿插入路径从下到上修复。
四种旋转条件直接用于删除
删除时子树形态判断不同,不能用被删 key 的比较套入插入分支。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
插入 3、1、2 应做什么?
需要一点提示
左孩子右侧变高。
查看解析与答案
LR:先左旋节点 1,再右旋节点 3,得到根 2、孩子 1 和 3。
旋转后中序为什么不变?
需要一点提示
写出 A,y,B,z,C 的次序。
查看解析与答案
两种结构中序都为 A,y,B,z,C,B 只改变父节点,不改变键值区间。
为什么不每次重新递归计算整棵子树高度?
需要一点提示
重复扫描代价。
查看解析与答案
会增加重复工作;缓存高度并在局部更新,让每个回溯节点的检查保持 O(1)。