文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构】考研408 | 红黑树插入：一个口诀搞定“叔叔”脸色，实现近似平衡

【数据结构】考研408 | 红黑树插入：一个口诀搞定“叔叔”脸色，实现近似平衡

作者头像
蒙奇D索隆
发布于 2025-12-19 10:24:38
发布于 2025-12-19 10:24:38
2400
举报
文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇内容中我们详细介绍了红黑树的定义与性质：

  • 红黑树是一棵满足 根叶黑、不红红、黑路同 的 BST
  • 红黑树具有3条重要推论： 推论1：从根节点到叶结点的最长路径不大于最短路径的 2 倍 推论2：有 n 个内部结点的红黑树的高度 h \leq 2 * \log_2 (n + 1) 推论3：新插入红黑树中的结点初始着红色

前两条推论我们已经深入探讨过，它们确保了红黑树能够维持近似平衡的特性。那么，第三条推论为何规定新插入的结点必须初始化为红色？​ 这一关键选择背后蕴含着怎样的设计智慧？​ 它又将如何影响红黑树后续的平衡调整策略？ 带着这些疑问，让我们一同进入今天的内容——红黑树的插入操作，探索这一经典数据结构维持平衡的精妙机制。

一、推论3

在开始探讨 RBT 的插入操作前，我们需要先解决前面提到的问题：

  • 第三条推论为何规定新插入的结点必须初始化为红色？​
  • 这一关键选择背后蕴含着怎样的设计智慧？​
  • 它又将如何影响红黑树后续的平衡调整策略？

接下来我们会通过逐步的深入探讨，依次来解答这些问题；

代码语言：javascript
复制
flowchart TB
a[bh = 1]
a--->a1[NULL<br>bh = 0]
a--->a2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class a1 Black
class a2 Black

下面我们需要插入一个新的结点，这时就存在两种情况：

  • 插入的结点为黑色，我们得到的新树如下所示：
