红黑树的插入与删除操作流程解析

红黑树的插入与删除操作流程解析一、红黑树概述

红黑树是一种自平衡二叉查找树，通过维护节点颜色的红黑属性和特定的树形性质来保证树的高度平衡，从而实现高效的插入和删除操作。其关键特性包括：

（一）节点颜色

1.每个节点只能是红色或黑色。

2.根节点为黑色。

3.红色节点的两个子节点均为黑色（从任一节点到其所有后代的外部路径上不能有两个连续的红色节点）。

4.从任一节点到其所有叶子的所有简单路径都包含相同数目的黑色节点（黑高）。

二、红黑树的插入操作

插入操作遵循二叉查找树的常规插入方法，随后通过旋转和重新着色调整树形以满足红黑性质。

（一）插入步骤

1.常规插入：

-在二叉查找树中查找合适位置插入新节点，默认节点为红色。

-由于插入红色节点可能破坏红黑性质，需进行后续调整。

2.调整操作：

-从插入节点向上遍历，根据父节点颜色和兄弟节点关系判断调整类型。

-可能涉及以下情况：

(1)祖父节点为黑色：直接回退至父节点检查。

(2)祖父节点为红色：存在父亲是红色或黑色两种子场景。

（二）调整类型及处理

1.LL/RR旋转（单旋转）：

-LL型：右旋调整，适用于祖父-父节点-插入节点均为红色且插入节点在父节点右侧。

-RR型：左旋调整，适用于祖父-父节点-插入节点均为红色且插入节点在父节点左侧。

2.LR/RL旋转（双旋转）：

-LR型：先左旋父节点，再右旋祖父节点。

-RL型：先右旋父节点，再左旋祖父节点。

-通过旋转将连续红色节点分离，同时重新着色。

（三）终止条件

-调整过程持续向上传播，直至：

1.遇到黑色节点或到达根节点。

2.所有红黑性质重新满足。

三、红黑树的删除操作

删除操作先按二叉查找树规则移除节点，再通过类似插入的调整方法修复红黑性质。

（一）删除步骤

1.节点替换：

-若待删除节点有双孩子，用后继节点替代并删除后继节点（后继节点必为单孩子或无孩子）。

-若为单孩子或无孩子，直接删除并标记为红色。

2.重新着色：

-删除黑色节点可能导致黑高不均，需从子节点向上调整。

（二）调整方法

1.红色补丁法：

-删除黑色节点后，补一个红色“补丁”以保持黑高平衡。

-补丁向上传播过程中，通过旋转和着色消除冲突。

2.调整场景：

-删除节点为红色：直接回退至父节点。

-删除节点为黑色：需处理补丁与父节点、兄弟节点的颜色关系，可能涉及：

(1)兄弟节点为红色：先旋转调整，再统一处理。

(2)兄弟节点为黑色：根据兄弟子节点颜色进行多种旋转（如LL、LR等）。

（三）终止条件

-调整过程直至补丁到达根节点或树形满足红黑性质。

四、示例操作

（一）插入示例

-插入值：15→常规插入为红色，父节点（10）为红色，祖父（5）为黑色。

-父节点与祖父均为红色→父节点右旋（若插入右侧），祖父-父节点变为红色。

-祖父节点（10）变为红色，需进一步调整（类似插入流程）。

（二）删除示例

-删除值：10→假设替换为后继节点12（红色）。

-补丁（12）向上传播，若兄弟节点（15）为红色：

1.父节点左旋（若补丁在左）。

2.重新着色后，补丁变为黑色，继续向上传播。

五、总结

红黑树的插入和删除操作通过“旋转+着色”的局部调整策略，确保在O(logn)时间内维持平衡。关键在于理解：

1.红黑性质是动态维护的，每次操作需从局部向上传播。

2.调整类型（单/双旋转）与父子兄弟关系密切相关。

3.终止条件通常为到达根节点或性质重新满足。

二、红黑树的插入操作（续）

（一）插入步骤（续）

1.常规插入：

查找位置：从根节点开始，按照二叉查找树的规则（节点值小于父节点则走左子树，大于父节点则走右子树）向下查找，直到找到空节点作为新节点的插入位置。

创建节点：在查找到的空位置创建一个新节点，该节点的值为其插入值。

