红黑树是什么？红黑树的插入和删除-js教程-PHP中文网

红黑树通过颜色规则与旋转变色操作保持平衡，插入时以红色节点加入并修复红红冲突，删除黑色节点时引发黑高失衡需复杂修复，核心在于五条性质确保最长路径不超过最短路径两倍，从而维持O(log n)效率。

红黑树是什么？红黑树的插入和删除

红黑树，说白了，就是一种特别聪明的二叉查找树。它不像普通二叉查找树那样，在插入或删除数据后可能会变得“歪七扭八”，导致查找效率骤降到线性时间。红黑树通过给每个节点“染色”（红或黑），并遵循一套严格的规则，确保树的高度始终保持在对数级别，这样一来，无论是查找、插入还是删除，它的平均和最坏时间复杂度都能稳定在O(log n)。这对于追求高效数据操作的系统来说，简直是救星。

红黑树的插入和删除

红黑树的精髓在于它如何在每次数据变动后，通过“变色”和“旋转”来维持其平衡特性。这个过程，坦白说，比理解它的定义要复杂得多，但正是这些看似繁琐的步骤，才赋予了它稳定高效的能力。

红黑树的插入操作

当我们想往红黑树里插入一个新节点时，第一步其实和普通二叉查找树一样：找到合适的位置，把新节点作为叶子节点放进去。但这里有个关键点：新插入的节点，我们总是把它默认设为红色。

为什么是红色？想想看，如果新节点是黑色，它会立刻改变从它父节点到所有叶子节点的黑色节点数量（黑高），这会带来很多麻烦。而红色节点呢，它不会改变路径上的黑高，最多可能违反“不能有两个连续红色节点”的规则。处理这个“红色冲突”通常比处理黑高变化要简单。

插入红色节点后，如果它的父节点是黑色，那皆大欢喜，树依然平衡。但如果它的父节点也是红色，那麻烦就来了，我们必须进行修复。修复主要围绕三种情况展开：

父节点的兄弟节点（叔叔）是红色： 这种情况下，我们通常会把父节点和叔叔节点都变成黑色，然后把祖父节点变成红色。接着，把祖父节点视为新的“插入节点”，继续向上检查是否还有红色冲突。这有点像“颜色传递”，将问题向上推。
父节点的兄弟节点是黑色，且新节点是内侧子节点（即新节点、父节点、祖父节点形成“之”字形）： 这种时候，我们会先对父节点进行一次旋转，把“之”字形变成“一”字形，然后就转换成了第三种情况。
父节点的兄弟节点是黑色，且新节点是外侧子节点（即新节点、父节点、祖父节点形成“一”字形）： 这是最理想的情况。我们把父节点变黑，祖父节点变红，然后对祖父节点进行一次旋转。旋转完成后，树的平衡就恢复了。

这个过程听起来有点绕，但核心思想就是通过局部调整（变色和旋转），将不平衡的状态逐步消除，直到满足红黑树的所有规则。

红黑树的删除操作

删除操作比插入要复杂得多，因为删除一个节点可能导致更多规则被破坏，尤其是黑高规则。

删除一个节点时，首先我们会找到要删除的节点。如果它有两个子节点，我们会找到它的中序后继节点（或前驱节点），将中序后继的值复制到要删除的节点上，然后转而去删除这个中序后继节点。这样，我们总是将删除操作简化为删除一个最多只有一个子节点的节点。

接下来，真正的挑战来了。当被删除的节点是黑色时，问题就会出现。因为它的消失，导致经过它路径的黑高减少了1，这会破坏整个树的黑高平衡。如果被删除的节点是红色，那直接删除就行，不会影响黑高。

当删除一个黑色节点时，我们需要一个“替补”节点来填补它的位置。如果替补节点是红色，直接把它变黑就行了。但如果替补节点也是黑色（或者是个空节点），那么我们就面临一个“双重黑色”问题，这意味着那个位置的黑高“亏欠”了一个黑色节点，需要进行一系列复杂的修复：

