红黑树的插入操作

字数 2043 2025-11-11 19:11:51

红黑树的插入操作

红黑树是一种自平衡的二叉搜索树，它在插入和删除操作后通过特定的规则和旋转来维持平衡，从而保证最坏情况下的时间复杂度为O(log n)。今天我们将重点讲解红黑树的插入操作。

1. 红黑树的性质

在了解插入操作之前，我们必须牢记红黑树必须满足的五条性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶子节点（NIL节点，空节点）都是黑色。
如果一个节点是红色的，则它的两个子节点都是黑色的。（即不能有两个连续的红色节点）
从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。（这被称为黑色高度平衡）

2. 插入操作的第一步：基本二叉搜索树插入

红黑树的插入操作首先遵循标准二叉搜索树（BST）的规则：

从根节点开始，与待插入节点z的键值进行比较。
如果z.key小于当前节点的键值，则进入左子树；否则进入右子树。
重复此过程，直到找到一个空位置（NIL节点）。
将新节点z插入到这个空位置。

初始时，我们将新插入的节点着为红色。为什么？因为如果着为黑色，会立即违反性质5（从根到叶子的路径上黑色节点数不再相等），修正起来会非常困难，可能需要对整棵树进行调整。而着为红色，可能违反性质2（根为黑）或性质4（无连续红节点），但影响的只是局部结构，我们可以通过相对简单的调整来修复。

3. 插入操作的第二步：调整颜色与旋转以恢复平衡

插入红色节点后，我们检查是否违反了红黑树的性质。可能的情况如下：

情况1：新节点z是根节点。
- 问题：违反了性质2（根节点必须是黑色）。
- 修复方法：非常简单，直接将z重新着为黑色即可。
情况2：z的父节点P是黑色。
- 问题：没有违反任何性质。因为插入红色节点没有改变黑色高度，也没有产生连续的红节点（父节点是黑的）。
- 修复方法：无需任何操作，树仍然是平衡的。

如果上述两种情况都不满足，即z不是根节点，且z的父节点P是红色的，那么就违反了性质4，出现了连续的红色节点。此时，我们需要根据z的叔父节点（即z祖父节点的另一个子节点，记为U）的颜色来进行不同的调整。我们定义z的祖父节点为G。

情况3：z的叔父节点U是红色的。
- 场景：P和U都是红色。
- 修复方法（重新着色）：
  1. 将父节点P和叔父节点U都着为黑色。
  2. 将祖父节点G着为红色。
  3. 现在，以G为根的子树在局部恢复了平衡（解决了P和z的连续红色问题）。
  4. 但是，G被染红了，它可能也有一个红色的父节点，从而在更高层产生连续红色节点的问题。因此，我们将G视为新的z，从步骤3的开始重新开始整个调整过程（递归向上处理）。
(图中三角形代表子树)
情况4：z的叔父节点U是黑色的（或NIL）。 这种情况需要旋转。它又分为两种子情况，取决于z和其父节点P的方位关系。
- 情况4a：左右情况（LR） - P是G的左孩子，z是P的右孩子。
  - 修复方法：
    1. 以P为支点进行左旋。左旋后，z成为P的父节点，原来的P-z关系被反转。
    2. 经过这次旋转，情况4a被转换成了情况4b。现在，原本的z节点有了一个新的父节点（即旋转前的z），我们接下来就按照情况4b来处理这个“新的z”（其实就是原来的z，但它在树中的相对位置变了）。
- 情况4b：左左情况（LL） - P是G的左孩子，z是P的左孩子。（情况4a旋转后也会变成此情况）
  - 修复方法（旋转+重新着色）：
    1. 将父节点P着为黑色。
    2. 将祖父节点G着为红色。
    3. 以G为支点进行右旋。
    4. 旋转后，P成为了原来G位置的新根（黑色），G成为了P的右孩子（红色）。这既消除了连续红色节点，又保持了黑色高度平衡。
- 对称地，还存在“右左情况（RL）”和“右右情况（RR）”，处理方式与4a和4b对称（左右旋转方向互换即可）。
(情况4a和4b示意图，左旋右旋修复了结构)

4. 操作总结与复杂度

红黑树的插入过程可以总结为：

BST插入：按照二叉搜索树规则插入新节点，并将其着为红色。
循环调整：如果新节点是根，染黑（情况1）。否则，进入一个循环，只要不违反规则或未调整到根，就持续判断：
- 如果父节点是黑色，结束（情况2）。
- 如果叔父节点是红色，执行重新着色，并将问题上移（情况3）。
- 如果叔父节点是黑色，先通过旋转将情况调整为“直链”（LL或RR），然后通过一次旋转和重新着色完成修复（情况4）。修复后平衡立即恢复，循环结束。

时间复杂度：插入操作的时间复杂度为O(log n)。因为BST的查找插入是O(log n)，而调整过程（旋转和重新着色）最多沿着路径向上回溯O(log n)的高度，且旋转操作是常数时间O(1)。

通过这种严谨的、分情况的调整策略，红黑树在每次插入后都能高效地恢复平衡，确保了其优异的性能。