初始着色：新插入的节点默认被着色为红色。这一步是为了后续的调整：因为插入红色节点最容易破坏红黑树的某些性质（尤其是性质3：红色节点的两个子节点均为黑色），但相对简单，且调整过程更容易处理红色节点引发的冲突。

示例：假设我们要向红黑树中插入值`x`。从根节点R开始比较，找到路径R->A->C。比较`x`与节点C的值。如果`x<C`，则沿C的左子树继续查找；如果`x>C`，则沿C的右子树继续查找。最终找到空子节点，在空位置创建节点`x`，并将其着色为红色。

2.调整操作（详细说明）：

触发调整：为什么需要调整？因为虽然根节点总是黑色（性质2），但新插入的节点是红色。如果连续有两个红色节点（例如，新节点及其父节点都是红色），就会直接违反性质3（红色节点的两个子节点均为黑色）。因此，调整操作的目标就是修复因新插入红色节点而可能破坏的红黑性质。

向上遍历：从新插入的红色节点开始，沿着从该节点到根节点的路径，逐层向上检查其父节点和祖父节点的关系，直到遇到以下情况之一停止：

达到根节点（此时调整完成）。

遇到黑色节点（父节点是黑色，则当前路径没有问题，调整完成）。

发现一个“祖父-父节点-（父节点的兄弟节点）”都是红色的模式，需要进行旋转和着色操作。

路径性质：在向上遍历时，需要关注两个关键点：

当前节点（红色或黑色）及其父节点（红色或黑色）的颜色。

父节点与祖父节点的相对位置关系（左/右）。

父节点与其兄弟节点的颜色（虽然兄弟节点颜色在遍历时可能未知，但会影响调整策略）。

（二）调整类型及处理（详细说明）

1.LL旋转（左左旋转）：

场景描述：假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的左孩子。同时，父节点`y`是其祖父节点`x`的左孩子。

旋转操作：

以祖父节点`x`为中心，进行右旋。

旋转方向：将父节点`y`向上移动，成为祖父节点`x`的根节点；将子节点`z`向上移动，成为父节点`y`的根节点。

着色规则：

将父节点`y`和子节点`z`的颜色都改为黑色。

将祖父节点`x`的颜色改为红色。

结果：经过这次旋转和着色：

性质3（红色节点的两个子节点均为黑色）在`y`和`z`这条路径上被修复。

但`x`（现在是`y`的父节点）和`y`变成了连续的红色节点（`x`-`y`），可能需要进一步向上调整。因此，调整过程不会在此停止，会继续检查`y`和`x`的关系。

图示（概念）：

```

x(黑)y(红)

//

//

y(红)----z(红)

/\

/\

z(红)...

\

...

```

旋转后：

```

y(黑)

/\

/\

x(红)z(黑)

/\

/\

......

\/

\/

...(新路径)

```

2.RR旋转（右右旋转）：

场景描述：与LL旋转对称。假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的右孩子。同时，父节点`y`是其祖父节点`x`的右孩子。

旋转操作：

以祖父节点`x`为中心，进行左旋。

旋转方向：将父节点`y`向上移动，成为祖父节点`x`的根节点；将子节点`z`向上移动，成为父节点`y`的根节点。

着色规则：

将父节点`y`和子节点`z`的颜色都改为黑色。

将祖父节点`x`的颜色改为红色。

结果：与LL旋转类似，修复了`y`和`z`这条路径的性质3，但可能需要继续向上调整。

图示（概念）：

```

x(黑)z(红)

\/

\/

y(红)

\/

\/

z(红)

\

...

```

旋转后：

```

z(黑)

/\

/\

y(红)x(红)

/\

/\

......

\/

\/

......

```

3.LR旋转（左右旋转）：

场景描述：更复杂的情况。假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的左孩子（这是LR的关键部分），同时父节点`y`是其祖父节点`x`的右孩子。

旋转操作（两步）：

第一步（左旋）：以父节点`y`为中心，进行左旋。这会使得`z`成为`y`的父节点。

```

x(黑)

/\

/\

y(红)...

\/

z(红)

```

左旋`y`后：

```

x(黑)

/\

/\

z(红)...

/\

/\

y(红)...

```

第二步（右旋）：以祖父节点`x`为中心，进行右旋。现在`z`是`x`的右孩子。

```

x(黑)

/\

/\

z(红)...

/\

/\

y(红)...

```

