红黑树

1. 红黑树概述

1.1 红黑树的定义

红黑树是一种自平衡的二叉搜索树，，由Rudolf Bayer于1972年发明。它能确保在最坏情况下基本动态集合操作（如插入、删除、查找）的时间复杂度为 O(log⁡n)，这里的 n 是树中节点的数量。红黑树在它的每个节点上增加了一个存储位来表示节点的颜色（红色或黑色），通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。这使得树的高度始终保持在对数级别，从而保证了操作的高效性。

image-20250301180009516

红黑树的高效性使其在很多领域都有广泛的应用，以下是一些常见场景：

  1. 标准库的实现

    • C++ STL 的map/multimap/set/multiset容器
    • Java TreeMap 和 TreeSet

    由于红黑树的自平衡特性，这些容器在插入、删除和查找操作上都能保证 O(logn)的时间复杂度，为开发者提供了高效的数据存储和检索方式。

  2. Linux 内核进程调度，是在完全公平调度器（Completely Fair Scheduler，CFS）里，红黑树被用于管理进程。

    CFS 是 Linux 内核 2.6.23 版本之后引入的一种进程调度算法，其核心目标是实现进程调度的公平性。它基于时间片分配的思想，为每个进程分配一定的虚拟运行时间（vruntime）。在调度时，优先选择 vruntime 最小的进程来运行，以此确保每个进程都能公平地获得 CPU 时间。

    • CFS 使用红黑树来组织处于可运行状态的进程。
    • 进程插入：
      • 当一个进程变为可运行状态（例如，从睡眠状态被唤醒）时，内核会把该进程插入到红黑树中。
      • 插入操作依据进程的 vruntime 来确定其在红黑树中的位置，以保证红黑树的有序性。
      • 插入操作时间复杂度为 O(logn)，所以能高效地完成插入操作。
    • 进程的删除：
      • 当一个进程进入睡眠状态或者退出运行时，内核会将该进程从红黑树中删除。
      • 删除操作同样能在 O(logn)的时间复杂度内完成，确保了操作的高效性。
    • 进程的选择：
      • CFS 调度器在选择下一个要运行的进程时，会直接选取红黑树中最左边的节点（即 vruntime 最小的进程）。
      • 因为红黑树是按照 vruntime 有序排列的，所以找到最左边的节点非常高效，时间复杂度为 O(logn)。

  3. 数据库系统

    • 索引实现：红黑树可以作为索引的数据结构。
    • 事务日志管理：数据库的事务日志需要高效地记录和检索事务操作信息。

    通过红黑树的快速查找特性，能在 O(logn)时间内定位到相关记录，大大提高查询效率。

  4. 文件系统

    • 目录项查找：红黑树可以用于存储目录项的索引，根据文件名进行快速查找。
    • 磁盘块分配管理：红黑树可以用于管理磁盘块的分配信息，根据磁盘块的编号或地址进行快速查找和分配，确保磁盘空间的高效利用。

  5. 图形处理

    • 碰撞检测
      • 红黑树可以用于管理物体的边界框信息，根据物体的位置或坐标进行排序。
      • 在进行碰撞检测时，可以快速查找可能发生碰撞的物体对，减少不必要的比较操作，提高碰撞检测的效率。
    • 场景管理：
      • 在图形渲染场景中，红黑树可以用于存储大量的图形对象，如模型、纹理等。
      • 红黑树可以根据对象的深度、优先级等进行排序，方便快速查找和渲染，提高图形渲染的效率。

1.2 红黑树的性质

  1. 颜色属性：红黑树的节点是有颜色的，不是黑色，就是红色。

  2. 根节点属性：root 根节点必须为黑色

  3. 空节点属性：所有的 nullptr 空节点都被视为黑色

    • 在红黑树中这些 nullptr节点不存储数据，仅用于维护红黑树性质

  4. 红色节点限制：不能出现连续的红色节点

    • 如果父亲节点是红色，左右孩子节点一定是黑色的
    • 如果孩子节点中有红色节点，父亲节点一定是黑色的

  5. 路径相等：对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

    • 这个数目被称为该节点的黑高（Black - Height）。
    image-20250301193201449

