考研笔记

红黑树

红黑树是「嫌 AVL 太贵」的产物。

教材开篇给的动机很明确：为了保持 AVL 树 的平衡性，在插入和删除操作后，会非常频繁地调整全树整体拓扑结构，代价较大。为此在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构。

放宽到什么程度？AVL 是高度平衡（左右子树高度差 ≤ 1），红黑树是适度平衡——「任意一个结点左右子树的高度，相差不超过 2 倍」。平衡性差了，但调整的频率低了，综合下来更划算。

理解这一节的抓手是：五条性质里，性质 ④ 和 ⑤ 才是有内容的，其余三条是记账用的。 插入破坏的永远是 ④（出现两个相邻红结点），删除破坏的永远是 ⑤（某条路径黑结点少了一个）。知道破坏的是哪一条，就知道该怎么修。

机制

五条红黑性质

一棵红黑树是满足如下红黑性质的二叉排序树：

  1. 每个结点或是红色，或是黑色的。
  2. 根结点是黑色的。（根叶黑）
  3. 叶结点（虚构的外部结点、NULL 结点）都是黑色的。
  4. 不存在两个相邻的红结点（红结点的父结点和孩子结点均是黑色的）。（不红红）
  5. 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。（黑路同）

与 折半查找的判定树 和 B 树 类似，为了便于对红黑树的实现和理解，引入了 个外部叶结点，以保证红黑树中每个结点（内部结点）的左、右孩子均非空。

关联对照：

「虚构 个外部结点」这套做法在本章出现了三次：折半查找判定树的方形失败结点、 红黑树的 NULL 叶结点、B 树的失败结点。三处的作用完全一样—— 把「查找失败」变成一个可以指到的位置，从而让「路径长度」这个量对失败也有定义。 记住一次，三处通用。

黑高

从某结点出发（不含该结点）到达一个叶结点的任意一个简单路径上的黑结点总数称为该结点的黑高（记为 ）。黑高的概念是由性质 ⑤ 确定的。根结点的黑高称为红黑树的黑高。

「不含该结点」这四个字是定义的全部。 一个黑结点自己不算进自己的黑高里；外部 NULL 结点的黑高是 0。

flowchart TD
    R(("6<br/>bh=2")) --- N2(("2<br/>bh=1"))
    R --- N15(("15<br/>bh=2"))
    N2 --- E1[" "]
    N2 --- E2[" "]
    N15 --- N11(("11<br/>bh=1"))
    N15 --- N18(("18<br/>bh=1"))
    N11 --- N8(("8<br/>bh=1"))
    N11 --- N14(("14<br/>bh=1"))
    N18 --- E3[" "]
    N18 --- N20(("20<br/>bh=1"))
    N8 --- E4[" "]
    N8 --- E5[" "]
    N14 --- E6[" "]
    N14 --- E7[" "]
    N20 --- E8[" "]
    N20 --- E9[" "]

    classDef black fill:#212121,stroke:#000,color:#fff,stroke-width:2px
    classDef red fill:#e57373,stroke:#b71c1c,color:#000,stroke-width:2px
    classDef nil fill:#424242,stroke:#000,color:#fff
    class R,N2,N11,N18 black
    class N15,N8,N14,N20 red
    class E1,E2,E3,E4,E5,E6,E7,E8,E9 nil

验算一遍性质 ⑤：从根 6 出发的四条路径 6-2-□、6-15-11-8-□、6-15-18-□、6-15-18-20-□，黑结点数依次是 ——全相等，。红结点 15 不计入，NULL 结点计入。

两条结论

结论 1：从根到叶结点的最长路径不大于最短路径的 2 倍。

  • 由性质 ⑤，当从根到任意一个叶结点的简单路径最短时，这条路径必然全由黑结点构成
  • 由性质 ④，当某条路径最长时，这条路径必然是由黑结点和红结点相间构成的，此时红结点和黑结点的数量相同

上图中 6−2 和 6−15−18−20 就是这样的两条路径。

结论 2：有 个内部结点的红黑树的高度 。

证明：由结论 1，从根到叶结点（不含叶结点）的任何一条简单路径上都至少有一半是黑结点，因此根的黑高至少为 ，于是有 ，即可求得结论。

由结论 2 也可推出：黑高为 的红黑树，内部结点数最少是 ，最多是 。

量结果
树高上界
黑高为 时结点数最少（全黑，满二叉树）
黑高为 时结点数最多（红黑相间，高度翻倍）

和 AVL 树怎么选

教材给的判据只有一句：

对于一棵动态查找树，若插入和删除操作比较少、查找操作比较多，则采用 AVL 树比较合适，否则采用红黑树更合适。

但紧接着补了一句现实：由于维护这种高度平衡所付出的代价比获得的效益大得多，红黑树的实际应用更广泛，C++ 中的 map 和 set（Java 中的 TreeMap 和 TreeSet）就是用红黑树实现的。

插入：三种情况，看叔结点的颜色

结论 3：新插入红黑树中的结点初始着为红色。