右旋`x`后：

```

z(黑)

/\

/\

y(红)x(红)

/\

/\

......

\/

\/

......

```

着色规则：

将父节点`y`和祖父节点`x`的颜色改为黑色。

将子节点`z`的颜色改为红色。

结果：修复了`y`和`z`这条路径的性质3，且`x`和`y`不再是连续的红色节点，调整过程可能停止。

4.RL旋转（右左旋转）：

场景描述：与LR旋转对称。假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的右孩子（这是RL的关键部分），同时父节点`y`是其祖父节点`x`的左孩子。

旋转操作（两步）：

第一步（右旋）：以父节点`y`为中心，进行右旋。这会使得`z`成为`y`的父节点。

```

x(黑)

/\

/\

...y(红)

/\

/\

z(红)...

```

右旋`y`后：

```

x(黑)

/\

/\

...z(红)

/\

/\

y(红)...

```

第二步（左旋）：以祖父节点`x`为中心，进行左旋。现在`z`是`x`的左孩子。

```

x(黑)

/\

/\

...z(红)

/\

/\

y(红)...

```

左旋`x`后：

```

z(黑)

/\

/\

y(红)x(红)

/\

/\

......

\/

\/

......

```

着色规则：与LR旋转相同。

将父节点`y`和祖父节点`x`的颜色改为黑色。

将子节点`z`的颜色改为红色。

结果：与LR旋转类似，修复并调整完成。

（三）终止条件（续）

调整完成标志：调整过程通过旋转和着色，最终达到以下状态之一即视为完成：

1.路径修复：从当前节点到根节点的路径上，不再存在连续的红色节点，且所有红黑性质均被满足。

2.到达根节点：调整过程向上传播至根节点，此时根节点自动为黑色（如果之前因连续红色而临时修改过根节点颜色，此时应恢复为黑色）。

3.无冲突：在向上遍历过程中，没有发现祖父-父节点-父节点兄弟节点均为红色的模式，则无需调整，直接结束。

迭代过程：调整过程可能是迭代的，即一次LL/RR/RL/RL调整可能只是解决了部分冲突，导致需要继续向上检查父节点和祖父节点。例如，在LL调整后，新的祖父节点（原父节点）和新的父节点（原子节点）可能又变成了红色，如果它们也是红色的，就需要对新的父节点进行LL或RR调整。这个过程会一直持续，直到满足终止条件。

三、红黑树的删除操作（续）

（一）删除步骤（详细说明）

1.查找与定位节点：

目标节点：确定要删除的节点`t`。

查找路径：沿二叉查找树的规则查找节点`t`的路径。

子节点情况：

无子节点（叶子节点）：最简单的情况，直接删除该节点。

一个子节点：用其子节点替换该节点，然后删除原子节点（相当于删除一个叶子节点）。

两个子节点：找到`t`的中序后继节点`s`（或中序前驱节点，后继更常用），将`s`的值复制到`t`的位置，然后删除原`s`节点。由于`s`至多只有一个子节点，问题就转化为前两种情况。

2.执行删除：

删除操作本身：在树中移除目标节点`t`（无论是直接删除叶子，还是用后继替换再删除后继）。

删除的影响：删除一个节点，特别是删除一个黑色节点，可能会破坏红黑树的性质，主要是：

性质4（黑高）：从任何节点到其叶子的两条简单路径可能不再具有相同的黑色节点数。

性质3（红色节点的子节点为黑色）：如果删除的黑色节点有一个红色的子节点，那么这条路径的黑色节点数会减少。

引入“双重黑”概念：为了不直接破坏黑高，引入一个虚拟的“黑色”节点，称为双重黑（DoubleBlack）。当删除一个黑色节点时，可以在其位置放置一个双重黑，然后通过一系列操作将这个双重黑“吸收”掉（即消除双重黑），同时恢复红黑树的性质。最终结果是，实际树的大小减少了1（因为删除了一个节点），并且黑高保持不变。

3.修复操作（吸收双重黑）：

修复目标：从被删除节点`t`的位置（现在是双重黑）开始，向上传播，寻找并消除双重黑。

传播路径：双重黑会向上影响其父节点`p`。因为双重黑等效于其父节点黑高加1，这会导致`p`的黑高计算出现问题（相对于其兄弟节点）。