2. 红黑树的操作

2.1 插入

红黑树的插入操作可以分为以下几个步骤：

  1. 按照二叉搜索树的方式插入新节点：将新节点插入到红黑树中合适的位置，就像普通的二叉搜索树插入操作一样。
    • 如果红黑树为空，新插入的节点就是根节点，颜色为黑色。
    • 如果红黑树非空，新插入的节点初始颜色为红色。
  2. 调整颜色和旋转：由于新节点的插入可能会破坏红黑树的性质，需要通过调整节点颜色和进行旋转操作（左旋和右旋）来恢复红黑树的性质。具体的调整情况取决于新节点的父节点、祖父节点以及叔叔节点的颜色。

关于红黑树的颜色调整和旋转可以分为以下几种情况：

  1. 只需要调整颜色的场景：新插入的节点的父亲和叔叔都是红色节点

    在下面这棵红黑树中插入新的节点，值为 9

    image-20250301232218135

    • 按照BST树的规则将数据添加到红黑树中，并且值为9的节点颜色为红色，和它的父节点颜色一致，不满足规则，需要将父亲和叔叔修改为黑色节点，祖父修改为红色节点。

    • 现在以12为根节点的这棵子树的父节点是红色，出现了两个连续的红色节点，继续调整颜色，将值为12的节点的父亲和叔叔节点修改为黑色，它的祖父节点修改为红色，此时祖父节点为树的根节点，树的根节点不能是红色，再次将祖父节点修改为黑色。

  2. 左旋场景1：父亲是红色，叔叔是黑色，孩子、父亲、爷爷不在同一侧。

    在下面这棵红黑树中插入新的节点，值为 45。

    • 新插入的节点45的父亲节点和叔叔节点都是红色，祖父节点是黑色，需要调整颜色：父亲和叔叔变成黑色，祖父节点变成红色。

    • 孩子节点60和父亲节点40都是红色，叔叔节点90和祖父节点80是黑色，孩子、父亲、爷爷不在同一侧，以 40 为根节点左旋。

  3. 右旋场景1：父亲是红色，叔叔是黑色，孩子、父亲、爷爷在同一侧。

    在上图中，对红黑树进行了左旋之后可以看到，出现了连续的红色节点，并且父亲节点60和叔叔节点90颜色不一致（不是全部为红色），所以需要继续进行调整。

    • 孩子40、父亲60、祖父80节点在同一侧，将父亲节点变成黑色，将祖父节点变成红色。

    • 以节点80（祖父节点）为根节点右旋，红黑树的调整结束。

    调整完毕之后每个分支的黑色节点数量为2个。

  4. 右旋场景2：父亲是红色，叔叔是黑色，孩子、父亲、爷爷在不同一侧。

    在下面这棵红黑树中插入新的节点，值为 80。

    • 新插入的节点80的父亲节点和叔叔节点全部为红色，调整节点颜色，父亲、叔叔节点变为黑色，祖父节点变为红色。

    • 出现了连续的红色节点60和90，需要以90为根节点向右旋转。

  5. 左旋场景2：父亲是红色，叔叔是黑色，孩子、父亲、爷爷在同一侧。

    在上图中，通过右旋得到了两个连续的红色节点60和90

    • 颜色调整：父节点变为黑色，祖父节点变为红色。

    • 以节点39为根节点向左旋转，得到一棵满足条件的红黑树，每个分支上都有两个黑色节点。

2.2 删除

红黑树的删除操作比插入操作更为复杂，同样可以分为以下几个步骤：

2.2.1 找到要删除的节点

按照二叉搜索树的删除逻辑找到要删除的节点。如果该节点有两个子节点，则用其前驱节点（左子树中的最大节点）或者后继节点（右子树中的最小节点）替换该节点，然后删除这个前驱或者后继节点，这样就将问题转化为删除最多只有一个子节点的情况。

BST树的节点删除剖析

双黑节点

在红黑树的删除操作中，当要删除的节点是黑色节点，并且在删除它之后，为了保持红黑树的性质 5（从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点），就会引入“双黑”的概念。

