前言
本文介绍如何使用红黑树封装出 set 与 map。
一、STL 源码分析
首先，库里面 stl_set 与 stl_map 中：
对于 set 来说，key_type 是 key，value_type 也是 key，也就是说 set 是一个 rbTree<Key, Key> 的模型。
对于 map 来说，key_type 是 key，但是 value_type 是 pair<const key, T>，也就是说 map 是一个 rbTree<Key, pair<Key, Value>> 的模型。
我们再来看一下 rb_tree 的结构：
rb_tree 中，前两个参数是 <key, value>，而 __rb_tree_node<value> 里面的参数传的是 value，因此我们可以总结出，这里 map 的结点中存储的是 pair<key, value>，而 set 的结点中存储的是 key。
那么到底为什么是这样的结构呢？我们将在下面的讲解中逐一解释。
二、红黑树的构建
对于红黑树的构建，之前的文章有详细的讲解。当然，我们之前红黑树是默认存储 pair，现在要同时满足 map 与 set，因此一些地方需要改变，之后总结的时候会给出完整的更改后的代码。
#pragma once
#include <iostream>
using namespace std;
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _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;
Node* parent = nullptr;
while (cur) {
// 小于往左走
if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) // 大于往右走
{
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
cur = new Node(kv);
// 其他结点初始颜色为红色
cur->_col = RED;
// 链接
if (cur->_kv.first < parent->_kv.first) {
parent->_left = cur;
}
else {
parent->_right = cur;
}
cur->_parent = parent;
// 如果我们 parent 是黑色，不用处理，就结束了
// 情况一：cur 为红，parent 为红，grandfather 为黑，uncle 不确定
// 用 while 循环是因为我们要不断的向上调整
while (parent && parent->_col == RED) {
// 首先我们要找到 grandfather
Node* grandfather = parent->_parent;
// 接下来通过 grandfather 找到 uncle
// 如果 parent 是 grandfather->_left
if (parent == grandfather->_left) {
// 说明 uncle 在右边
Node* uncle = grandfather->_right;
// uncle 存在且为红
if (uncle && uncle->_col == RED) {
// 满足上述情况，开始调整颜色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else // uncle 不存在 或 uncle 存在且为黑色
{
// 判断要怎样旋转
// 右单旋
if (cur == parent->_left) {
// g
// p
// c
RotateR(grandfather);
// 调整颜色
parent->_col = BLACK;
grandfather->_col = RED;
}
else // 左右双旋
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
// 调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出
break;
}
}
else // (parent == grandfather->_right)
{
// 如果 parent 是 grandfather->_right
// 说明 uncle 在左边
Node* uncle = grandfather->_left;
// uncle 存在且为红
if (uncle && uncle->_col == RED) {
// 满足上述情况，开始调整颜色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else // uncle 不存在 或 uncle 存在且为黑色
{
// 判断要怎样旋转
// 左单旋
if (cur == parent->_right) {
// g
// p
// c
RotateL(grandfather);
// 调整颜色
parent->_col = BLACK;
grandfather->_col = RED;
}
else // 右左双旋
{
// g
// p
// c
RotateR(parent);
RotateL(grandfather);
// 调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
// 这里保证根为黑色
_root->_col = BLACK;
return true;
}
// 左单旋
void RotateL(Node* parent) {
Node* cur = parent->_right;
Node* curleft = cur->_left;
// 重新链接
parent->_right = curleft;
if (curleft) // 如果 curleft 存在
{
curleft->_parent = parent;
}
cur->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (ppnode == nullptr) {
_root = cur;
cur->_parent = nullptr;
}
else {
if (ppnode->_left == parent) {
ppnode->_left = cur;
}
else {
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
// 右单旋
void RotateR(Node* parent) {
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright) {
curright->_parent = parent;
}
cur->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (ppnode == nullptr) {
cur->_parent = nullptr;
_root = cur;
}
else {
if (ppnode->_left == parent) {
ppnode->_left = cur;
}
else {
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
// 检查是否构建正确
bool CheckColour(Node* root, int blacknum, int benchmark) {
if (root == nullptr) {
if (blacknum != benchmark) return false;
return true;
}
if (root->_col == BLACK) {
++blacknum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
cout << root->_kv.first << "出现连续红色节点" << endl;
return false;
}
return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark);
}
bool IsBalance() {
return IsBalance(_root);
}
bool IsBalance(Node* root) {
if (root == nullptr) return true;
if (root->_col != BLACK) {
return false;
}
// 基准值
int benchmark = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) ++benchmark;
cur = cur->_left;
}
return CheckColour(root, 0, benchmark);
}
private:
Node* _root = nullptr;
};
三、map 与 set 整体框架的搭建与解析
namespace jyf {
template<class k, class v>
class map {
public:
private:
RBTree<k, pair<k, v>> _t;
};
}
namespace jyf {
template<class k>
class set {
public:
private:
RBTree<k, k> _t;
};
}
解析：
首先无论是 map 还是 set 都有两个模板参数，第一个是 key，这个 key 是多存的，它的作用体现在像 find() 这样的函数中。
这里先看第二个参数，传给了 RBTree 的 T，而 T 就是结点中储存的东西，也就是说，你是 set，那么节点中就储存的是 key, 你是 map，那么节点中就储存的是 pair<k, v>。
四、如何取出进行比较？
1. map 与 set 的数据是不同的
我们要明白一个问题，map 与 set 结点中存储的数据是不一样的，因此，如果节点中还存储的是 pair 就不对了，因此，我们结点之中存储的数据应该是 T 类型的数据，如果是 set 就是 key，如果是 map 就是 pair。
2. 取出数据进行比较
1）问题发现
再 insert 函数中，我们之前的红黑树是这样实现的，比如这个找到插入位置的逻辑：
在这张图片里面，我们之前使用 pair，但是现在对于 map 和 set 存储的数据不同，因此需要用 data 来比较。
但是！！！
对于 map 来说，它的 value 是 pair，但是 pair 的比较逻辑能满足我们的需要吗？
可以看到，pair 的比较逻辑是先比 first，first 一样就比 second，但是，我们这里不需要比较 second，key_value 的模型中，只需要比较 key 不同，因此我们需要一种方法，重新定义我们的比较。
怎么重新比较呢？
这里我们通过观察发现，对于 set 来说，它的 data 是 key，可以直接比较，唯一有问题的是 map，因此我们采取的方式是仿函数。
2）仿函数解决
我们可以多定义一个模板参数 KeyOfT，这个模板参数用来定义仿函数，他的作用是取出 Set 或 Map 中的 Key。
对于 Set，它的 data 直接就是 key：
struct SetKeyOfT {
const K& operator()(const K& key) {
return key;
}
};
对于 Map，它的 data 是一个 pair，我们需要 pair 的 first，也就是 key：
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) {
return kv.first;
}
};
至此，我们在取出数据的时候，只要定义出一个对象，重载 operator()，用 () 将 data 包起来，就得到了我们想要的数据。
可以说，这里 set 迁就了 map~
五、封装插入
完成了上述步骤，我们就可以实现封装 map 与 set 的插入了~
对于 set：
bool insert(const K& key) {
return _t.Insert(key);
}
对于 map：
bool insert(const pair<K, V>& kv) {
return _t.Insert(kv);
}
六、迭代器的实现
要实现迭代器，就要先理解迭代器是怎么用的：
下面是一个模板表示迭代器的使用：
it = s.begin();
while (it != s.end()) {
cout << *it << endl;
++it;
}
为了实现这个过程，我们需要重载很多东西。
我们先将框架搭出来：
template<class T>
struct __TreeIterator {
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T> Self;
Node* _node;
__TreeIterator(Node* node) : _node(node) {}
};
1. operator* 与 operator->
RBTree 中：
T& operator*() {
return _node->_data;
}
T* operator->() {
return &(_node->_data);
}
2. operator!=
bool operator!=(const Self& s) {
return _node != s._node;
}
3. operator++
对于树的迭代器，++ 与 -- 就非常重要了，这里有很多坑~
首先对于一个红黑树，他走的是中序的排序，图如下：
那么，it.begin() 是谁呢？
我们说中序是 左 - 根 - 右，也就是说，begin 应该是上图中的 1。
其次，如果我们进行 ++ 操作，迭代器会到那里去呢？
这里分以下几种情况：
- 如果右不为空
那么下一个访问的，将是右树的最左：
- 如果右为空
这里又分两种情况：
cur 是 parent 的右——下一个访问没有被访问的祖先
cur 是 parent 的左——下一个访问 parent
通过观察这两种情况我们可以发现：
也就是说，当右为空的时候，下一个访问的是孩子是父亲的左侧的那一个祖先。
代码总结：
Self& operator++() {
if (_node->_right != nullptr) {
Node* curleft = _node->_right;
while (curleft->_left) {
curleft = curleft->_left;
}
_node = curleft;
}
else {
// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
Node* cur = _node;
Node* parent = _node->_parent;
while (parent) {
if (parent->_left == cur) {
break;
}
else {
cur = parent;
parent = parent->_parent;
}
}
_node = parent;
}
return *this;
}
4. operator--
原理与 ++ 是一样的，只不过原本 ++ 的顺序是中序，即 左 - 根 - 右，- - 是反过来的，因此是 右 - 根 - 左
Self& operator--() {
if (_node->_left) {
Node* subRight = _node->_left;
while (subRight->_right) {
subRight = subRight->_right;
}
_node = subRight;
}
else {
// 孩子是父亲的右的那个节点
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left) {
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
5. 套用普通迭代器
RBTree 中：
经过前面的分析，begin 就是树最左边的结点，end 我们设置为 nullptr。
typedef __TreeIterator<T> iterator;
public:
iterator begin() {
Node* leftMin = _root;
while (leftMin && leftMin->_left) {
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end() {
return iterator(nullptr);
}
set 与 map 中，我们要封装这个方法：
iterator begin() {
return _t.begin();
}
iterator end() {
return _t.end();
}
测试普通迭代器：
jyf::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));
jyf::map<int, int>::iterator mit = m.begin();
while (mit != m.end()) {
mit->first = 1;
mit->second = 2;
cout << mit->first << ":" << mit->second << endl;
++mit;
}
cout << endl;
for (const auto& kv : m) {
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
jyf::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);
auto it = s.begin();
while (it != s.end()) {
// 修改
if (*it % 2 == 0) {
*it += 10;
}
cout << *it << " ";
++it;
}
cout << endl;
for (const auto& e : s) {
cout << e << " ";
}
cout << endl;
七、const 迭代器
我们知道 set 是不允许修改的，map 的 key 不允许修改，而 value 允许修改，再通过观察库中的实现，我们可以发现：
set 实现不能修改的原因是——iterator 迭代器与 const_iterator 都是 const 迭代器。
而 map 实现 key 不能修改，value 可以修改的方法是，在定义 map 的 value 的时候，pair<K, V> 修改为 pair<const K, V>
具体的逻辑我们下一次在进行讲解~
八、查找
查找是通过 key 来查找的，而不是通过 value 来查找的，这也就解释了为什么最开始定义模板参数还要多定义一个 key。
同样，为了取出对应的值，我们也需要仿函数来包上 data。
Node* Find(const K& key) {
Node* cur = _root;
KeyOfT kot;
while (cur) {
if (kot(cur->_data) < key) {
cur = cur->_right;
}
else if (kot(cur->_data) > key) {
cur = cur->_left;
}
else {
return cur;
}
}
return nullptr;
}
总结
红黑树在 STL 的应用 set 与 map 的实现：
set 节点存储 key（rbTree<Key, Key> 模型）。
map 节点存储 pair<const Key, T>（rbTree<Key, pair<Key, Value>> 模型）。
rbTree 的设计：
节点使用 __rb_tree_node，value 的具体含义根据容器类型不同而不同。