关键角色：

`p`（父节点）：当前需要被修复的节点，初始时为双重黑。

`s`（兄弟节点）：`p`的非空子节点。

`sl`（左孩子）：`s`的左孩子（可能为红或黑）。

`sr`（右孩子）：`s`的右孩子（可能为红或黑）。

处理策略：根据`p`和`s`的颜色关系，以及`s`及其子节点的颜色，分为多种情况处理。核心思想是：如果`s`及其子节点能够“补偿”掉`p`的额外黑色，则修复完成；如果不能，则通过旋转和着色将问题向上传递。

（二）调整方法（详细说明）

1.红色补丁法（详细解释）：

核心思想：与插入调整类似，删除调整的核心也是通过旋转和着色来维护性质。引入“红色补丁”的概念可以更清晰地理解这个过程。当从`p`（双重黑）向上传播时，可以在`p`的兄弟`s`上“贴”一个红色补丁。

补丁作用：这个红色补丁等效于`s`是红色的，并且其子节点是黑色的（如果`s`原本就是红色，则补丁直接生效；如果`s`原本是黑色，则贴上补丁后，`s`变为红色，其子节点变为黑色，从而补偿了`p`的额外黑色）。

传播过程：

如果`s`上有红色补丁（即`s`是红色的），则可以将补丁移到`p`上（`p`变为双重黑），然后消除`s`上的补丁（`s`变回黑色），此时`p`仍然双重黑，需要继续向上传播。

如果`s`上没有红色补丁（即`s`是黑色的），则需要检查`s`的子节点，通过旋转和着色来消除`p`上的双重黑。

终止条件：调整过程终止于以下情况：

到达根节点：根节点不能是双重黑，因此可以将双重黑传播到根节点，然后将其移除，树的大小减1，黑高不变。

修复完成：通过一系列操作成功消除了`p`上的双重黑，并且没有需要向上继续传播的问题。

2.调整场景（分类讨论）：

场景1：兄弟节点`s`为红色

操作：

1.将`s`着色为黑色。

2.将`p`着色为红色。

3.以`p`为中心，进行以`p`为轴心的旋转（左旋或右旋，取决于`s`是`p`的左/右孩子）。

结果：这一步消除了`p`上的双重黑（双重黑被“吸收”到`p`上，然后`p`被着色为红色，`s`被着色为黑色），并且将问题限制在`p`的父节点上。此时需要继续检查`p`及其新的兄弟节点。

注意：这里的旋转是关键，它将`s`的红色性质向上传递，而不是向下传递到`s`的子节点。

场景2：兄弟节点`s`为黑色

子场景2.1：`s`的左孩子`sl`为黑色，右孩子`sr`为黑色

操作：

1.将`s`着色为红色。

结果：通过将`s`着色为红色，相当于在`s`这条路径上补偿了一个黑色，从而消除了`p`上的双重黑。

终止：调整完成，无需继续向上传播。

子场景2.2：`s`的左孩子`sl`为红色，右孩子`sr`为黑色

操作：

1.将`sl`着色为黑色。

2.将`s`着色为红色。

3.以`s`为中心，进行以`s`为轴心的左旋。

结果：这一系列操作消除了`p`上的双重黑。左旋将`sl`的红色性质向上传递到`s`，然后`s`被着色为红色，从而补偿了`p`的黑色。

终止：调整完成，无需继续向上传播。

子场景2.3：`s`的左孩子`sl`为黑色，右孩子`sr`为红色

操作：

1.将`sr`着色为黑色。

2.将`p`着色为红色。

3.以`p`为中心，进行以`p`为轴心的右旋。

结果：这一系列操作消除了`p`上的双重黑。右旋将`sr`的红色性质向上传递到`p`，然后`p`被着色为红色，从而补偿了`s`这条路径的黑色。

终止：调整完成，无需继续向上传播。

子场景2.4：`s`的左孩子`sl`为红色，右孩子`sr`为红色（不常见于正常调整流程，但理论上可能）

操作：

1.将`sl`着色为黑色。

2.将`sr`着色为黑色。

3.将`p`着色为红色。

4.以`p`为中心，进行以`p`为轴心的右旋。

结果：通过将`sl`和`sr`都着色为黑色，相当于在`s`这条路径上补偿了两个黑色，从而消除了`p`上的双重黑。然后右旋将`p`的红色性质传递到其父节点。