“双黑节点”并不是指节点具有两种颜色，而是一种虚拟的概念。当删除一个黑色节点后，我们可以将这个额外减少的黑色标记到该节点的父节点或者该节点原来所在的位置上，这个带有额外黑色标记的节点就被称为双黑节点。可以把“双黑节点”理解为该节点实际上有两个黑色的权重，目的是提醒我们这个位置实际上需要额外的一个黑色节点来恢复平衡。

如下图是一颗合法的红黑树，当删除了黑色节点6之后就会破坏红黑树的性质 5，此时节点11所在位置就成为了双黑节点：

image-20250307105032292

2.2.2 节点的删除和调整

当做了上面的处理之后，我们要删除的节点最多只有一个子节点，假设要删除的目标节点为 targetNode，其唯一的子节点（若存在）为 childNode，targetNode 的父节点为 parentNode，targetNode 的兄弟节点为 siblingNode。根据 targetNode 和 childNode 的颜色，可分为以下几种情况：

  • 情况 1：被删除的目标节点 targetNode 是红色

    由于红色节点的删除不会影响红黑树的任何性质（不会破坏黑高，也不会出现连续的红色节点），所以直接删除 targetNode 即可，不需要进行额外的调整。

  • 情况 2：被删除的目标节点 targetNode 是黑色，且其子节点 childNode 是红色

    删除 targetNode 后，将 childNode 染成黑色，这样就可以保持红黑树的性质，也不需要进行额外的旋转操作。

  • 情况 3：被删除的目标节点 targetNode 是黑色，且其子节点 childNode 也是黑色（或 childNode 为空节点）。

    这种情况比较复杂，需要进行额外的调整操作，以恢复红黑树的性质。根据兄弟节点 siblingNode 及其子节点的颜色，又可细分为以下几种情况：

被删除节点位于左侧

由于以下情况比较复杂，所以图例中只提供出操作过程中涉及到的相关部分节点，因此这棵子树可能不满足红黑树的性质5（局部不满足性质5，不代表整棵树不满足红黑树的性质5）。

  • 情况 3-1：兄弟节点 siblingNode 是黑色，且 siblingNode 的右子节点是红色

    在这种情况下， parentNode 节点的颜色可能是黑色可能是红色，但是父节点的颜色对处理的过程不会造成任何影响，如下图（待删除的节点为8，父节点为16，兄弟节点为20）：

    1. 将 siblingNode 染成 parentNode 的颜色，parentNode 染成黑色，siblingNode 的右红色子节点染成黑色（如果右子节点的红色，不需要考虑左侧子节点的颜色）。
    2. 对 parentNode 进行左旋，红黑树的性质得到恢复，调整结束。

    父节点为黑色

    将节点20设置为父节点的颜色 - 黑色，父节点16设置为黑色，20的右子节点设置为黑色。

    在进行节点删除操作之前，当前子树左侧路径上有2个黑色节点，右侧路径上有3个黑色节点。对于整棵红黑树（未画出）而言，这一状态是满足性质5的。因此，在调整之后，如果仍然能够保持子树中黑色节点的数量为左侧2个、右侧3个，那么我们就可以认为这棵红黑树已经调整完毕。

    父节点为红色

    节点20设置为父节点的颜色 - 红色，父节点16设置为黑色，20的右子节点设置为黑色。

    调整前、调整后这棵子树左侧路径黑节点都是1个，右侧路径黑色节点都是2个，调整结束。

  • 情况 3-2：兄弟节点 siblingNode 是黑色，siblingNode 的左子节点是红色，右子节点是黑色

    1. 将 siblingNode 的红色子节点染成黑色，siblingNode 染成红色

    2. 对 siblingNode 进行右旋，问题转化为情况 3-1 继续处理。

    • 待删除的节点为8，父节点为16，兄弟节点为20
    • 将兄弟的左侧红色子节点18染成黑色，兄弟节点20染成红色。
    • 基于兄弟节点进行右旋，待删除节点8的兄弟节点更新为18，得到了和场景3-1相同的子树结构。
    • 按照场景3-1的流程继续对红黑树进行调整。

  • 情况 3-3：兄弟节点 siblingNode 是黑色，且 siblingNode 的两个子节点都是黑色。

    1. 将兄弟节点siblingNode涂成红色。

      image-20250307181701308

    2. 基于父节点parentNode继续向上进行调整，对应的场景可能是场景3-1、场景3-2、场景3-3或者场景3-4，根据实际情况进行调整即可。

      此时的根节点是16，需要观察节点16的兄弟的颜色：

      • 兄弟节点是红色，按照情况3-4处理
      • 兄弟节点是黑色，需要观察兄弟节点的孩子的颜色
        • 右孩子是红色节点，按照情况3-1处理
        • 右孩子是黑色节点，左孩子是红色节点，按照情况3-2处理
        • 左孩子和右孩子都是黑色节点，按照情况3-3处理

  • 情况 3-4：兄弟节点 siblingNode 是红色

    1. 将 siblingNode 染成黑色，parentNode 染成红色。

    2. 对 parentNode 进行左旋，siblingNode 更新为黑色的节点10

    3. 基于兄弟节点 siblingNode 继续进行调整，有三种情况：

      • siblingNode的右孩子是红色，按照情况3-1处理。
      • siblingNode的右孩子是黑色，左孩子是红色，按照情况3-2处理
      • siblingNode的左右两个孩子都是黑色，按照情况3-3处理。