代码语言：javascript
复制
flowchart TB
a[bh_l = 2<br>bh_r = 1]
a--->b[bh = 1]
b ---> b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]
a--->a1[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class a1 Black
class b Black
class b1 Black
class b2 Black

可以看到，此时由于插入的是黑结点，这就导致了插入的那棵子树的黑高发生了变化，进而使得该子树的父节点不再满足 黑路同 的性质，因此需要进行调整，使其恢复 黑路同； 在上例中，我们需要做的调整就是将新插入的结点转变为 红结点 即可解决问题；

  • 插入的结点为红色，我们得到的新树如下所示：
代码语言：javascript
复制
flowchart TB
a[bh_l = 1]
a--->b[bh = 1]
b ---> b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]
a--->a1[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class a1 Black
class b Red
class b1 Black
class b2 Black

此时插入的结点并对 RBT 照成任何影响，因此不需要任何调整； 通过这个例子我们不难发现，当插入的结点初始为黑色时，这就代表每一次的插入操作都会改变树的 黑路同 这一性质，也就是说，每一次插入操作的执行，都需要伴随着树的调整操作； 当插入的结点初始为红色时，我们需要进行调整时的情况就变成了当前插入的结点破坏了 不红红 这一性质时，才需要进行调整操作； 这就是为什么新插入的结点必须初始化为红色，这种选择的核心智慧在于，通过选择插入红色结点，将插入操作可能引发的平衡问题控制在局部和特定情况下，从而大幅降低调整的概率和开销。 那么他会对 RBT 的后续平衡调整策略带来哪些影响呢？接下来我们就来通过探讨 RBT 的插入操作，进一步解答该问题；

二、插入思想

RBT 的插入操作与 AVL 的插入操作有很多的相似之处，这里我们简单的回顾以下 AVL 的插入操作：

  • 在树中根据 BST 的插入规则插入新结点
  • 当插入的新结点破坏了树的平衡，则找到 最小不平衡子树 ，并新结点的插入位置（相对于 最小不平衡子树 的根节点）
  • 根据新结点的插入位置完成 最小不平衡子树 的平衡调整后，需要继续向上查找，直到整棵树恢复平衡

在 RBT 中，其插入的过程如下：

  • 通过 查找 操作，确定新结点的插入位置，并插入新结点
  • 插入的新结点为根，则将其染成黑色，并完成插入
  • 插入的新结点不是根，则需要判断是否需要进行调整
    • 若插入新结点后依然满足红黑树定义，则插入结束
    • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义，这时就需要通过其叔结点的颜色进行进一步的判断
      • 叔结点为黑结点，则需要完成 旋转+染色
        • LL型：右单旋，父换爷+染色
        • RR型：左单旋，父换爷+染色
        • LR型：左、右双旋，儿换爷+染色
        • RL型：右、左双旋，儿换爷+染色
      • 叔结点为红结点，则需要完成 染色+变新
        • 叔父爷染色，爷变为新结点

对比这二者的插入过程，我们不难发现，不管是 AVL 还是 RBT ，二者在进行插入操作时有如下的相同之处：

  • 当插入的新结点不会破坏树的特性时，直接插入新结点，即可完成插入操作；
  • 当插入的新结点破坏了树的特性时，则需要对其进行相应的调整操作

这二者的不同之处在于具体的调整操作的实现上：

  • AVL 的平衡调整是以插入的新结点相对于 最小不平衡子树 的根节点的相对位置进行具体的平衡旋转：
    • 插入的新结点位于 最小不平衡子树 的左孩子的左子树，则进行 LL平衡旋转 ，使其恢复平衡
    • 插入的新结点位于 最小不平衡子树 的左孩子的右子树，则进行 LR平衡旋转 ，使其恢复平衡
    • 插入的新结点位于 最小不平衡子树 的右孩子的右子树，则进行 RR平衡旋转 ，使其恢复平衡
    • 插入的新结点位于 最小不平衡子树 的右孩子的左子树，则进行 RL平衡旋转 ，使其恢复平衡
  • RBT 的调整操作是以插入的新结点的叔结点的颜色进行具体的调整：
    • 叔结点为黑色，则根据插入的新结点相对于其爷结点的相对位置进行旋转操作：
      • 新结点位于其爷结点的左孩子的左子树，则需要进行 LL旋转 并完成染色操作
      • 新结点位于其爷结点的左孩子的右子树，则需要进行 LR旋转 并完成染色操作
      • 新结点位于其爷结点的右孩子的右子树，则需要进行 RR旋转 并完成染色操作
      • 新结点位于其爷结点的右孩子的左子树，则需要进行 RL旋转 并完成染色操作
    • 叔结点为红色，则需要先将叔、父、爷三个结点进行染色，再将爷结点视为新插入的结点，并对其再一次进行插入判断，直到整棵树恢复成一棵 RBT

了解了插入的具体思想，接下来我们就来通过实例来说明 RBT 的具体插入过程

三、插入过程

下面我们通过将 [20, 10, 5, 30, 20] 依次插入到一棵空的 RBT 中；

  • 插入第一个元素 20

首先，我们将新插入的结点染成红色，并插入到树中：

代码语言：javascript
复制
flowchart TB
a[20]

classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Red

由于此时插入的结点为根结点，因此我们只需将其变为黑色，即可完成插入操作：

代码语言：javascript
复制
flowchart TB
a[20]

classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black

当然，完成的插入过程是需要记录当前结点的黑高，这里我们将其省略了，但是大家心里一定要清楚，每一此的调整，都需要对各结点的黑高同步的进行相应的调整；

  • 插入元素 10

接下来，我们需要根据 BST 的插入规则，将新的元素 10 染成红色，并插入到树中：

代码语言：javascript
复制
flowchart TB
a[20]
a--->b[10]
a--->a1[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Red
class a1 Black

此时对于新插入的结点 10 来说，其父结点为黑色，因此我们不需要进行任何调整，可以直接完成插入操作；

  • 插入元素 5

同理，我们需要将元素 5 染成红色后，根据 BST 的插入规则插入到树中：

代码语言：javascript
复制
flowchart TB
a[20]
a--->b[10]
a--->a1[NULL]

b--->c[5]
b--->b1[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Red
class a1 Black
class c Red
class b1 Black

此时我们发现，插入的新结点的父结点为红色，破坏了 RBT 的 不红红 ，因此我们需要通过其叔结点的颜色进行具体的平衡调整； 新结点 5 的叔结点为 NULL ，其颜色为 黑色 ，因此我们需要判断该结点相对于其爷结点 20 的位置：

代码语言：javascript
复制
flowchart TB
a[20]
a--->|L|b[10]
a--->a1[NULL]

b--->|L|c[5]
b--->b1[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Red
class a1 Black
class c Red
class b1 Black

此时我们不难发现，新插入的结点位于其爷结点的左孩子的左子树中，因此我们需要对其进行 LL旋转：

代码语言：javascript
复制
flowchart TB
a[20]
a--->|L|b[10]
a--->a1[NULL]

b--->|L|c[5]
b--->b1[NULL]

ARROW[进行一次右单旋转->]

B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->A2[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Red
class A Black
class A1 Black
class A2 Black
class C1 Black
class C2 Black
class B Red
class a1 Black
class c Red
class C Red
class b1 Black

完成旋转操作后，我们需要对其父结点与原爷结点进行染色：

  • 将父结点由红色染成黑色
  • 将爷结点由黑色染成红色
代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->A2[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Red
class A1 Black
class A2 Black
class C1 Black
class C2 Black
class B Black
class C Red
class b1 Black

可以看到，此时完成 旋转 + 染色 后，整颗树恢复了 RBT 的红黑性质，因此我们完成了元素 5 的插入操作；

  • 插入元素 30

我们将 30 染成红色后插入到树中：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->D[30]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Red
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Red
class b1 Black

可以看到，此时新插入的结点破坏了 不红红 这条性质，因此我们需要通过其叔结点来决定如何进行调整； 结点 30 的叔结点为 5 ，且颜色为红色，因此我们需要将 30 的叔、父、爷这三个结点进行染色：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->D[30]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Black
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Red
class C Black
class b1 Black

此时，我们需要将爷结点 10 作为新插入的结点，在一次进行判断，由于此时的爷结点为树的根结点，因此我们只需要修改其颜色即可：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->D[30]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Black
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Black
class b1 Black

经过这次的 染色 + 变新 操作后，该树再一次恢复了 RBT 的性质；

  • 插入元素 20

相比于 AVL ，RBT 因为其 近似平衡 没有 高度平衡 那么严格，因此 RBT 允许在树中插入相同元素，这时只要我们预先约定好其插入的位置即可，这时我们就有两种选择：

  • 选择1：规定左子树 \leq 根结点，即相同元素需要插入到该元素的左子树中
  • 选择2：规定根结点 \leq 右子树，即相同元素需要插入到该元素的右子树中

这里我们使用 选择2 ，即，将相同的元素插入到其右子树中：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->D[30]

D--->E[20]
D--->D1[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Black
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Black
class b1 Black
class E Red
class D1 Black

可以看到此时插入的新结点破坏了 RBT 的 不红红 性质，因此我们需要通过其叔结点判断具体应该如何调整； 新结点 20 的叔结点为 NULL ，且颜色为黑色，因此我们需要根据新结点相对其爷结点的位置来进行进一步调整：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->|R|D[30]

D--->|L|E[20]
D--->D1[NULL]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Black
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Black
class b1 Black
class E Red
class D1 Black

可以看到，新插入的结点位于其爷结点的右孩子的左子树，因此我们需要进行一次 RL旋转：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
A[20]
B--->A
A--->A1[NULL]
A--->|R|D[30]

D--->|L|E[20]
D--->D1[NULL]

arrow[先进行一次右单旋转->]

b[10]
c[5]
b --->c
c--->c1[NULL]
c--->c2[NULL]
a[20]
b--->a
a--->a1[NULL]
e[20]
a--->|R|e
e--->e1[NULL]
d[30]
e--->|R|d

classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Black
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Black
class b1 Black
class E Red
class D1 Black

class a Black
class a1 Black
class d Red
class c1 Black
class c2 Black
class b Black
class c Black
class b1 Black
class e Red
class e1 Black

与 AVL 的 RL旋转 一样，先将以新结点的父结点 30 为根的子树完成一次右单旋转，之后再将以新结点的原爷结点，也就是现在的父结点黑 20 为根的子树进行一次左单旋转：

代码语言：javascript
复制
flowchart TB
b[10]
c[5]
b --->c
c--->c1[NULL]
c--->c2[NULL]
a[20]
b--->a
a--->a1[NULL]
e[20]
a--->|R|e
e--->e1[NULL]
d[30]
e--->|R|d

arrow[再进行一次左单旋转->]

B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
E[20]

B--->E
A[20]
E--->A
A--->A1[NULL]
A--->A2[NULL]


D[30]
E--->D

classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Black
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Black
class b1 Black
class E Red
class A2 Black

class a Black
class a1 Black
class d Red
class c1 Black
class c2 Black
class b Black
class c Black
class b1 Black
class e Red
class e1 Black

此时我们再对新结点与原爷结点进行染色操作：

代码语言：javascript
复制
flowchart TB
B[10]
C[5]
B --->C
C--->C1[NULL]
C--->C2[NULL]
E[20]

B--->E
A[20]
E--->A
A--->A1[NULL]
A--->A2[NULL]


D[30]
E--->D

classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class A Red
class A1 Black
class D Red
class C1 Black
class C2 Black
class B Black
class C Black
class b1 Black
class E Black
class A2 Black

此时经过 旋转 + 染色 操作后，该树再一次恢复为一棵 RBT ；

小结

不难发现，当我们将新插入的结点统一染成红色后进行插入，这就直接决定了后续平衡调整的核心任务：解决 红红 的问题。 整个调整的策略主要着眼于四个结点：新结点、父结点、爷结点、叔结点； 其具体的调整会根据：新结点 与 爷结点 的位置关系以及 叔结点 的颜色进一步展开，其具体的过程可以总结为以下内容：

  • 当插入结点的叔结点为 黑色 时，需要完成 旋转 + 染色 操作：
    • 当新结点的位置位于其爷结点的 左子树的左孩子，或者 右子树的右孩子 时，需要进行一次 LL旋转 或者 RR旋转；
      • 完成旋转后，进行染色的对象为新结点的 原父结点 以及 原爷结点
    • 当新结点的位置位于其爷结点的 左子树的右孩子，或者 右子树的左孩子 时，需要进行一次 LR旋转 或者 RL旋转
      • 完成旋转后，进行染色的对象为 新结点 以及 原爷结点
  • 当插入结点的叔结点为 红色 时，需要完成 染色 + 变新 操作：
    • 染色的对象为新结点的 叔结点、父结点、爷结点
    • 变新的对象为新结点的 爷结点，即将 爷结点 视为新插入的结点
    • 完成操作后，需要将 爷结点 视为新结点继续向上进行判断，直至整棵树恢复成一棵 RBT

结语

通过今天的学习，我们深入探讨了红黑树插入操作的核心机制。从新结点初始为红色的设计智慧，到基于叔叔结点颜色的分类调整策略，红黑树展现出了精妙的平衡艺术。

核心模块

关键知识点

说明与规则

插入结点颜色

新插入结点默认为红色

避免直接破坏黑高平衡（性质5）。若插入黑结点，每次插入都会改变路径黑高，必须调整；插入红结点仅在导致“红红”冲突时才需调整。

调整触发条件

插入后父结点为红色（破坏“不红红”性质）

若父结点为黑色，直接插入完成。调整核心是解决连续红色结点的局部问题。

情景分类依据

依据叔叔结点 的颜色决定调整策略

- 叔叔为红：执行“染色+向上回溯”。<br>- 叔叔为黑（或不存在）：执行“旋转+染色”。

叔叔为红（染色+回溯）

1. 将父、叔染黑<br>2. 将爷染红<br>3. 将爷结点视为新结点，向上回溯检查

将红色向上“推送”，可能递归到根。回溯至根时，需确保根为黑。

叔叔为黑 - LL/RR型（单旋+染色）

- LL：右单旋，父染黑，爷染红<br>- RR：左单旋，父染黑，爷染红

新结点位于爷结点左子的左子树（LL）或右子的右子树（RR）。旋转后原父结点成为新根并变黑。

叔叔为黑 - LR/RL型（双旋+染色）

- LR：先左旋父结点，再右旋爷结点，新结点染黑，爷染红<br>- RL：先右旋父结点，再左旋爷结点，新结点染黑，爷染红

新结点位于爷结点左子的右子树（LR）或右子的左子树（RL）。双旋后新结点成为局部根并变黑。

调整终止条件

1. 调整后满足红黑树所有性质<br>2. 向上回溯至根结点（根最终染黑）<br>3. 旋转+染色后局部平衡，无需继续回溯

“旋转+染色”可一次性解决局部问题；“染色+回溯”可能需传递到根。

与AVL树对比

- 平衡标准：红黑树“近似平衡” vs AVL树“严格平衡”<br>- 调整频率：红黑树插入旋转次数通常更少<br>- 调整依据：红黑树看叔叔结点颜色，AVL树看平衡因子

红黑树通过放宽平衡条件减少调整，综合性能更优，尤其适用于频繁插入删除的场景。

RBT 的插入操作实际上并不复杂，关键在于理解其"以局部调整换取全局平衡"的设计哲学。通过与 AVL树 的对比学习，我们能更好地把握 RBT 在性能与实现复杂度之间的精妙平衡。 互动与分享

  • 点赞👍 - 您的认可是我持续创作的最大动力
  • 收藏⭐ - 方便随时回顾这些重要的基础概念
  • 转发↗️ - 分享给更多可能需要的朋友
  • 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-04，如有侵权请联系 cloudcommunity@tencent.com 删除
数据结构
class
null
width
设计

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据结构
class
null
width
设计
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 导读
  • 一、推论3
  • 二、插入思想
  • 三、插入过程
    • 小结
  • 结语
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论