终止：调整完成，无需继续向上传播。

3.调整流程总结：

从双重黑节点开始，向上传播。

根据父节点和兄弟节点的颜色、兄弟子节点的颜色，选择上述场景之一执行操作。

每次操作后，检查`p`是否仍然双重黑。如果是，继续向上传播；如果不是，则调整完成。

最终，双重黑会被“吸收”到根节点，然后根节点被着色为黑色（如果之前被临时修改过），树的大小减1，黑高保持不变。

（三）终止条件（续）

调整完成：当`p`（最初的双重黑节点）不再双重黑时，调整过程结束。这意味着：

通过旋转和着色，双重黑的影响已经被消除。

树的形状和红黑性质得到了恢复。

实际效果：删除操作的实际效果是：

移除了目标节点`t`。

通过引入和吸收双重黑，维护了红黑树的黑高和其它性质。

最终树的大小减少了1。

所有剩余节点的黑高仍然保持一致。

五、总结（续）

红黑树的插入和删除操作是其在实践中得以广泛应用的关键。它们的核心在于通过局部调整机制（旋转和着色）来维护树的平衡和红黑性质。

插入：关键在于处理新插入的红色节点可能引发的连续红色问题。通过LL、RR、LR、RL四种旋转（或其中两步的组合）以及相应的着色规则，可以在O(logn)时间内将插入操作的影响限制在常数个节点内。

删除：关键在于处理删除黑色节点后可能破坏的黑高和连续红色问题。通过引入“双重黑”概念和“红色补丁”方法，以及针对不同兄弟节点及其子节点颜色的多种调整策略，可以在O(logn)时间内恢复树的平衡和性质。

通用性：无论是插入还是删除，调整过程都可能涉及多轮向上传播，直到影响被吸收或到达根节点。理解这些调整场景和操作的具体步骤，是掌握红黑树操作的关键。通过这些机制，红黑树能够确保在最坏情况下也能提供高效的查找、插入和删除操作。

一、红黑树概述

红黑树是一种自平衡二叉查找树，通过维护节点颜色的红黑属性和特定的树形性质来保证树的高度平衡，从而实现高效的插入和删除操作。其关键特性包括：

（一）节点颜色

1.每个节点只能是红色或黑色。

2.根节点为黑色。

3.红色节点的两个子节点均为黑色（从任一节点到其所有后代的外部路径上不能有两个连续的红色节点）。

4.从任一节点到其所有叶子的所有简单路径都包含相同数目的黑色节点（黑高）。

二、红黑树的插入操作

插入操作遵循二叉查找树的常规插入方法，随后通过旋转和重新着色调整树形以满足红黑性质。

（一）插入步骤

1.常规插入：

-在二叉查找树中查找合适位置插入新节点，默认节点为红色。

-由于插入红色节点可能破坏红黑性质，需进行后续调整。

2.调整操作：

-从插入节点向上遍历，根据父节点颜色和兄弟节点关系判断调整类型。

-可能涉及以下情况：

(1)祖父节点为黑色：直接回退至父节点检查。

(2)祖父节点为红色：存在父亲是红色或黑色两种子场景。

（二）调整类型及处理

1.LL/RR旋转（单旋转）：

-LL型：右旋调整，适用于祖父-父节点-插入节点均为红色且插入节点在父节点右侧。

-RR型：左旋调整，适用于祖父-父节点-插入节点均为红色且插入节点在父节点左侧。

2.LR/RL旋转（双旋转）：

-LR型：先左旋父节点，再右旋祖父节点。

-RL型：先右旋父节点，再左旋祖父节点。

-通过旋转将连续红色节点分离，同时重新着色。

（三）终止条件

-调整过程持续向上传播，直至：

1.遇到黑色节点或到达根节点。

2.所有红黑性质重新满足。

三、红黑树的删除操作

删除操作先按二叉查找树规则移除节点，再通过类似插入的调整方法修复红黑性质。

（一）删除步骤

1.节点替换：

-若待删除节点有双孩子，用后继节点替代并删除后继节点（后继节点必为单孩子或无孩子）。

-若为单孩子或无孩子，直接删除并标记为红色。

2.重新着色：

-删除黑色节点可能导致黑高不均，需从子节点向上调整。