被删除节点位于右侧

被删除的节点位于右侧和位于左侧在处理的时候思路大致相同，不同的是旋转的时候方向是相反的。

  • 情况 3-1：兄弟节点 siblingNode 是黑色，且 siblingNode 的左子节点是红色

    1. 将 siblingNode 染成 parentNode 的颜色，parentNode 染成黑色，siblingNode 的左红色子节点染成黑色（如果左子节点的红色，不需要考虑右侧子节点的颜色）。
    2. 对 parentNode 进行右旋，红黑树的性质得到恢复，调整结束。

    父节点为黑色

    • 待删除的节点为36，父节点为30，兄弟节点为25
    • 兄弟节点为25染成父节点的黑色，节点25的左孩子20染成黑色，父节点30染成黑色
    • 基于父节点30进行右旋，红黑树调整完毕。

    父节点为红色

    • 待删除的节点为36，父节点为30，兄弟节点为25
    • 兄弟节点为25染成父节点的红色，节点25的左孩子20染成黑色，父节点30染成黑色
    • 基于父节点30进行右旋，红黑树调整完毕。

  • 情况 3-2：兄弟节点 siblingNode 是黑色，siblingNode 的左子节点是黑色，右子节点是红色

    1. 将 siblingNode 的红色子节点染成黑色，siblingNode 染成红色

    2. 对 siblingNode 进行左旋，问题转化为情况 3-1 继续处理。

    • 待删除的节点为36，父节点为30，兄弟节点为25
    • 将兄弟的右侧红色子节点26染成黑色，兄弟节点25染成红色。
    • 基于兄弟节点进行左旋，待删除节点36的兄弟节点更新为26，得到了和场景3-1相同的子树结构。
    • 按照场景3-1的流程继续对红黑树进行调整。

  • 情况 3-3：兄弟节点 siblingNode 是黑色，且 siblingNode 的两个子节点都是黑色。

    这种情况的处理和待删除节点在左侧的处理步骤完全相同，此处不再进行过多赘述。

  • 情况 3-4：兄弟节点 siblingNode 是红色

    1. 将 siblingNode 染成黑色，parentNode 染成红色。

    2. 对 parentNode 进行右旋，siblingNode 更新为黑色的节点26

    3. 基于兄弟节点 siblingNode 继续进行调整，有三种情况：

      • siblingNode的左孩子是红色，按照情况3-1处理。
      • siblingNode的左孩子是黑色，右孩子是红色，按照情况3-2处理
      • siblingNode的左右两个孩子都是黑色，按照情况3-3处理。

3. 红黑树的实现

3.1 类的定义