理由要能说出来：假设新插入的结点初始着为黑色，则这个结点所在的路径比其他路径多出一个黑结点（几乎每次插入都破坏性质 ⑤），调整起来也比较麻烦。若插入的结点是红色的，则此时所有路径上的黑结点数量不变，仅在出现连续两个红结点时才需要调整，而且这种调整也比较简单。

设结点 为新插入的结点。插入过程：

  1. 用二叉查找树插入法插入，并将结点 着为红色。若结点 的父结点是黑色的，无须做任何调整，此时就是一棵标准的红黑树，结束。
  2. 若结点 是根结点，则将 着为黑色（树的黑高增 1），结束。
  3. 若结点 不是根结点，且 的父结点 是红色的，则分下面三种情况，区别在于 的叔结点 的颜色不同。

因 是红色的，插入前的树是合法的，根据性质 ② 和 ④，爷结点 必然存在且为黑色。性质 ④ 只在 和 之间被破坏了。

flowchart TD
    S["新结点 z 着红色<br/>按 BST 插入"] --> Q1{"z.p 是黑色？"}
    Q1 -->|"是"| END1["无须调整，结束"]
    Q1 -->|"否"| Q2{"z 是根？"}
    Q2 -->|"是"| END2["z 着黑<br/>黑高 +1，结束"]
    Q2 -->|"否"| Q3{"叔结点 y 的颜色"}
    Q3 -->|"y 黑，z 是右孩子"| C1["情况 1（LR）<br/>先左旋 → 转成情况 2"]
    Q3 -->|"y 黑，z 是左孩子"| C2["情况 2（LL）<br/>右单旋 + 交换父与爷的颜色<br/>结束"]
    Q3 -->|"y 红"| C3["情况 3<br/>父与叔着黑、爷着红<br/>z 上移两层，回到判断"]
    C1 --> C2
    C3 --> Q2

    classDef done fill:#c8e6c9,stroke:#1b5e20
    classDef loop fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    class END1,END2,C2 done
    class C3 loop
    class S,Q1,Q2,Q3,C1 norm

情况 1（LR，先左旋，再右旋）： 的叔结点 是黑色的，且 是其爷结点的左孩子的右孩子。先做一次左旋将此情形转变为情况 2，左旋后 和父结点 交换位置。因为 和 都是红色的，所以左旋操作对结点的黑高和性质 ⑤ 都无影响。

情况 2（LL，右单旋）： 的叔结点 是黑色的，且 是其爷结点的左孩子的左孩子。做一次右旋，并交换 的原父结点和原爷结点的颜色，就可以保持性质 ⑤，也不会改变树的黑高。这样，红黑树中也不再有连续两个红结点，结束。

若父结点 是爷结点 的右孩子，则还有两种对称的情况：RL（先右旋，再左旋）和 RR（左单旋）。

情况 3（ 是左孩子或右孩子无影响）： 的父结点 和叔结点 都是红色的。因为爷结点 是黑色的，将 和 都着为黑色，将 着为红色，以在局部保持性质 ④ 和 ⑤。然后把 作为新结点 来重复循环，指针 在树中上移两层。

只要满足情况 3 的条件，就会不断循环，每次循环指针 都会上移两层，直到满足第 2 步（ 上移到根结点）或情况 1 或情况 2 的条件。

边界辨析：

教材专门澄清了一个「可能的疑问」：虽然插入的初始位置一定是红黑树的某个叶结点， 但因为在情况 3 中结点 存在不断上升的可能，所以对于三种情况，结点 都有存在于子树的可能。 换句话说，不要以为 永远是新插入的那个叶子——它是一个会往上爬的游标。

删除

层次辨析：

教材把这一小节标为 *3. 并加了注意框： 「本节难度较大，考查概率较低，读者可根据自身情况决定是否学习或学习的时机。」 这是教材自己给的降级，不是我的判断。时间紧时这一小节可以最后再看， 但下面这几条结论性的东西要知道，因为它们会以选择题的形式出现。

  • 插入破坏的是性质 ④（容易导致连续的两个红结点）；删除破坏的是性质 ⑤（删除黑结点会导致根结点到叶结点间的黑结点数量减少）。
  • 删除过程也是先执行二叉查找树的删除方法。若待删结点有两个孩子，不能直接删除，而要找到该结点的中序后继（或前驱）填补，即右子树中最小的结点，然后转换为删除该后继结点。由于后继结点至多只有一个孩子，这样就转换为待删结点是终端结点或仅有一个孩子的情况。
  • 最终，删除一个结点只有两种情况：待删结点只有右子树或左子树、待删结点没有孩子。
  • 若待删结点只有一棵子树，则子树只有一个结点，且必然是红色，否则会破坏性质 ⑤。
  • 若待删结点无孩子且是红色，直接删除，不需要做任何调整。
  • 若待删结点无孩子且是黑色，则把用来替换它的结点 视为还有额外一重黑色，定义为双黑结点。删除操作的任务就转化为将双黑结点恢复为普通结点。
  • 恢复分四种情况，区别在于 的兄弟结点 及 的孩子结点的颜色不同：情况 1（ 红）、情况 2（ 黑且 的右孩子红，RR 左单旋）、情况 3（ 黑、左孩子红、右孩子黑，RL 先右旋再左旋）、情况 4（ 黑且两个孩子都黑）。
  • 情况 4 是可能重复执行的唯一一种：从 和 中各提取一重黑色，把调整任务向上「推」给父结点 ， 上升一层。情况 1、2、3 在各执行常数次的颜色改变和至多 3 次旋转后便终止。

