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

文章目录

- 什么是红黑树？
- - 示意图
  - 红黑树的特点
  - 红黑树的节点结构
  - 插入和删除操作
  - - 旋转操作
    - 重新着色
  - 红黑树的应用
- 树的构造过程
- - 插入新节点
  - - 自平衡调整策略
  - 示例
- 查询过程

什么是红黑树？

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

示意图

红黑树

红黑树的特点

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

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

红黑树的节点结构

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

插入和删除操作

在红黑树中插入或删除节点时，可能会破坏上述的一些性质。因此，在插入或删除操作之后，需要进行一系列的旋转（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) 时间内完成查找、插入和删除操作，同时保持较好的空间效率。因此，它成为许多高效数据结构和算法的基础之一。

树的构造过程

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

插入新节点

插入操作：
- 新节点总是以红色插入。这是因为红色节点意味着其父节点是黑色，这样插入一个红色节点不会立即违反红黑树的性质。
- 新节点插入到正确的位置，就像在普通的二叉查找树中一样。具体来说，新节点插入到叶节点的位置（此时的叶节点是指树中没有子节点的节点）。
修复插入后的不平衡：
- 插入新节点后，可能会导致红黑树的性质被破坏。特别是性质 4（红色节点不能有红色子节点）可能会被破坏。因此，需要进行一系列调整来恢复红黑树的性质。
- 根据插入节点的位置以及其父节点和叔叔节点（如果有）的颜色，采取不同的调整策略。

自平衡调整策略

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

Case 1: 新节点是根节点：
- 如果新插入的节点成为了树的根节点，那么只需简单地将新节点的颜色改为黑色即可。
Case 2: 叔叔节点是红色：
- 如果新节点的叔叔节点是红色，那么可以将新节点的父节点和叔叔节点都设为黑色，而祖父节点设为红色。
- 然后，将祖父节点设为当前节点，继续向上调整。
Case 3: 叔叔节点是黑色（或不存在）：
- 如果新节点的叔叔节点是黑色或不存在（即新节点的父节点是祖父节点的唯一子节点），则需要进行旋转和重新着色操作来恢复红黑树的性质。
这种情况又分为几种子情况：
- Case 3a: 新节点是其父节点的右子节点，且父节点是祖父节点的左子节点：
  - 执行左旋操作，将新节点的父节点变为当前节点，并进行 Case 3b 的检查。
- Case 3b: 新节点是其父节点的左子节点，且父节点是祖父节点的左子节点：
  - 将新节点的父节点设为黑色，祖父节点设为红色。
  - 对祖父节点执行右旋操作。
- Case 3c: 新节点是其父节点的左子节点，且父节点是祖父节点的右子节点：
  - 执行右旋操作，将新节点的父节点变为当前节点，并进行 Case 3d 的检查。
- Case 3d: 新节点是其父节点的右子节点，且父节点是祖父节点的右子节点：
  - 将新节点的父节点设为黑色，祖父节点设为红色。
  - 对祖父节点执行左旋操作。

示例

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

插入节点 10：
- 作为第一个节点，插入后设为黑色。
插入节点 20：
- 作为右子节点插入，设为红色。
- 无需调整，因为只有一个节点，没有违反红黑树性质。
插入节点 30：
- 作为 20 的右子节点插入，设为红色。
- 此时，20 和 30 都是红色，违反性质 4，需要调整。
- 由于 10（祖父节点）是黑色，且 20（父节点）的兄弟节点为空，故采用 Case 3b 的处理方式。
- 将 20 设为黑色，10 设为红色，并对 10 执行右旋。
插入节点 40：
- 作为 30 的右子节点插入，设为红色。
- 此时，30 和 40 都是红色，需要调整。
- 由于 20（祖父节点）是黑色，且 30（父节点）的兄弟节点为空，故采用 Case 3d 的处理方式。
- 将 30 设为黑色，20 设为红色，并对 20 执行左旋。

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

查询过程

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

从根节点开始：
- 查询开始于树的根节点。
比较键值：
- 将要查找的键值与当前节点的键值进行比较。
  - 如果两者相等，则找到了所查找的键值，查询结束。
  - 如果查找的键值小于当前节点的键值，则继续在当前节点的左子树中查找。
  - 如果查找的键值大于当前节点的键值，则继续在当前节点的右子树中查找。
递归搜索：
- 根据上述比较结果，选择相应的子树，并在该子树中重复步骤2的操作。
到达叶子节点：
- 如果一直到达叶子节点（即当前节点为空），且没有找到目标键值，则说明该键值不在树中，查询失败。
返回结果：
- 如果在树中找到了目标键值，返回相应的节点或值。
- 如果没有找到目标键值，返回一个指示未找到的标志或特定值。