首先需要定义出红黑树的树节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 定义红黑树节点
struct RBNode
{
    // 定义枚举, 节点颜色
    enum class Color {RED, BLACK};
    int data;
    Color color;
    RBNode* left;
    RBNode* right;
    RBNode* parent;
    RBNode(int value) : data(value), color(Color::RED), 
                        left(nullptr), right(nullptr), parent(nullptr) {}
    // 判断节点是红色还是黑色
    inline bool isRed() { return color == Color::RED; }
    inline bool isBlack() { return color == Color::BLACK; }
    // 设置节点颜色
    inline void setRed() { color = Color::RED; }
    inline void setBlack() { color = Color::BLACK; }
};

然后再将红黑树对应的类定义出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 定义红黑树类
class RBTree
{
public:
    RBTree();
    ~RBTree();
    void buildTree();
    // 节点的插入
    void insert(int data);
    // 节点的删除
    void remove(int data);
    // 中序遍历
    void inorder();
    // 节点的颜色
    inline bool isBlack(RBNode* node)
    {
        return node == nullptr || node->isBlack();
    }
    inline bool isRed(RBNode* node)
    {
        return node != nullptr && node->isRed();
    }

private:
    enum class FindOP { Insert, Remove };
    // 左旋
    void leftRotate(RBNode* root);
    // 右旋
    void rightRotate(RBNode* root);
    // 插入修复
    void insertFixup(RBNode* root);
    // 删除修复
    void removeFixup(RBNode* root);
    // 节点迁移 n2->n1
    void transplant(RBNode* n1, RBNode* n2);
    // 根据数据找插入/删除位置
    RBNode* findPos(int data, FindOP op = FindOP::Insert);
    // 遍历
    void inorder(RBNode* root);
    void clear(RBNode* root);
private:
    RBNode* m_root; // 红黑树根节点
};

3.2 构造和析构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
RBTree::RBTree() : m_root(nullptr)
{
}

RBTree::~RBTree()
{
    clear(m_root);
}

void RBTree::clear(RBNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    clear(root->left);
    clear(root->right);
    cout << "释放节点: " << root->data << endl;
    delete root;
}

3.3 左旋和右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void RBTree::leftRotate(RBNode* root)
{
    RBNode* rightChild = root->right;
    root->right = rightChild->left;
    if (rightChild->left != nullptr)
    {
        rightChild->left->parent = root;
    }

    rightChild->parent = root->parent;
    if (root->parent == nullptr)
    {
        m_root = rightChild;
    }
    else if (root == root->parent->left)
    {
        root->parent->left = rightChild;
    }
    else
    {
        root->parent->right = rightChild;
    }
    rightChild->left = root;
    root->parent = rightChild;
}

void RBTree::rightRotate(RBNode* root)
{
    RBNode* leftChild = root->left;
    root->left = leftChild->right;
    if (leftChild->right != nullptr)
    {
        leftChild->right->parent = root;
    }
    leftChild->parent = root->parent;
    if (root->parent == nullptr)
    {
        m_root = leftChild;
    }
    else if (root == root->parent->right)
    {
        root->parent->right = leftChild;
    }
    else
    {
        root->parent->left = leftChild;
    }
    leftChild->right = root;
    root->parent = leftChild;
}

3.4 插入和插入调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
RBNode* RBTree::findPos(int data, FindOP op)
{
    RBNode* parent = nullptr;
    RBNode* curNode = m_root;
    while (curNode != nullptr)
    {
        parent = curNode; 
        if (data < curNode->data)
        {
            curNode = curNode->left;  
        }
        else if (data > curNode->data)
        {
            curNode = curNode->right; 
        }
        else
        {
            return op == FindOP::Insert ? nullptr : curNode;
        }
    }

    return op == FindOP::Insert ? parent : nullptr;
}

void RBTree::insert(int data)
{
    RBNode* node = new RBNode(data);
    RBNode* parent = findPos(data);    
    node->parent = parent;
    if (parent == nullptr)
    {
        m_root = node;
    }
    else if (data < parent->data)
    {
        parent->left = node;
    }
    else
    {
        parent->right = node;
    }
    insertFixup(node);
}