（二）调整方法

1.红色补丁法：

-删除黑色节点后，补一个红色“补丁”以保持黑高平衡。

-补丁向上传播过程中，通过旋转和着色消除冲突。

2.调整场景：

-删除节点为红色：直接回退至父节点。

-删除节点为黑色：需处理补丁与父节点、兄弟节点的颜色关系，可能涉及：

(1)兄弟节点为红色：先旋转调整，再统一处理。

(2)兄弟节点为黑色：根据兄弟子节点颜色进行多种旋转（如LL、LR等）。

（三）终止条件

-调整过程直至补丁到达根节点或树形满足红黑性质。

四、示例操作

（一）插入示例

-插入值：15→常规插入为红色，父节点（10）为红色，祖父（5）为黑色。

-父节点与祖父均为红色→父节点右旋（若插入右侧），祖父-父节点变为红色。

-祖父节点（10）变为红色，需进一步调整（类似插入流程）。

（二）删除示例

-删除值：10→假设替换为后继节点12（红色）。

-补丁（12）向上传播，若兄弟节点（15）为红色：

1.父节点左旋（若补丁在左）。

2.重新着色后，补丁变为黑色，继续向上传播。

五、总结

红黑树的插入和删除操作通过“旋转+着色”的局部调整策略，确保在O(logn)时间内维持平衡。关键在于理解：

1.红黑性质是动态维护的，每次操作需从局部向上传播。

2.调整类型（单/双旋转）与父子兄弟关系密切相关。

3.终止条件通常为到达根节点或性质重新满足。

二、红黑树的插入操作（续）

（一）插入步骤（续）

1.常规插入：

查找位置：从根节点开始，按照二叉查找树的规则（节点值小于父节点则走左子树，大于父节点则走右子树）向下查找，直到找到空节点作为新节点的插入位置。

创建节点：在查找到的空位置创建一个新节点，该节点的值为其插入值。

初始着色：新插入的节点默认被着色为红色。这一步是为了后续的调整：因为插入红色节点最容易破坏红黑树的某些性质（尤其是性质3：红色节点的两个子节点均为黑色），但相对简单，且调整过程更容易处理红色节点引发的冲突。

示例：假设我们要向红黑树中插入值`x`。从根节点R开始比较，找到路径R->A->C。比较`x`与节点C的值。如果`x<C`，则沿C的左子树继续查找；如果`x>C`，则沿C的右子树继续查找。最终找到空子节点，在空位置创建节点`x`，并将其着色为红色。

2.调整操作（详细说明）：

触发调整：为什么需要调整？因为虽然根节点总是黑色（性质2），但新插入的节点是红色。如果连续有两个红色节点（例如，新节点及其父节点都是红色），就会直接违反性质3（红色节点的两个子节点均为黑色）。因此，调整操作的目标就是修复因新插入红色节点而可能破坏的红黑性质。

向上遍历：从新插入的红色节点开始，沿着从该节点到根节点的路径，逐层向上检查其父节点和祖父节点的关系，直到遇到以下情况之一停止：

达到根节点（此时调整完成）。

遇到黑色节点（父节点是黑色，则当前路径没有问题，调整完成）。

发现一个“祖父-父节点-（父节点的兄弟节点）”都是红色的模式，需要进行旋转和着色操作。

路径性质：在向上遍历时，需要关注两个关键点：

当前节点（红色或黑色）及其父节点（红色或黑色）的颜色。

父节点与祖父节点的相对位置关系（左/右）。

父节点与其兄弟节点的颜色（虽然兄弟节点颜色在遍历时可能未知，但会影响调整策略）。

（二）调整类型及处理（详细说明）

1.LL旋转（左左旋转）：

场景描述：假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的左孩子。同时，父节点`y`是其祖父节点`x`的左孩子。

旋转操作：

以祖父节点`x`为中心，进行右旋。

旋转方向：将父节点`y`向上移动，成为祖父节点`x`的根节点；将子节点`z`向上移动，成为父节点`y`的根节点。

着色规则：

将父节点`y`和子节点`z`的颜色都改为黑色。

将祖父节点`x`的颜色改为红色。

结果：经过这次旋转和着色：

性质3（红色节点的两个子节点均为黑色）在`y`和`z`这条路径上被修复。

