每日学习一个数据结构-红黑树

什么是红黑树？

红黑树（Red-Black Tree）是一种自平衡的二叉查找树（Binary Search Tree, BST）。红黑树的设计目的是为了在插入和删除操作期间保持树的平衡，从而确保操作的时间复杂度为 O(log n)，其中 n 是树中的节点数量。这种平衡有助于在最坏情况下也保持良好的性能表现。

示意图

红黑树的特点

红黑树具有以下五个性质，这些性质确保了红黑树的自平衡性：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL 节点，空节点）都是黑色。
4. 如果一个节点是红色的，则它的两个子节点必须是黑色的（即，红色节点不能连续出现，或者说红色节点的孩子必须是黑色）。
5. 任意节点到其每个叶子节点的所有路径上包含相同数目的黑色节点（这被称为“黑色高度”）。

红黑树的节点结构

通常情况下，红黑树的节点除了包含关键字、左子树指针、右子树指针和父节点指针之外，还会包含一个颜色属性（红色或黑色）。这里的“红色”和“黑色”并不是真正的颜色，而是逻辑标记，用来帮助算法执行自平衡操作。

插入和删除操作

在红黑树中插入或删除节点时，可能会破坏上述的一些性质。因此，在插入或删除操作之后，需要进行一系列的旋转（rotation）和重新着色（recoloring）操作，以恢复红黑树的性质。

旋转操作

旋转操作分为两种：左旋（Left Rotation）和右旋（Right Rotation）。这两种操作可以改变树的形状，但不会改变树的排序顺序。

• 左旋：对于一个节点 x，其右孩子 y 成为新的根节点，x 成为 y 的左子树。
• 右旋：对于一个节点 y，其左孩子 x 成为新的根节点，y 成为 x 的右子树。

重新着色

重新着色是指改变节点的颜色以满足红黑树的性质。

红黑树的应用

红黑树因其优良的性能和相对简单的自平衡机制，在多种场景下得到广泛应用，尤其是在计算机科学领域，如：

• 关联数组：在 C++ STL 中的 std::map 和 std::set，以及 Java 的 TreeMap 和 TreeSet，都使用了红黑树作为底层实现。
• 数据库管理系统：一些数据库管理系统使用红黑树来组织索引数据。
• 操作系统调度器：一些操作系统中的进程调度算法也使用红黑树来维护进程队列。

红黑树的优点在于它能够在 O(log n) 时间内完成查找、插入和删除操作，同时保持较好的空间效率。因此，它成为许多高效数据结构和算法的基础之一。

树的构造过程

红黑树的构造过程通常涉及插入新节点、删除节点以及必要的自平衡调整。构造过程的关键是在插入或删除节点后，保持红黑树的五个性质不变。下面是红黑树插入新节点的具体步骤及其自平衡调整过程。

插入新节点

1. 插入操作：

   • 新节点总是以红色插入。这是因为红色节点意味着其父节点是黑色，这样插入一个红色节点不会立即违反红黑树的性质。
   • 新节点插入到正确的位置，就像在普通的二叉查找树中一样。具体来说，新节点插入到叶节点的位置（此时的叶节点是指树中没有子节点的节点）。

2. 修复插入后的不平衡：

   • 插入新节点后，可能会导致红黑树的性质被破坏。特别是性质 4（红色节点不能有红色子节点）可能会被破坏。因此，需要进行一系列调整来恢复红黑树的性质。
   • 根据插入节点的位置以及其父节点和叔叔节点（如果有）的颜色，采取不同的调整策略。

自平衡调整策略

调整策略主要包括以下几种情况：

1. Case 1: 新节点是根节点：

   • 如果新插入的节点成为了树的根节点，那么只需简单地将新节点的颜色改为黑色即可。

2. Case 2: 叔叔节点是红色：

   • 如果新节点的叔叔节点是红色，那么可以将新节点的父节点和叔叔节点都设为黑色，而祖父节点设为红色。
   • 然后，将祖父节点设为当前节点，继续向上调整。

3. Case 3: 叔叔节点是黑色（或不存在）：

   • 如果新节点的叔叔节点是黑色或不存在（即新节点的父节点是祖父节点的唯一子节点），则需要进行旋转和重新着色操作来恢复红黑树的性质。

   这种情况又分为几种子情况：

   • Case 3a: 新节点是其父节点的右子节点，且父节点是祖父节点的左子节点：

     • 执行左旋操作，将新节点的父节点变为当前节点，并进行 Case 3b 的检查。

   • Case 3b: 新节点是其父节点的左子节点，且父节点是祖父节点的左子节点：

     • 将新节点的父节点设为黑色，祖父节点设为红色。
     • 对祖父节点执行右旋操作。

   • Case 3c: 新节点是其父节点的左子节点，且父节点是祖父节点的右子节点：

     • 执行右旋操作，将新节点的父节点变为当前节点，并进行 Case 3d 的检查。

   • Case 3d: 新节点是其父节点的右子节点，且父节点是祖父节点的右子节点：

     • 将新节点的父节点设为黑色，祖父节点设为红色。
     • 对祖父节点执行左旋操作。

示例

假设我们要在一个空的红黑树中依次插入节点 10、20、30 和 40。

1. 插入节点 10：

   • 作为第一个节点，插入后设为黑色。

2. 插入节点 20：

   • 作为右子节点插入，设为红色。
   • 无需调整，因为只有一个节点，没有违反红黑树性质。

3. 插入节点 30：

   • 作为 20 的右子节点插入，设为红色。
   • 此时，20 和 30 都是红色，违反性质 4，需要调整。
   • 由于 10（祖父节点）是黑色，且 20（父节点）的兄弟节点为空，故采用 Case 3b 的处理方式。
   • 将 20 设为黑色，10 设为红色，并对 10 执行右旋。

4. 插入节点 40：

   • 作为 30 的右子节点插入，设为红色。
   • 此时，30 和 40 都是红色，需要调整。
   • 由于 20（祖父节点）是黑色，且 30（父节点）的兄弟节点为空，故采用 Case 3d 的处理方式。
   • 将 30 设为黑色，20 设为红色，并对 20 执行左旋。

通过以上步骤，可以逐步构建出一棵符合红黑树性质的树。每次插入后，都需要检查并调整以确保树的性质保持不变。

查询过程

红黑树是一种自平衡的二叉查找树，它保证了在最坏的情况下，任何查找、插入或删除操作的时间复杂度都是 O(log n)。下面概述了红黑树的查询过程：

1. 从根节点开始：

   • 查询开始于树的根节点。

2. 比较键值：

   • 将要查找的键值与当前节点的键值进行比较。
     • 如果两者相等，则找到了所查找的键值，查询结束。
     • 如果查找的键值小于当前节点的键值，则继续在当前节点的左子树中查找。
     • 如果查找的键值大于当前节点的键值，则继续在当前节点的右子树中查找。

3. 递归搜索：

   • 根据上述比较结果，选择相应的子树，并在该子树中重复步骤2的操作。

4. 到达叶子节点：

   • 如果一直到达叶子节点（即当前节点为空），且没有找到目标键值，则说明该键值不在树中，查询失败。

5. 返回结果：

   • 如果在树中找到了目标键值，返回相应的节点或值。
   • 如果没有找到目标键值，返回一个指示未找到的标志或特定值。

红黑树的查询过程与普通二叉查找树非常相似，但是由于红黑树的自平衡特性，可以确保树的高度始终保持在较低水平，从而提高了最坏情况下的性能。注意，在实际的查询过程中，不会涉及到红黑树的颜色属性，因为查询仅关心键值的比较，而不涉及树的平衡性质。