手算模板

判断一棵树是不是红黑树：按五条性质逐条查，顺序是 ② → ④ → ⑤（① ③ 是记账约定，基本不会被违反）。⑤ 要补出所有 NULL 叶结点再数，漏补 NULL 是最常见的错。

插入一个关键字：

  1. 按 BST 找到位置挂上，着红。
  2. 看父结点：黑 → 结束。
  3. 看 是不是根：是 → 着黑，黑高 +1，结束。
  4. 看叔结点的颜色：
    • 叔红 → 情况 3：父、叔着黑，爷着红， 跳到爷，回第 2 步。
    • 叔黑 → 看 是「外侧」还是「内侧」孩子：
      • 外侧（LL / RR） → 情况 2：单旋 + 交换原父与原爷的颜色，结束。
      • 内侧（LR / RL） → 情况 1：先朝里旋一次转成外侧，再按情况 2 做，结束。

记忆抓手：叔红就变色往上爬，叔黑就旋转一次就完。

算黑高：从目标结点的孩子开始往下数到任一 NULL，只数黑的，NULL 算一个黑。

边界

说法判断说明
「红黑树是平衡二叉树」❌是适度平衡，左右子树高度可相差近 2 倍；AVL 才是高度平衡
「红黑树首先是二叉排序树」✅定义的第一句就是「满足红黑性质的二叉排序树」
「黑高包含结点自身」❌定义是「不含该结点」
「叶结点指的是没有孩子的实际结点」❌指虚构的外部 NULL 结点，且它们都是黑色的
「不存在两个相邻的黑结点」❌是不存在两个相邻的红结点；黑结点相邻完全合法
「新插入的结点着黑色」❌着红色（结论 3），理由是不破坏性质 ⑤
「插入后一定要旋转」❌父结点是黑的就什么都不做
「插入最多旋转一次」⚠️情况 1 + 情况 2 合起来是两次旋转；情况 3 只变色不旋转，但可能循环多轮
「情况 3 会一直循环到根」⚠️可能循环到根，也可能中途遇到情况 1 / 2 就结束
「树高 」❌是 ，多一个因子 2
「黑高为 时结点数最多 」❌最少 ，最多
「查找操作多就该用红黑树」❌反了。查找多、增删少 → AVL；否则红黑树
「红黑树的删除是重点」❌教材标 * 并注明「考查概率较低」

口径差异：

算法竞赛里红黑树只以 std::map / std::set 的形式出现——没有人手写它，也没有人关心它转了几次。 408 恰恰相反：2023 年起红黑树进入考纲，考的就是「插入 5、4、12 之后树长什么样」「某结点的黑高是多少」 「下列哪棵树不是红黑树」。 算竞背景在这一节的帮助接近于零，而且会带来一个反向干扰—— 习惯了「有 map 就够了」的人容易跳过性质 ⑤ 的细节，而性质 ⑤ 正是所有选择题的落点。

关联对照：

红黑树的调整方法和 AVL 树的调整方法有异曲同工之妙（教材原话）： 都是 LL / RR / LR / RL 四种，都是「内侧先转成外侧，外侧一次转完」。 区别在于触发条件：AVL 看平衡因子，红黑树看叔结点的颜色； AVL 旋完就结束，红黑树的情况 3 只变色不旋转，靠往上爬来终结。

对照速查

AVL 树红黑树
平衡标准高度平衡，适度平衡，最长路径 最短路径
树高，常数更小 量级
判据看什么平衡因子结点颜色
插入调整旋转，最多 1 次调整变色 + 旋转，情况 3 可上溯
删除调整可能回溯到根情况 4 可上溯
适用查找多、增删少增删较多；实际应用更广
工业实现较少C++ map/set，Java TreeMap/TreeSet
插入情况叔结点 的位置动作是否结束
情况 1黑内侧（LR / RL）先旋一次 → 转情况 2否
情况 2黑外侧（LL / RR）单旋 + 交换原父与原爷的颜色是
情况 3红无所谓父、叔着黑，爷着红， 上移两层否，回到循环
性质插入会破坏删除会破坏
④ 无相邻红结点会不会
⑤ 黑结点数相同不会（因为新结点着红）会

考点

  • 五条性质，尤其 ④ 和 ⑤ 的准确措辞。
  • 黑高的定义不含自身，NULL 结点算黑、黑高为 0。
  • 结论 1 / 2：最长 ≤ 2× 最短；；黑高 时结点数 。
  • 新结点着红及其理由。
  • 插入三种情况按叔结点颜色分，叔红变色上爬、叔黑旋转终结。
  • 插入破坏 ④、删除破坏 ⑤——一句话定位修哪条。
  • AVL 与红黑树的选择判据（查找多用 AVL）。
  • 删除是 * 号内容、考查概率较低——这本身也是一条边界。

链接

反向链接