但`x`（现在是`y`的父节点）和`y`变成了连续的红色节点（`x`-`y`），可能需要进一步向上调整。因此，调整过程不会在此停止，会继续检查`y`和`x`的关系。

图示（概念）：

```

x(黑)y(红)

//

//

y(红)----z(红)

/\

/\

z(红)...

\

...

```

旋转后：

```

y(黑)

/\

/\

x(红)z(黑)

/\

/\

......

\/

\/

...(新路径)

```

2.RR旋转（右右旋转）：

场景描述：与LL旋转对称。假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的右孩子。同时，父节点`y`是其祖父节点`x`的右孩子。

旋转操作：

以祖父节点`x`为中心，进行左旋。

旋转方向：将父节点`y`向上移动，成为祖父节点`x`的根节点；将子节点`z`向上移动，成为父节点`y`的根节点。

着色规则：

将父节点`y`和子节点`z`的颜色都改为黑色。

将祖父节点`x`的颜色改为红色。

结果：与LL旋转类似，修复了`y`和`z`这条路径的性质3，但可能需要继续向上调整。

图示（概念）：

```

x(黑)z(红)

\/

\/

y(红)

\/

\/

z(红)

\

...

```

旋转后：

```

z(黑)

/\

/\

y(红)x(红)

/\

/\

......

\/

\/

......

```

3.LR旋转（左右旋转）：

场景描述：更复杂的情况。假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的左孩子（这是LR的关键部分），同时父节点`y`是其祖父节点`x`的右孩子。

旋转操作（两步）：

第一步（左旋）：以父节点`y`为中心，进行左旋。这会使得`z`成为`y`的父节点。

```

x(黑)

/\

/\

y(红)...

\/

z(红)

```

左旋`y`后：

```

x(黑)

/\

/\

z(红)...

/\

/\

y(红)...

```

第二步（右旋）：以祖父节点`x`为中心，进行右旋。现在`z`是`x`的右孩子。

```

x(黑)

/\

/\

z(红)...

/\

/\

y(红)...

```

右旋`x`后：

```

z(黑)

/\

/\

y(红)x(红)

/\

/\

......

\/

\/

......

```

着色规则：

将父节点`y`和祖父节点`x`的颜色改为黑色。

将子节点`z`的颜色改为红色。

结果：修复了`y`和`z`这条路径的性质3，且`x`和`y`不再是连续的红色节点，调整过程可能停止。

4.RL旋转（右左旋转）：

场景描述：与LR旋转对称。假设当前节点为`z`（红色），其父节点`y`为红色，祖父节点`x`为黑色。并且`z`是其父节点`y`的右孩子（这是RL的关键部分），同时父节点`y`是其祖父节点`x`的左孩子。

旋转操作（两步）：

第一步（右旋）：以父节点`y`为中心，进行右旋。这会使得`z`成为`y`的父节点。

```

x(黑)

/\

/\

...y(红)

/\

/\

z(红)...

```

右旋`y`后：

```

x(黑)

/\

/\

...z(红)

/\

/\

y(红)...

```

第二步（左旋）：以祖父节点`x`为中心，进行左旋。现在`z`是`x`的左孩子。

```

x(黑)

/\

/\

...z(红)

/\

/\

y(红)...

```

左旋`x`后：

```

z(黑)

/\

/\

y(红)x(红)

/\

/\

......

\/

\/

......

```

着色规则：与LR旋转相同。

将父节点`y`和祖父节点`x`的颜色改为黑色。

将子节点`z`的颜色改为红色。

结果：与LR旋转类似，修复并调整完成。

（三）终止条件（续）

调整完成标志：调整过程通过旋转和着色，最终达到以下状态之一即视为完成：

1.路径修复：从当前节点到根节点的路径上，不再存在连续的红色节点，且所有红黑性质均被满足。

2.到达根节点：调整过程向上传播至根节点，此时根节点自动为黑色（如果之前因连续红色而临时修改过根节点颜色，此时应恢复为黑色）。

3.无冲突：在向上遍历过程中，没有发现祖父-父节点-父节点兄弟节点均为红色的模式，则无需调整，直接结束。

迭代过程：调整过程可能是迭代的，即一次LL/RR/RL/RL调整可能只是解决了部分冲突，导致需要继续向上检查父节点和祖父节点。例如，在LL调整后，新的祖父节点（原父节点）和新的父节点（原子节点）可能又变成了红色，如果它们也是红色的，就需要对新的父节点进行LL或RR调整。这个过程会一直持续，直到满足终止条件。

