【C++】红黑树 --- map/set 底层

这里写自定义目录标题

一、红黑树概念及性质1. 概念2. 性质 二、红黑树的实现1. 红黑树节点的定义2. 红黑树的定义3. 红黑树的插入4. 红黑树的验证5. 红黑树相关的接口方法 三、用红黑树封装 map/set1. 红黑树的迭代器2. 改造红黑树3. 用红黑树封装 set4. 用红黑树封装 map

一、红黑树概念及性质

1. 概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black.

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的；如下图：

2. 性质

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

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

很简单，假设每条路径的黑色节点数量为 h 个，那么 h <= 红黑树中任意一条路径长度 <= 2h；那么最短路径就是 h，即这条路径上全是黑色节点；最长路径是 2h，这条路径上全是一黑一红间隔；

如下图，左边是这颗红黑树的最短路径，高度为 2；最右边是这颗红黑树的最长路径，高度为 4；这颗红黑树中符合上面的所有规则，所以最短路径没有超过最长路径的两倍，所以这颗树符合红黑树的规则。

二、红黑树的实现

1. 红黑树节点的定义

想要实现一颗红黑树 ，首先我们得有树的节点，而树的节点中我们需要存：该节点的父节点、该节点的右孩子、该节点的左孩子、树节点的颜色以及数据类型；代码如下：

enum COLOUR{RED,BLACK};template<class K, class V>struct RBTreeNode{RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;COLOUR _col;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_col(RED){}};

这里在节点的定义中，要将节点的默认颜色给成红色，这个后面再介绍。

2. 红黑树的定义

红黑树的定义如下：

template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;private:Node* _root = nullptr;};

3. 红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索树的规则插入新节点

代码如下：

bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}// 找到插入位置Node* cur = _root, *parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;}

检测新节点插入后，红黑树的性质是否造到破坏

上面节点的定义中，我们默认给节点的颜色是红色，为什么是红色呢？因为如果给黑色，那么影响的将会是整棵树，新增黑节点的路径多了一个黑色节点，那么其它全部路径都会受到影响，影响面太大。

如果是新增的是红色节点，那么就要看其父节点，如果父节点是黑色的，那么就结束了；如果父节点也是红色的，那么违反了有连续的红色节点，只需要处理一下当前路径即可；所以默认新增节点为红色。

因为新节点的默认颜色是红色，因此：如果其父节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的父节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

此时关键是要看叔叔(uncle)节点，因为当新增节点的父节点 parent 为红色的时候，如果 uncle 也是红色的，那么就让 parent 和 uncle 一起变黑色即可；如果 uncle 是黑色或者不存在，再另外讨论。

约定:cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红

如下图：

此时 a、b、c、d、e 都为符合规则的红黑子树，如果当 a、b、c、d、e 都为空，那么 cur 就是新增节点；否则，cur 就是从下面的子树中更新上来的。

上图中的情况，只需要变色处理即可，如下图所示，将 g 变红，p 和 u 变黑；如果 g 是根节点，最后还要把根节点变黑；如果 g 不是根节点，还要继续往上更新：

代码如下：

while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//     g//   p   u// cif (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1、uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上更新处理cur = grandfather;parent = cur->_parent;}}}

与上面情况相同但是 p 在 g 的右边的时候，如下图所示：

此时的处理情况与上面的处理情况一样，如下图：

代码如下(续上)：

// grandfather->_right == parent//     g//   u   p//         celse{Node* uncle = grandfather->_left;// uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}}

总结：当 uncle 为红色时，解决方案：将 p，u 改为黑，g 改为红，然后把 g 当成 cur，继续向上调整。

情况二: cur 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑

情况2.1，如下图所示，当 p 为 g 的左孩子：

情况2.2，当 p 为 g 的右孩子：

说明：u 的情况有两种：

如果 u 不存在，则 cur 一定是新插入节点，因为如果 cur 不是新插入节点，则 cur 和 p 一定有一个节点的颜色是黑色，就不满足红黑树的性质4：每条路径黑色节点个数相同；如果 u 存在，则其一定是黑色的，那么 cur 节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为 cur 的子树在调整过程中将 cur 节点的颜色由黑色改成了红色。

上面的情况2.1和情况2.2需要旋转处理，因为这两种情况本质上是相同的，所以下面只看情况2.1的旋转过程，情况2.2相反即可：

代码如下：

情况2.1

// 单旋//     g//   p  u// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}

情况2.2

// 单旋//     g//   u   p //         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}

总结，情况二的解决方案：p 为 g 的左孩子，cur 为 p 的左孩子，则进行右单旋转；相反，p 为 g 的右孩子，cur 为 p 的右孩子，则进行左单旋转；p、g变色- -p变黑，g变红。

情况三: cur 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑

情况三与情况二的不同在于：例如下面的情况3.1，cur 是在 p 的右子树，而情况2.1中 cur 是在 p 的左子树：

情况3.2：

此时这种情况相当于AVL树中双旋的情况，cur 到 g 是折线的形式，在红黑树中这种情况确实也是需要进行双旋，下面只画出情况3.1的旋转过程和变色，情况3.2也是类似的；旋转过程是先对 p 进行左单旋，再对 g 进行右单旋：

双旋完成后将 cur 变成黑色，g 变成红色；完成更新，跳出循环。

代码如下(续上)：

情况3.1

// 双旋//      g//   p     u//      celse{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}

情况3.2

// 双旋//     g//   u   p //     celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}

总结：p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 做左单旋转，然后对 g 做右单旋 + 变色；相反，p 为 g 的右孩子，cur 为 p 的左孩子，则针对 p 做右单旋转，然后对 g 做左单旋 + 变色。

完整的插入代码如下：

bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}// 找到插入位置Node* cur = _root, *parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//     g//   p   u// cif (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1、uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上更新处理cur = grandfather;parent = cur->_parent;}else{// 情况2.1// 单旋//     g//   p// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况3.1// 双旋//     g//   p//     celse{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}// grandfather->_right == parent//     g//   u   p//         celse{Node* uncle = grandfather->_left;// uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}// uncle 存在且为黑 或者 uncle 不存在else{// 情况2.2// 单旋//     g//   u   p //         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况3.2// 双旋//     g//   u   p //     celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 最后保证根节点是黑色的_root->_col = BLACK;return true;}

4. 红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质

首先我们验证是否满足二叉搜索树，代码如下：

// 判断中序遍历是否为有序序列void Inorder(){_Inorder(_root);cout << endl;}// 按中序遍历打印树的节点void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}

其次判断其是否满足红黑树的性质：

// 判断是否平衡bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 先统计一条路径的黑色节点，与其它路径的比较int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){refVal++;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}// 检查是否符合红黑树规则bool Check(Node* root, int blacknum, int refVal){if (root == nullptr){if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}

下面我们随机插入一些数验证我们的红黑树是否正常，我们直接插入 1w 个数据，代码如下：

int main(){const int N = 10000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++)v.push_back(rand() + i);RBTree<int, int> t;for (auto e : v)t.Insert(make_pair(e, e));t.Inorder();if (t.IsBalance())cout << "红黑树正常" << endl;elsecout << "红黑树异常" << endl;return 0;}

执行结果如下：

如上图，验证了我们的红黑树是正常的。

5. 红黑树相关的接口方法

下面给出红黑树相关的完整接口代码，包括插入、查找、获取高度、判平衡等；代码如下：

#pragma once#include <iostream>using namespace std;enum COLOUR{RED,BLACK};template<class K, class V>struct RBTreeNode{RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;COLOUR _col;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_col(RED){}};template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}// 找到插入位置Node* cur = _root, *parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//     g//   p   u// cif (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1、uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上更新处理cur = grandfather;parent = cur->_parent;}else{// 情况2.1// 单旋//     g//   p// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况3.1// 双旋//     g//   p//     celse{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}// grandfather->_right == parent//     g//   u   p//         celse{Node* uncle = grandfather->_left;// uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}// uncle 存在且为黑 或者 uncle 不存在else{// 情况2.2// 单旋//     g//   u   p //         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况3.2// 双旋//     g//   u   p //     celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 最后保证根节点是黑色的_root->_col = BLACK;return true;}// 判断中序遍历是否为有序序列void Inorder(){_Inorder(_root);cout << endl;}// 判断是否平衡bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 先统计一条路径的黑色节点，与其它路径的比较int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){refVal++;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}// 获取树的高度int Height(){return _Height(_root);}// 获取树的节点数size_t Size(){return _Size(_root);}// 查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}private:// 获取树的节点个数size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}// 获取树的高度int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}// 检查是否符合红黑树规则bool Check(Node* root, int blacknum, int refVal){if (root == nullptr){if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}// 按中序遍历打印树的节点void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right, * subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;// 如果 parent 是根节点，就直接更新 subR 为根节点，并将 subR 的_parent指向空if (_root == parent){_root = subR;subR->_parent = nullptr;}// 否则，先判断 parent 是 parentParent 的右还是左，再将parentParent的左或者右连接subRelse{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left, * subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* parentParent = parent->_parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}private:Node* _root = nullptr;};

三、用红黑树封装 map/set

1. 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：

begin()与end()

STL明确规定，begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin() 可以放在红黑树中最小节点(即最左侧节点)的位置，end() 放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成 nullptr 呢？答案是行不通的，因为对 end() 位置的迭代器进行 - - 操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将 end() 放在头结点的位置；但是我们为了方便，将 end() 给成 nullptr.

