【数据结构】C++实现红黑树

【数据结构】C++实现红黑树

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？

红黑树确保从根到叶子的最长可能路径不会超过最短可能路径的两倍，是因为它的性质3和性质4的组合导致的。让我解释一下为什么这些性质可以实现这个目标：

1. 性质3：如果一个节点是红色的，则它的两个孩子结点是黑色的。

   这个性质确保了没有两个相邻的红色节点，因为如果有相邻的红色节点，那么它们的父节点必须是黑色的，这会违反性质2。

2. 性质4：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

   这个性质确保了从根到叶子的各个路径上的黑色节点数目是相等的。这意味着树中最短路径上的黑色节点数目将限制了整个树的最长路径上的黑色节点数目。

现在让我们考虑一下为什么最长路径不会超过最短路径的两倍：

• 假设最短路径上的黑色节点数目为k。这是因为性质4，从根到叶子的任何路径上都有k个黑色节点。
• 最长路径上的黑色节点数目不可能超过2k。这是因为性质3，如果最长路径上有相邻的红色节点，那么它们的父节点必须是黑色的，这会导致两个黑色节点被跳过，从而使最短路径上的黑色节点数目不等于k。

所以，红黑树的性质3和性质4保证了最长路径上的黑色节点数目最多是最短路径上的黑色节点数目的两倍，从而确保了从根到叶子的最长可能路径不会超过最短可能路径的两倍。这也是红黑树保持平衡性的关键特性之一，确保了树的性能在各种操作中保持较为一致。

红黑树的实现

红黑树结点的定义

我们这里直接实现KV模型的红黑树，为了方便后序的旋转操作，将红黑树的结点定义为三叉链结构，除此之外还新加入了一个成员变量，使用枚举用于表示结点的颜色。

// 红黑树结点颜色
enum Colour {
    RED,
    BLACK,
};