三、红黑树的删除操作（续）

（一）删除步骤（详细说明）

1.查找与定位节点：

目标节点：确定要删除的节点`t`。

查找路径：沿二叉查找树的规则查找节点`t`的路径。

子节点情况：

无子节点（叶子节点）：最简单的情况，直接删除该节点。

一个子节点：用其子节点替换该节点，然后删除原子节点（相当于删除一个叶子节点）。

两个子节点：找到`t`的中序后继节点`s`（或中序前驱节点，后继更常用），将`s`的值复制到`t`的位置，然后删除原`s`节点。由于`s`至多只有一个子节点，问题就转化为前两种情况。

2.执行删除：

删除操作本身：在树中移除目标节点`t`（无论是直接删除叶子，还是用后继替换再删除后继）。

删除的影响：删除一个节点，特别是删除一个黑色节点，可能会破坏红黑树的性质，主要是：

性质4（黑高）：从任何节点到其叶子的两条简单路径可能不再具有相同的黑色节点数。

性质3（红色节点的子节点为黑色）：如果删除的黑色节点有一个红色的子节点，那么这条路径的黑色节点数会减少。

引入“双重黑”概念：为了不直接破坏黑高，引入一个虚拟的“黑色”节点，称为双重黑（DoubleBlack）。当删除一个黑色节点时，可以在其位置放置一个双重黑，然后通过一系列操作将这个双重黑“吸收”掉（即消除双重黑），同时恢复红黑树的性质。最终结果是，实际树的大小减少了1（因为删除了一个节点），并且黑高保持不变。

3.修复操作（吸收双重黑）：

修复目标：从被删除节点`t`的位置（现在是双重黑）开始，向上传播，寻找并消除双重黑。

传播路径：双重黑会向上影响其父节点`p`。因为双重黑等效于其父节点黑高加1，这会导致`p`的黑高计算出现问题（相对于其兄弟节点）。

关键角色：

`p`（父节点）：当前需要被修复的节点，初始时为双重黑。

`s`（兄弟节点）：`p`的非空子节点。

`sl`（左孩子）：`s`的左孩子（可能为红或黑）。

`sr`（右孩子）：`s`的右孩子（可能为红或黑）。

处理策略：根据`p`和`s`的颜色关系，以及`s`及其子节点的颜色，分为多种情况处理。核心思想是：如果`s`及其子节点能够“补偿”掉`p`的额外黑色，则修复完成；如果不能，则通过旋转和着色将问题向上传递。

（二）调整方法（详细说明）

1.红色补丁法（详细解释）：

核心思想：与插入调整类似，删除调整的核心也是通过旋转和着色来维护性质。引入“红色补丁”的概念可以更清晰地理解这个过程。当从`p`（双重黑）向上传播时，可以在`p`的兄弟`s`上“贴”一个红色补丁。

补丁作用：这个红色补丁等效于`s`是红色的，并且其子节点是黑色的（如果`s`原本就是红色，则补丁直接生效；如果`s`原本是黑色，则贴上补丁后，`s`变为红色，其子节点变为黑色，从而补偿了`p`的额外黑色）。

传播过程：

如果`s`上有红色补丁（即`s`是红色的），则可以将补丁移到`p`上（`p`变为双重黑），然后消除`s`上的补丁（`s`变回黑色），此时`p`仍然双重黑，需要继续向上传播。

如果`s`上没有红色补丁（即`s`是黑色的），则需要检查`s`的子节点，通过旋转和着色来消除`p`上的双重黑。

终止条件：调整过程终止于以下情况：

到达根节点：根节点不能是双重黑，因此可以将双重黑传播到根节点，然后将其移除，树的大小减1，黑高不变。

修复完成：通过一系列操作成功消除了`p`上的双重黑，并且没有需要向上继续传播的问题。

2.调整场景（分类讨论）：

场景1：兄弟节点`s`为红色

操作：

1.将`s`着色为黑色。

2.将`p`着色为红色。

3.以`p`为中心，进行以`p`为轴心的旋转（左旋或右旋，取决于`s`是`p`的左/右孩子）。

结果：这一步消除了`p`