兄弟节点是红色： 这种情况下，先将兄弟节点变黑，父节点变红，然后对父节点进行旋转。这会将情况转化为兄弟节点是黑色的场景，方便后续处理。
兄弟节点是黑色，且兄弟的两个子节点都是黑色： 此时，将兄弟节点变红，然后将“双重黑色”问题向上转移到父节点。如果父节点现在是双重黑色，则继续处理。
兄弟节点是黑色，兄弟的内侧子节点是红色，外侧子节点是黑色： 将兄弟的内侧子节点变黑，兄弟节点变红，然后对兄弟节点进行旋转。这会把情况转化为第四种。
兄弟节点是黑色，兄弟的外侧子节点是红色： 这是最理想的修复情况。将兄弟节点染成父节点的颜色，父节点变黑，兄弟的外侧子节点也变黑，然后对父节点进行旋转。此时，黑高平衡恢复，修复过程结束。

可以看到，删除操作的修复过程涉及更多种情况的判断和更复杂的旋转与变色组合，这也是它被认为比插入更难理解和实现的原因。

红黑树为什么能保持平衡？它的核心机制是什么？

红黑树之所以能保持平衡，并非靠什么神秘力量，而是因为它严格遵守一套“宪法”——五条核心性质：

节点非红即黑： 每个节点要么是红色，要么是黑色。简单直接。
根节点是黑色： 树的起点，必须是黑色的。这就像给树定个基调。
叶节点（NIL节点）是黑色： 所有的空子节点（我们通常用特殊的NIL节点表示，它们是树的外部节点）都是黑色的。这确保了所有路径的“终点”都是黑色的。
红色节点的孩子必须是黑色： 这条规则至关重要，它直接杜绝了“红红相连”的情况。这意味着从根到叶的任何路径上，都不会出现连续的红色节点。
任意节点到其所有后代叶节点的路径上，包含的黑色节点数量相同： 这就是所谓的“黑高”特性。它保证了从任何一个节点出发，到达其所有叶子节点的路径上，黑色节点的数量都是一样的。

这五条规则协同作用，共同保证了红黑树的平衡。想想看，如果一个路径上不能有连续的红色节点（规则4），那么最长的路径（红黑红黑...）和最短的路径（黑黑黑...）之间，红色节点最多只能是黑色节点数量的两倍。结合规则5（黑高相同），这意味着最长的路径长度不会超过最短路径长度的两倍。这样一来，树的高度始终被限制在O(log n)的范围内，无论数据如何增删，都不会出现极度倾斜的情况。旋转和变色，就是为了在插入或删除后，重新满足这些规则的“矫正手段”。

红黑树的插入操作具体是如何进行的？有哪些常见场景？

红黑树的插入，其实就是在一个基本有序的二叉查找树上，通过颜色和旋转来“微调”的过程。

我们先按照二叉查找树的规则，找到新值应该插入的位置，然后把它作为叶子节点插入。这个新节点，我们总会把它初始化为红色。

接着，我们要检查它是否破坏了红黑树的规则。最常被破坏的就是“红色节点的孩子必须是黑色”这条（规则4）。如果新节点的父节点也是红色，那我们就得启动修复机制了。

修复机制主要看新节点的父节点和祖父节点的关系，以及父节点的兄弟节点（叔叔）的颜色。

场景一：叔叔节点是红色。 假设我们插入了一个新节点N，它的父节点P是红色，P的兄弟节点（叔叔U）也是红色。这时，N、P、U、祖父G可能看起来是这样：
```
      G (黑)
     / \
    P(红) U(红)
   /
  N(红)
```
登录后复制
这种情况下，修复方法是：把P和U都变成黑色，把G变成红色。然后，把G看作新插入的节点，继续向上检查，直到根节点或没有红色冲突为止。