void RBTree::insertFixup(RBNode* root)
{
    while (root->parent != nullptr && root->parent->isRed())
    {
        RBNode* grandpa = root->parent->parent;
        RBNode* uncle = nullptr;
        if (root->parent == grandpa->left)
        {
            uncle = grandpa->right;
        }
        else
        {
            uncle = grandpa->left;
        }

        if (uncle != nullptr && uncle->isRed())
        {
            root->parent->setBlack();
            uncle->setBlack();
            grandpa->setRed();
            root = grandpa; 
        }
        else
        {
            if (root->parent == grandpa->left && root == root->parent->right)
            {
                root = root->parent;
                leftRotate(root);
            }
            else if (root->parent == grandpa->right && root == root->parent->left)
            {
                root = root->parent;
                rightRotate(root);
            }

            root->parent->setBlack();
            grandpa->setRed();
            if (root->parent == grandpa->left)
            {
                rightRotate(grandpa);
            }
            else
            {
                leftRotate(grandpa);
            }
        }
    }
    m_root->setBlack();
}

3.5 删除和删除调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
void RBTree::transplant(RBNode* n1, RBNode* n2)
{
    if (n1->parent == nullptr)
    {
        m_root = n2;
    }
    else if (n1 == n1->parent->left)
    {
        n1->parent->left = n2;
    }
    else
    {
        n1->parent->right = n2;
    }
    if (n2 != nullptr)
    {
        n2->parent = n1->parent;
    }
}

void RBTree::remove(int data)
{
    if (m_root == nullptr)
    {
        return;
    }
    RBNode* curNode = findPos(data, FindOP::Remove);
    if (curNode == nullptr)
    {
        cout << "没有找到要删除的节点..." << endl;
        return;
    }

    if (curNode->left != nullptr && curNode->right != nullptr)
    {
        RBNode* preNode = curNode->left;
        while (preNode->right != nullptr)
        {
            preNode = preNode->right;
        }
        curNode->data = preNode->data;
        curNode = preNode; 
    }
    RBNode* child = curNode->left; 
    if (child == nullptr)
    {
        child = curNode->right;
    }
    if (child != nullptr)
    {
        transplant(curNode, child);
        RBNode::Color color = curNode->color;
        delete curNode;
        if (color == RBNode::Color::BLACK)
        {
            removeFixup(child); 
        }
    }
    else
    {
        if (curNode->parent == nullptr)
        {
            delete curNode;
            m_root = nullptr;
            return;
        }
        else
        {
            if (curNode->isBlack())
            {
                removeFixup(curNode);
            }
            transplant(curNode, nullptr);
            delete curNode;
        }
    }
}

void RBTree::removeFixup(RBNode* node)
{
    while (node != m_root && node->isBlack()) 
    {
        if (node == node->parent->left) 
        {
            RBNode* sibling = node->parent->right;
            if (isRed(sibling)) 
            {
                sibling->setBlack();
                node->parent->setRed();
                leftRotate(node->parent);
                sibling = node->parent->right;
            }
            if(isBlack(sibling->left) && isBlack(sibling->right))
            {
                sibling->setRed();
                node = node->parent;
            }
            else
            {
                if (isBlack(sibling->right))
                {
                    sibling->left->setBlack();
                    sibling->setRed();
                    rightRotate(sibling);
                    sibling = node->parent->right;
                }
                sibling->color = node->parent->color;
                node->parent->setBlack();
                sibling->right->setBlack();
                leftRotate(node->parent);
                break;
            }
        }
        else 
        {
            RBNode* sibling = node->parent->left;
            if (isRed(sibling)) 
            {
                sibling->setBlack();
                node->parent->setRed();
                rightRotate(node->parent);
                sibling = node->parent->left;
            }
            if (isBlack(sibling->right) && isBlack(sibling->left)) 
            {
                sibling->setRed();
                node = node->parent;
            }
            else 
            {
                if (isBlack(sibling->left)) 
                {
                    sibling->right->setBlack();
                    sibling->setRed();
                    leftRotate(sibling);
                    sibling = node->parent->left;
                }

                sibling->color = node->parent->color;
                node->parent->setBlack();
                sibling->left->setBlack();
                rightRotate(node->parent);
                break;
            }
        }
    }
    node->setBlack();
}

