一、红黑树概念及性质
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
// c
if (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
// c
else
{
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
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
情况2.2
// 单旋
// g
// u p
// c
if (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
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
情况3.2
// 双旋
// g
// u p
// c
else
{
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
// c
if (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
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.1
// 双旋
// g
// p
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// grandfather->_right == parent
// g
// u p
// c
else
{
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
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.2
// 双旋
// g
// u p
// c
else
{
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;
else
cout << "红黑树异常" << 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
// c
if (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
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.1
// 双旋
// g
// p
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// grandfather->_right == parent
// g
// u p
// c
else
{
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
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.2
// 双旋
// g
// u p
// c
else
{
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的左或者右连接subR
else
{
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
// c
if (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
// c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.1
// 双旋
// g
// p
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// grandfather->_right == parent
// g
// u p
// c
else
{
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
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// 情况3.2
// 双旋
// g
// u p
// c
else
{
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的左或者右连接subR
else
{
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 进行验证，结果如下：文章来源：https://www.toymoban.com/news/detail-756082.html
文章来源地址https://www.toymoban.com/news/detail-756082.html
到了这里，关于【C++】红黑树 --- map/set 底层的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构 - C++] 红黑树RBTree](https://imgs.yssmx.com/Uploads/2024/01/817663-1.png)