快写红薯通AI
快写红薯通AI，专为小红书而生的AI写作工具

57

查看详情
```
      G (红)  -- G现在可能与它的父节点冲突
     / \
    P(黑) U(黑)
   /
  N(红)
```
登录后复制
这个场景的好处是，它通过颜色翻转，将问题向上层传递，而不涉及复杂的树结构变化。
场景二：叔叔节点是黑色，且新节点是内侧子节点（“之”字形）。 假设N是P的右孩子，P是G的左孩子（或反过来）。
```
      G (黑)
     / \
    P(红) U(黑)
     \
      N(红)
```
登录后复制
这时，N、P、G形成一个“之”字形。我们首先对P进行一次左旋（如果N是P的右孩子），或者右旋（如果N是P的左孩子），让N变成P的位置，P变成N的左孩子。这样，“之”字形就变成了“一”字形，即转换成了场景三。
```
      G (黑)
     / \
    N(红) U(黑)
   /
  P(红)
```
登录后复制
（这里N和P的相对位置变了，N现在是G的左孩子，P是N的左孩子）
场景三：叔叔节点是黑色，且新节点是外侧子节点（“一”字形）。 假设N是P的左孩子，P是G的左孩子（或反过来）。
```
      G (黑)
     / \
    P(红) U(黑)
   /
  N(红)
```
登录后复制
这是最常见的修复场景。我们把P变黑，G变红，然后对G进行一次右旋（如果N和P都是左孩子）。
```
      P (黑)
     / \
    N(红) G(红)
           \
            U(黑)
```
登录后复制
经过这次旋转和变色，红黑树的规则通常就能得到满足，修复过程也就结束了。

这些场景的判断和执行顺序是固定的，它们构成了红黑树插入操作的“修复算法”，确保了每次插入后，树都能迅速恢复平衡。

红黑树的删除操作为何更复杂？其修复过程有哪些关键步骤？

红黑树的删除操作之所以比插入复杂，核心原因在于：删除一个黑色节点，会直接破坏其路径上的黑高平衡。插入红色节点只是潜在地引入了“红红冲突”，而删除黑色节点则是实实在在地“抽走了”一个黑色节点，导致从根到某些叶子的路径上的黑高减少了1。这种“黑高亏欠”的处理，要比处理红色冲突棘手得多。

删除过程可以分为几个关键步骤：

定位与简化：
- 首先，找到要删除的节点。
- 如果这个节点有两个非空子节点，我们不会直接删除它。而是找到它的中序后继节点（或前驱节点），将中序后继节点的值复制到要删除的节点中，然后把问题转化为删除这个中序后继节点。中序后继节点有一个非常方便的特性：它最多只有一个子节点（它不可能有左子节点，否则它就不是中序后继了）。
- 这样，所有的删除操作最终都归结为删除一个最多只有一个子节点的节点。
实际删除与替补：
- 假设我们要删除的节点是
```
y
```
  登录后复制
  ，它的子节点（如果存在）是
```
x
```
  登录后复制
  。
- 将
```
y
```
  登录后复制
  从树中移除，让
```
x
```
  登录后复制
  来替代
```
y
```
  登录后复制
  的位置。
- 关键判断： 如果
```
y
```
  登录后复制
  是红色，那么删除它不会影响任何路径的黑高，直接移除即可，无需后续修复。
- 如果
  y
  登录后复制
  是黑色：这就是麻烦的开始。移除一个黑色节点，导致经过
```
y
```
  登录后复制
  的所有路径的黑高都减少了1。我们需要进行修复。此时，
```
x
```
  登录后复制
  被认为是“双重黑色”的，或者说它“携带”了一个黑高亏欠。