3.6 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void RBTree::inorder()
{
    inorder(m_root);
}

void RBTree::inorder(RBNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main()
{
    RBTree tree;
    vector<int> data = { 10,5,15,3,7,12,18,1,4,6,8,11,13,16,19,2,9,14,17,20 };
    for (auto it : data)
    {
        tree.insert(it);
    }

    cout << "中序遍历红黑树: ";
    tree.inorder();
    cout << endl;

    cout << "删除红黑树的若干个节点" << endl;
    tree.remove(1);
    tree.remove(2);
    tree.remove(3);
    tree.remove(4);
    tree.remove(5);
    tree.remove(6);
    tree.remove(7);
    tree.remove(8);
    tree.remove(9);
    tree.remove(11);
    tree.remove(12);
    tree.remove(13);
    tree.remove(14);
    tree.remove(15);

    cout << "中序遍历红黑树: ";
    tree.inorder();
    cout << endl;

    return 0;
}

4. 红黑树和AVL树对比

红黑树和AVL树都是自平衡的二叉搜索树，它们在不同场景下各有优劣，以下从多个方面对它们进行详细对比：

4.1 平衡标准

  • 红黑树
    • 是一种弱平衡的二叉搜索树，它通过节点颜色（红色或黑色）来维护平衡。主要遵循以下规则：每个节点要么是红色，要么是黑色；根节点是黑色；每个叶子节点（NIL节点，空节点）是黑色；如果一个节点是红色的，则它的两个子节点都是黑色的；对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
    • 这些规则保证了从根到叶子的最长路径不会超过最短路径的两倍，从而保证树的大致平衡。
  • AVL树
    • 是严格平衡的二叉搜索树，它的平衡标准是每个节点的左右子树的高度差（平衡因子）的绝对值不超过1，即平衡因子只能是 -1、0 或 1。一旦插入或删除节点导致某个节点的平衡因子超出这个范围，就需要通过旋转操作来恢复平衡。

4.2 插入和删除操作

  • 红黑树
    • 插入和删除操作时，主要通过颜色调整和少量的旋转操作来恢复树的平衡。由于红黑树的平衡标准相对宽松，因此在插入和删除节点时，需要进行的调整操作相对较少，尤其是在需要大量插入和删除数据的场景下，红黑树的性能表现较好。
  • AVL树
    • 插入和删除操作后，为了满足严格的平衡条件，可能需要进行多次旋转操作来恢复平衡。在频繁插入和删除节点的场景中，AVL树可能需要更多的旋转操作，导致性能有所下降。

4.3 查找操作

  • 红黑树
    • 由于红黑树只是大致平衡，树的高度可能会比AVL树略高一些，因此在查找操作上，平均时间复杂度虽然也是 O(logn)，但实际的查找效率可能会比AVL树稍低。
  • AVL树
    • 由于其严格的平衡条件，树的高度始终保持在接近最小的状态，查找操作的效率相对较高。在需要频繁进行查找操作的场景中，AVL树比红黑树更具优势。

4.4 实现复杂度

  • 红黑树
    • 实现相对复杂，因为需要维护节点的颜色信息，并且在插入和删除操作时需要考虑颜色的变化以及不同的颜色组合情况，代码实现和逻辑处理较为繁琐。
  • AVL树
    • 实现相对简单，主要关注节点的平衡因子和旋转操作。平衡因子的计算和旋转操作的逻辑相对清晰，代码实现相对容易理解。

4.5 应用场景

  • 红黑树
    • 广泛应用于需要频繁进行插入和删除操作的场景，如 Java 的 TreeMap、TreeSet，C++ STL 中的 map 和 set 等。在这些场景中，红黑树的弱平衡特性可以减少调整操作的开销，提高整体性能。
  • AVL树
    • 更适合于对查找性能要求较高，而插入和删除操作相对较少的场景，例如数据库的索引系统等。在这些场景中，AVL树的严格平衡可以保证快速的查找操作。