专题进阶 · 树与范围查询推荐总顺序 · 第 51 / 148 课

通过黑高理解红黑树的平衡,掌握左倾版本插入中的旋转和颜色翻转。

先学会这些,再进入本课 二叉搜索树 AVL 树
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

红黑树Red–Black Tree

颜色约束限制路径长度,通过旋转与变色保持对数高度。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

通过黑高理解红黑树的平衡,掌握左倾版本插入中的旋转和颜色翻转。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 普通插入与旋转保持中序顺序。
  2. 新红叶、带颜色转移的旋转和翻色保持局部路径黑高相等。
  3. 回溯消除右红与连续左红,根置黑,得到左倾红黑不变量;代码只涵盖插入,删除有独立修复过程。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

红节点能有黑孩子吗?

需要一点提示

禁止的是红红相邻。

查看解析与答案

可以,而且它的非空孩子必须黑;空叶也视为黑。

练习 2 · 边界与辨析

为什么新叶不直接染黑?

需要一点提示

只增加一条路径的黑节点。

查看解析与答案

会破坏该路径与兄弟路径的黑高一致性,修复更困难。

练习 3 · 变式与迁移

如何验证实现而非只看中序有序?

需要一点提示

还要检查颜色不变量。

查看解析与答案

检查根黑、无红红、各子路径黑高相等,并对 LLRB 检查无右红;中序有序只验证了 BST。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。