修复“双重黑色”问题： 当
```
x
```
登录后复制
是双重黑色时，我们需要通过一系列的旋转和变色来恢复平衡。这里主要有四种情况，
```
x
```
登录后复制
代表当前需要修复的节点，
```
w
```
登录后复制
代表
```
x
```
登录后复制
的兄弟节点。
- 情况一：
```
x
```
  登录后复制
  的兄弟
  w
  登录后复制
  是红色。
```
      P (黑)
     / \
    X   W (红)
       / \
      WL(黑) WR(黑)
```
  登录后复制
  这种情况下，我们把
```
w
```
  登录后复制
  变黑，
```
P
```
  登录后复制
  变红，然后对
```
P
```
  登录后复制
  进行旋转（如果
```
x
```
  登录后复制
  是左孩子，就左旋）。这会将情况转化为兄弟
```
w
```
  登录后复制
  是黑色的场景，方便后续处理。
```
      W (黑)
     / \
    P(红) WR(黑)
   / \
  X   WL(黑)
```
  登录后复制
  （这里
```
x
```
  登录后复制
  仍然是双重黑色，需要继续处理）
- 情况二：
```
x
```
  登录后复制
  的兄弟
  w
  登录后复制
  是黑色，且
  w
  登录后复制
  的两个子节点都是黑色。
```
      P (任意色)
     / \
    X   W (黑)
       / \
      WL(黑) WR(黑)
```
  登录后复制
  这种情况下，我们把
```
w
```
  登录后复制
  红色。这样，
```
w
```
  登录后复制
  所在的子树的黑高就减少了1，与
```
x
```
  登录后复制
  所在的子树保持一致。然后，将
```
x
```
  登录后复制
  的“双重黑色”属性转移到它的父节点
```
P
```
  登录后复制
  。如果
```
P
```
  登录后复制
  变成了双重黑色，我们就从
```
P
```
  登录后复制
  重新开始修复过程。
```
      P (变为双重黑色，如果原来是黑色)
     / \
    X   W (红)
       / \
      WL(黑) WR(黑)
```
  登录后复制
- 情况三：
```
x
```
  登录后复制
  的兄弟
  w
  登录后复制
  是黑色，
  w
  登录后复制
  的内侧子节点是红色，外侧子节点是黑色。
```
      P (任意色)
     / \
    X   W (黑)
       / \
      WL(红) WR(黑)
```
  登录后复制
  （假设
```
x
```
  登录后复制
  是左孩子，
```
WL
```
  登录后复制
  是
```
w
```
  登录后复制
  的左孩子）这种情况下，我们把
```
WL
```
  登录后复制
  变黑，
```
w
```
  登录后复制
  变红，然后对
```
w
```
  登录后复制
  进行旋转（如果
```
x
```
  登录后复制
  是左孩子，就右旋）。这会把情况转化为兄弟
```
w
```
  登录后复制
  的外侧子节点是红色的场景（情况四）。
```
      P (任意色)
     / \
    X   WL(黑)
         \
          W(红)
           \
            WR(黑)
```
  登录后复制
- 情况四：
```
x
```
  登录后复制
  的兄弟
  w
  登录后复制
  是黑色，
  w
  登录后复制
  的外侧子节点是红色。
```
      P (任意色)
     / \
    X   W (黑)
       / \
      WL(黑) WR(红)
```
  登录后复制
  （假设
```
x
```
  登录后复制
  是左孩子，
```
WR
```
  登录后复制
  是
```
w
```
  登录后复制
  的右孩子）这是最理想的修复场景。我们把
```
w
```
  登录后复制
  染成
```
P
```
  登录后复制
  的颜色，把
```
P
```
  登录后复制
  变黑，把
```
WR
```
  登录后复制
  变黑，然后对
```
P
```
  登录后复制
  进行旋转（如果
```
x
```
  登录后复制
  是左孩子，就左旋）。
```
      W (P的颜色)
     / \
    P(黑) WR(黑)
   /
  X
```
  登录后复制
  此时，红黑树的所有规则都已满足，修复过程终止。