template<class K, class V>
struct RBTreeNode {
    //使用三叉链
    RBTreeNode<K, V> *_left;
    RBTreeNode<K, V> *_right;
    RBTreeNode<K, V> *_parent;
    pair<K, V> _kv;
    Colour _col;//结点颜色
    // 在单参数构造函数中使用 explicit 关键字是一种好的编程习惯，可以提高代码的可读性和健壮性。
    // 加上 explicit 关键字，以避免出现不必要的隐式类型转换。如果没有加上 explicit 关键字，那么可以使用该构造函数创建一个 RBTreeNode 对象时，会发生隐式类型转换，将一个 pair 类型的对象转换为 RBTreeNode 对象，这可能导致程序行为出现意外的结果。
    explicit RBTreeNode(const pair<K, V> &kv)
        : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思考：在结点的定义中，为什么要将结点的默认颜色给成红色的？

当我们向红黑树插入结点时，若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。

若我们插入红黑树的结点是红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整；但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。

总结一下：

• 插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。
• 插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整。

权衡利弊后，我们在构造结点进行插入时，默认将结点的颜色设置为红色。

红黑树的插入

红黑树插入结点的逻辑分为三步：

1. 按二叉搜索树的插入方法，找到待插入位置。
2. 将待插入结点插入到树中。
3. 若插入结点的父结点是红色的，则需要对红黑树进行调整。

其中前两步与二叉搜索树插入结点时的逻辑相同，红黑树的关键在于第三步对红黑树的调整。

红黑树在插入结点后是如何调整的？

实际上，在插入结点后并不是一定会对红黑树进行调整，若插入结点的父结点是黑色的，那么我们就不用对红黑树进行调整，因为本次结点的插入并没有破坏红黑树的五点性质。

只有当插入结点的父结点是红色时才需要对红黑树进行调整，因为我们默认插入的结点就是红色的，如果插入结点的父结点也是红色的，那么此时就出现了连续的红色结点，因此需要对红黑树进行调整。

因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。

红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。

情况一

插入结点的叔叔存在，且叔叔的颜色是红色。此时，cur为红，p为红，u为红，g为黑

此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。

但调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。

但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进而进行不同的调整操作。

因此，情况一的抽象图表示如下：

注意： 叔叔存在且为红时，cur结点是parent的左孩子还是右孩子，调整方法都是一样的。

情况二

插入结点的叔叔存在，且叔叔的颜色是黑色。

这种情况一定是在情况一继续往上调整的过程中出现的，即这种情况下的cur结点一定不是新插入的结点，而是上一次情况一调整过程中的祖父结点，如果u结点存在，则其一定是黑色的，那么cur结点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整过程中将cur结点的颜色由黑色改成红色。

需要注意：

1. 从根结点一直走到空位置就算一条路径，而不是从根结点走到左右结点均为空的叶子结点时才算一条路径。
2. 情况二和情况三均需要进行旋转处理，旋转处理后无需继续往上进行调整，所以说情况二一定是由情况一往上调整的过程中出现的。

单旋处理

出现叔叔存在且为黑时，单纯使用变色已经无法处理了，这时我们需要进行旋转处理。若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则我们需要先进行单旋操作，从g结点进行右单旋，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。

图表示如下：

说明一下： 当直线关系为，parent是grandfather的右孩子，cur是parent的右孩子时，就需要先进行左单旋操作，再进行颜色调整。

双旋转处理

若祖孙三代的关系是折线（cur、parent、grandfather这三个结点为一条折线），则我们需要先进行左右双旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根是黑色的，因此无需继续往上进行处理。

旋转操作是先将p左单旋，在将g右单旋

说明一下： 当折线关系为，parent是grandfather的右孩子，cur是parent的左孩子时，就需要先进行右左双旋操作，再进行颜色调整

情况三

插入结点的叔叔不存在。

在这种情况下的cur结点一定是新插入的结点，而不可能是由情况一变化而来的，因为叔叔不存在说明在parent的下面不可能再挂黑色结点了，如下图：

如果插入前parent下面再挂黑色结点，就会导致图中两条路径黑色结点的数目不相同，而parent是红色的，因此parent下面自然也不能挂红色结点，所以说这种情况下的cur结点一定是新插入的结点。

单旋处理

和情况二一样，若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则我们需要先进行单旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。

图表示如下：

说明一下： 当直线关系为，parent是grandfather的右孩子，cur是parent的右孩子时，就需要先进行左单旋操作，再进行颜色调整。

双旋处理

若祖孙三代的关系是折线（cur、parent、grandfather这三个结点为一条折线），则我们需要先进行双旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根是黑色的，因此无需继续往上进行处理。

图表示如下：

说明一下： 当折线关系为，parent是grandfather的右孩子，cur是parent的左孩子时，就需要先进行右左双旋操作，再进行颜色调整。

我们发现情况三的处理是和情况二相同的，所以只需要处理情况二即可。

代码

bool Insert(const pair<K, V> &kv) {
    //创建根结点
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = BLACK;//根结点为黑色
        return true;
    }