红黑树的插入操作红黑树是一种自平衡的二叉搜索树，它在插入和删除操作后通过特定的规则和旋转来维持平衡，从而保证最坏情况下的时间复杂度为O(log n)。今天我们将重点讲解红黑树的插入操作。 1. 红黑树的性质在了解插入操作之前，我们必须牢记红黑树必须满足的五条性质：每个节点要么是红色，要么是黑色。根节点是黑色。每个叶子节点（NIL节点，空节点）都是黑色。如果一个节点是红色的，则它的两个子节点都是黑色的。（即不能有两个连续的红色节点）从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。（这被称为黑色高度平衡） 2. 插入操作的第一步：基本二叉搜索树插入红黑树的插入操作首先遵循标准二叉搜索树（BST）的规则：从根节点开始，与待插入节点 z 的键值进行比较。如果 z.key 小于当前节点的键值，则进入左子树；否则进入右子树。重复此过程，直到找到一个空位置（NIL节点）。将新节点 z 插入到这个空位置。初始时，我们将新插入的节点着为红色。为什么？因为如果着为黑色，会立即违反性质5（从根到叶子的路径上黑色节点数不再相等），修正起来会非常困难，可能需要对整棵树进行调整。而着为红色，可能违反性质2（根为黑）或性质4（无连续红节点），但影响的只是局部结构，我们可以通过相对简单的调整来修复。 3. 插入操作的第二步：调整颜色与旋转以恢复平衡插入红色节点后，我们检查是否违反了红黑树的性质。可能的情况如下：情况1：新节点 z 是根节点。问题：违反了性质2（根节点必须是黑色）。修复方法：非常简单，直接将 z 重新着为黑色即可。情况2： z 的父节点 P 是黑色。问题：没有违反任何性质。因为插入红色节点没有改变黑色高度，也没有产生连续的红节点（父节点是黑的）。修复方法：无需任何操作，树仍然是平衡的。如果上述两种情况都不满足，即 z 不是根节点，且 z 的父节点 P 是红色的，那么就违反了性质4，出现了连续的红色节点。此时，我们需要根据 z 的叔父节点（即 z 祖父节点的另一个子节点，记为 U ）的颜色来进行不同的调整。我们定义 z 的祖父节点为 G 。情况3： z 的叔父节点 U 是红色的。场景： P 和 U 都是红色。修复方法（重新着色）：将父节点 P 和叔父节点 U 都着为黑色。将祖父节点 G 着为红色。现在，以 G 为根的子树在局部恢复了平衡（解决了 P 和 z 的连续红色问题）。但是， G 被染红了，它可能也有一个红色的父节点，从而在更高层产生连续红色节点的问题。因此，我们将 G 视为新的 z ，从步骤3的开始重新开始整个调整过程（递归向上处理）。 (图中三角形代表子树) 情况4： z 的叔父节点 U 是黑色的（或NIL）。这种情况需要旋转。它又分为两种子情况，取决于 z 和其父节点 P 的方位关系。情况4a：左右情况（LR） - P 是 G 的左孩子， z 是 P 的右孩子。修复方法：以 P 为支点进行左旋。左旋后， z 成为 P 的父节点，原来的 P - z 关系被反转。经过这次旋转，情况4a被转换成了情况4b。现在，原本的 z 节点有了一个新的父节点（即旋转前的 z ），我们接下来就按照情况4b来处理这个“新的 z ”（其实就是原来的 z ，但它在树中的相对位置变了）。情况4b：左左情况（LL） - P 是 G 的左孩子， z 是 P 的左孩子。（情况4a旋转后也会变成此情况）修复方法（旋转+重新着色）：将父节点 P 着为黑色。将祖父节点 G 着为红色。以 G 为支点进行右旋。旋转后， P 成为了原来 G 位置的新根（黑色）， G 成为了 P 的右孩子（红色）。这既消除了连续红色节点，又保持了黑色高度平衡。对称地，还存在“右左情况（RL）”和“右右情况（RR）”，处理方式与4a和4b对称（左右旋转方向互换即可）。 (情况4a和4b示意图，左旋右旋修复了结构) 4. 操作总结与复杂度红黑树的插入过程可以总结为： BST插入：按照二叉搜索树规则插入新节点，并将其着为红色。循环调整：如果新节点是根，染黑（情况1）。否则，进入一个循环，只要不违反规则或未调整到根，就持续判断：如果父节点是黑色，结束（情况2）。如果叔父节点是红色，执行重新着色，并将问题上移（情况3）。如果叔父节点是黑色，先通过旋转将情况调整为“直链”（LL或RR），然后通过一次旋转和重新着色完成修复（情况4）。修复后平衡立即恢复，循环结束。时间复杂度：插入操作的时间复杂度为O(log n)。因为BST的查找插入是O(log n)，而调整过程（旋转和重新着色）最多沿着路径向上回溯O(log n)的高度，且旋转操作是常数时间O(1)。通过这种严谨的、分情况的调整策略，红黑树在每次插入后都能高效地恢复平衡，确保了其优异的性能。