operator++()与operator–()

迭代器最重要的部分就是在 ++ 和 - - 的实现上；先说 ++it 的核心，因为我们是要按照中序的顺序遍历红黑树，所以 ++it 最核心的就是找中序的下一个，此时分为两种情况：1. it 指向的节点，如果右子树不为空，下一个就是右子树的最左节点；2. it 指向的节点，如果右子树为空，表明 it 中的节点所在的子树访问完了，往上找孩子是父亲左的那个祖先；

再简单说一下 - -，- - 的实现与 ++ 反过来，分两种情况：1. 左不为空，下一个就是左子树的最右节点；2. 左为空，往上找孩子是父亲右的那个祖先；

如下为红黑树迭代器的代码示例：

template<class T, class Ref, class Ptr>struct __TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}// 前置--Self& operator--(){if (_node->_left){Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}// 前置++Self& operator++(){if (_node->_right){Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* cur = _node, * parent = cur->_parent;while (parent && cur != parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}};

2. 改造红黑树

因为关联式容器中存储的是 <key, value> 的键值对，因此，K 为 key 的类型，T：如果是 map，则为 pair<K, V>；如果是 set，则为 K；所以在封装 map/set 的时候，第二个模板参数就决定了树的节点是什么类型，如下图转换过程：

那么第二个问题来了，我们在插入节点的时候，可以使用 T 作为参数类型，如下图；

那么在比较的时候应该怎么比较呢？我们怎么知道这个 T 是 map 的 pair 类型 还是 set 的 K 类型 呢？所以这里需要在 map/set 中提供一个仿函数，来获取各自的数据类型，再进行比较；如下图转换过程：

那么 set 只有一个类型为什么还要写一个仿函数提取 key 呢？因为 set 的底层也是红黑树，为了保证红黑树的底层兼容 map，set 只能也写仿函数了，因为 map 是要仿函数获取类型的。

经过改造的红黑树的参考代码如下：

enum COLOUR{RED,BLACK};template<class T>struct RBTreeNode{RBTreeNode<T>* _parent;RBTreeNode<T>* _left;RBTreeNode<T>* _right;COLOUR _col;T _data;RBTreeNode(const T& data):_parent(nullptr),_left(nullptr),_right(nullptr),_data(data),_col(RED){}};template<class T, class Ref, class Ptr>struct __TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}// 前置--Self& operator--(){if (_node->_left){Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}// 前置++Self& operator++(){if (_node->_right){Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* cur = _node, * parent = cur->_parent;while (parent && cur != parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}};template<class K, class T, class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T, T&, T*> iterator;typedef __TreeIterator<T, const T&, const T*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end() {return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}pair<Node*, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}// 找到插入位置Node* cur = _root, *parent = nullptr;KeyOfT kot;while (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else{return make_pair(cur, false);}}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) > kot(cur->_data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//     g//   p   u// cif (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1、uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上更新处理cur = grandfather;parent = cur->_parent;}else{// 情况2.1// 单旋//     g//   p// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况3.1// 双旋//     g//   p//     celse{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}// grandfather->_right == parent//     g//   u   p//         celse{Node* uncle = grandfather->_left;// uncle 存在且为红// 不需要旋转if (uncle && uncle->_col == RED){// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}// uncle 存在且为黑 或者 uncle 不存在else{// 情况2.2// 单旋//     g//   u   p //         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// 情况3.2// 双旋//     g//   u   p //     celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 最后保证根节点是黑色的_root->_col = BLACK;return make_pair(newnode, true);}private:// 左单旋void RotateL(Node* parent){Node* subR = parent->_right, * subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;// 如果 parent 是根节点，就直接更新 subR 为根节点，并将 subR 的_parent指向空if (_root == parent){_root = subR;subR->_parent = nullptr;}// 否则，先判断 parent 是 parentParent 的右还是左，再将parentParent的左或者右连接subRelse{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left, * subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* parentParent = parent->_parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}private:Node* _root = nullptr;};

3. 用红黑树封装 set

以下我们用红黑树封装出一个简单的 set，代码如下：

#pragma once#include "RBTree.h"template<class K>class my_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _s.begin();}iterator end() const{return _s.end();}pair<iterator, bool> insert(const K& key){return _s.Insert(key);}private:RBTree<K, K, SetKeyOfT> _s;};

我们验证一下 my_set，结果如下：

4. 用红黑树封装 map

最后我们用红黑树封装出一个简单的 map，代码如下：

#pragma once#include "RBTree.h"template<class K, class V>class my_map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:// 对类模板取内嵌类型，加 typename 告诉编译器这里是类型typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const {return _t.begin();}const_iterator end() const {return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

对 my_map 进行验证，结果如下：