01先把问题说具体
AVL 严格控制高度差。能否用更宽松的局部规则,仍保证最坏对数高度?
02一步步得到方法
颜色记录的是结构约束
标准红黑约束包括:节点红或黑,根黑,空叶视为黑,红节点不能有红孩子,从任一节点到各空叶的黑节点数相同。我们称最后一个数量为黑高。
最长路径最多交替红黑,最短路径至少包含相同数量的黑节点,因此最长不超过最短的两倍;结合每层分支结构可得到 O(log n) 高度。颜色不是数据优先级。
本课选定左倾红黑树,而非混用版本
左倾红黑树 LLRB 额外要求红链接向左倾斜,可把红链接看成将两个 BST 节点合成一个 2–3 树节点。插入新叶先染红,因为这不会立即增加路径黑高。
回溯时三步修复:右红左不红则左旋;左红且左左红则右旋;左右都红则翻转颜色。最后把整树根染黑。这里规则的顺序属于本插入版本,不能与另一套标准红黑删除修复表随意拼接。
旋转还必须转移颜色
旋转不仅改链接,新根继承旧根颜色,降下去的旧根染红,这样保持穿过局部结构的黑高。颜色翻转相当于拆分临时四节点,把红连接向父亲上传;父亲若冲突,回溯继续修复。
03把一个小例子完全算清楚
插入键 1、2、3。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 插入 1 | 根 1 染黑 | 合法单节点 |
| 插入 2 | 右红,左旋为根 2,左孩子 1 红 | 消除右倾 |
| 插入 3 | 左右孩子均红 | 准备颜色翻转 |
| 翻转并根染黑 | 根 2 黑,孩子 1、3 黑 | 各路径黑高一致 |
窄屏可左右滑动表格,阅读完整计算与理由。
插入用颜色暂存需要向上合并的信息;最终结构仍然满足 BST 键序。
04为什么这个方法成立
- 普通插入与旋转保持中序顺序。
- 新红叶、带颜色转移的旋转和翻色保持局部路径黑高相等。
- 回溯消除右红与连续左红,根置黑,得到左倾红黑不变量;代码只涵盖插入,删除有独立修复过程。
05把推导翻译成代码
Python · 可独立运行的教学实现
class Node:
def __init__(self, key):
self.key, self.left, self.right, self.red = key, None, None, True
def red(t):
return t is not None and t.red
def left(h):
x = h.right
h.right, x.left = x.left, h
x.red, h.red = h.red, True
return x
def right(h):
x = h.left
h.left, x.right = x.right, h
x.red, h.red = h.red, True
return x
def put(h, key):
if h is None:
return Node(key)
if key < h.key:
h.left = put(h.left, key)
elif key > h.key:
h.right = put(h.right, key)
if red(h.right) and not red(h.left):
h = left(h)
if red(h.left) and red(h.left.left):
h = right(h)
if red(h.left) and red(h.right):
h.red = not h.red
h.left.red = not h.left.red
h.right.red = not h.right.red
return h
def insert(root, key):
root = put(root, key)
root.red = False
return root逐个理解关键决定
x.red, h.red = h.red, True- 旋转转移原根颜色,维持经过该局部的黑节点数。
root.red = False- 根上方没有父链接,可以把上传的红色吸收为全树统一增加的黑高。
06时间、空间与实现范围
高度 O(log n),查找与插入 O(log n),存储 O(n)。颜色只需常数附加信息。
本实现是集合,重复键不新增节点;未实现删除,不能将 put 当作完整容器 API。
07改变条件,检查哪里会出错
把红黑平衡理解为左右节点数一样
只控制路径黑高与红色连续性,不要求子树等大。
只旋转链接不处理颜色
可能保持 BST 却破坏黑高,仍是错误红黑树。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
红节点能有黑孩子吗?
需要一点提示
禁止的是红红相邻。
查看解析与答案
可以,而且它的非空孩子必须黑;空叶也视为黑。
为什么新叶不直接染黑?
需要一点提示
只增加一条路径的黑节点。
查看解析与答案
会破坏该路径与兄弟路径的黑高一致性,修复更困难。
如何验证实现而非只看中序有序?
需要一点提示
还要检查颜色不变量。
查看解析与答案
检查根黑、无红红、各子路径黑高相等,并对 LLRB 检查无右红;中序有序只验证了 BST。