    Node *parent = nullptr;
    Node *cur = _root;
    //寻找结点插入位置
    while (cur) {
        if (kv.first > cur->_kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (kv.first < cur->_kv.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 相等则不插入
            return false;
        }
    }
    // cur走到了合适的位置
    cur = new Node(kv);
    // 选择插入到parent的左边还是右边
    if (kv.first < parent->_kv.first) {
        parent->_left = cur;
    } else {
        parent->_right = cur;
    }
    // cur链接parent
    cur->_parent = parent;
    // parent存在且parent的节点为红色的(意味着，循环往上调整到parent不存在或者parent为黑就不用调整了)
    // 红黑树性质:红色结点的孩子必须是黑色的
    while (parent && parent->_col == RED) {
        Node *grandfather = parent->_parent;
        // 如果爷爷的左边是父亲，那么爷爷的右边就是叔叔
        if (grandfather->_left == parent) {
            Node *uncle = grandfather->_right;
            // 情况1：u存在且为红，变色处理，并继续往上处理
            if (uncle && uncle->_col == RED) {
                // 调整parent变黑，uncle变黑，grandfather变红
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;

                // 继续往上调整,此时的grandfather作为新插入结点,继续判断他的父亲是否是红色结点
                // 重置parent，先将grandfather位置看成新增结点cur
                cur = grandfather;
                parent = cur->_parent;
            } else {// 情况2+3  u不存在/u存在且为黑，旋转+变色
                //插入结点是父亲的左孩子
                if (cur == parent->_left) {
                    //     g
                    //   p   u
                    // c
                    // g p c成为一条直线,并且cur在parent的左边
                    // 需要右旋+变色,右旋后parent成为根，需要变黑，grandfather变为parent的右孩子，需要变红
                    RotateRight(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    //     g
                    //   p   u
                    //     c
                    // 当cur为parent的右边时，需要左旋+右旋+变色
                    RotateLeft(parent);
                    RotateRight(grandfather);// 右旋cur成为新的根,变为黑色，grandfather变为cur孩子，变为红色
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {//(grandfather->_right == parent)  如果爷爷的右边是父亲，那么爷爷的左边就是叔叔
            //    g
            //  u   p
            //        c
            Node *uncle = grandfather->_left;
            // 情况1：u存在且为红，变色处理，并继续往上处理
            if (uncle && uncle->_col == RED) {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;

                // 继续往上调整
                cur = grandfather;
                parent = cur->_parent;
            } else// 情况2+3：u不存在/u存在且为黑，旋转+变色
            {
                //    g
                //  u   p
                //        c
                if (cur == parent->_right) {
                    RotateLeft(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    //     g
                    //  u     p
                    //     c
                    RotateRight(parent);
                    RotateLeft(grandfather);
                    //parent的位置没变不需要变色
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    // 最后的根变为黑节点
    _root->_col = BLACK;
    return true;
}

// 左单旋
void RotateLeft(Node *parent) {
    Node *subR = parent->_right;// 要旋转的parent的右子树
    Node *subRL = subR->_left;  // 子树的左子树

    // 旋转链接
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;

    // 需要记录要旋转的树还有没有父亲
    Node *ppnode = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

    // 如果ppnode为nullptr，说明parent一开始为根，旋转后subR为根
    if (ppnode == nullptr) {
        // 更新根节点
        _root = subR;
        _root->_parent = nullptr;
    } else {
        if (ppnode->_left == parent) {
            ppnode->_left = subR;
        } else {
            ppnode->_right = subR;
        }
        subR->_parent = ppnode;
    }
}

// 右单旋
void RotateRight(Node *parent) {
    Node *subL = parent->_left;
    Node *subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;

    Node *ppnode = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (ppnode == nullptr) {
        _root = subL;
        _root->_parent = nullptr;
    } else {
        if (ppnode->_left == parent) {
            ppnode->_left = subL;
        } else {
            ppnode->_right = subL;
        }
        subL->_parent = ppnode;
    }
}
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

红黑树的验证

红黑树也是一种特殊的二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断该二叉树是否满足二叉搜索树的性质。

代码如下：

void InOrder(Node *root) {
    if (root == nullptr) {
        return;
    }

    InOrder(root->_left);
    cout << root->_kv.first << " ";
    InOrder(root->_right);
}

void InOrder() {
    InOrder(this->_root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

但中序有序只能证明是二叉搜索树，要证明二叉树是红黑树还需验证该二叉树是否满足红黑树的性质。

bool IsBalance() {
    if (_root && _root->_col == RED) {
        cout << "根节点颜色是红色" << endl;
        return false;
    }

    int benchmark = 0;// 基准值，任选一条做，用于比较每条节点黑色节点相同，如果不相同则说明不平衡
    Node *cur = this->_root;
    while (cur) {
        if (cur->_col == BLACK)
            benchmark++;
        cur = cur->_left;
    }
    // 连续红色节点
    return _check(this->_root, 0, benchmark);
}

bool _check(Node *root, int BlackNum, int benchmark) {
    // 检查不能存在连续的红色节点
    // benchmark基准值
    if (root == nullptr) {
        if (benchmark != BlackNum) {
            cout << "某条路径黑色节点的数量不相等" << endl;
            return false;
        }

        return true;
    }

    if (root->_col == BLACK) {
        BlackNum++;
    }

    if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
        cout << "存在连续的红色节点" << endl;
        return false;
    }

    return _check(root->_left, BlackNum, benchmark) && _check(root->_right, BlackNum, benchmark);
}
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

红黑树的查找

红黑树的查找函数与二叉搜索树的查找方式一模一样

Node *find(const K &key) {
    Node *cur = this->_root;
    while (cur) {
        if (key > cur->_kv.first) {
            cur = cur->_right;
        } else if (key < cur->_kv.first) {
            cur = cur->_left;
        } else {
            return cur;
        }
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。