点击跳转至文章：【C++】：红黑树深度剖析 — 手撕红黑树！
目录
前言
map 和 set 的底层本质上还是复用，通过对红黑树的改造，再分别套上一层 map 和 set 的 “壳子”，以达到 “一树二用” 的目的。
在改造红黑树的过程中，我大概归纳了以下几个需要重点解决的问题：
(1) 对红黑树节点的改造。关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是 set 则是 K，如果是map，则为pair<K, V>。如何用一个节点结构控制两种类型，使用类模板参数T。
(2) 在插入操作时，如何完成数据的比较。由于我们的节点类型的泛型，如果是 set 则是 K，如果是map，则为pair<K, V>，而pair的比较是由 first 和 second 共同决定的，这显然不符合要求。因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key 数据。
(3) 在红黑树中实现普通迭代器和const迭代器，再套上 “壳子”。
(4) 关于 key 的修改问题。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。这个问题需要单独处理。
(5) 红黑树相关接口的改造。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。
说明：如果大家要自己动手实现封装，可以按照上面五个问题的流程进行实现。但是在本篇文章中由于展示等的原因，无法按照上面的步骤。
一，红黑树的改造
1. 红黑树的主体框架
(1) K 是给find，erase用的，T 是给节点，insert用的；
(2) KeyOfT 是由于下面需要比较，但是比较时不知道T的类型， set是key类型的比较，map是pair类型的比较，要统一变成key的比较。
template <class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //节点
public:
typedef RBTreeIterator<T, T&, T*> Iterator; //普通迭代器
typedef RBTreeIterator<T, const T&, const T*> ConstIterator; //const 迭代器
//其他功能的实现……
private:
Node* _root = nullptr;
};
2. 对红黑树节点结构的改造
//枚举颜色
enum Colour
{
RED,
BLACK
};
//节点类
template <class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//pair<K, V> _kv;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(BLACK)
{}
};
3. 红黑树的迭代器
3.1 迭代器类
//迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
bool operator!=(const Self& s)
{
return s._node != _node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
//从局部的某一个过程考虑
Self& operator++()
{
if (_node->_right)
{
//右不为空，右子树的最左节点就是下一个访问的节点
Node* leftMost = _node->_right;
while (leftMost->_left)
leftMost = leftMost->_left;
_node = leftMost;
}
else
{
//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先
//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点
Node* cur = _node;
Node* parent = cur->_parent;
//循环找祖先
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
迭代器中最复杂的就是 operator++()的实现，它与原先的 vector/list 不同，红黑树的迭代器是要完成二叉树的中序遍历。
为了完成二叉树的中序遍历，我们需要从局部的某一过程考虑，就是假设 it 已经走到了某一节点，要找到下一个访问的节点，分为两种情况：
(1) 当前节点的右子树不为空：
如下图，假设 it 已经到达了13节点，说明此时13的左子树已经访问完了，右子树不为空，下一个要访问的节点就是右子树的最左节点15
(2) 当前节点的右子树为空：
如下图，假设 it 此时到达了15节点，它的右子树为空，下一个访问哪个节点呢？有些人单纯的认为是15的父亲17，其实是错误的。
那假设 it 到达6节点上呢，6的右为空，但是根据中序遍历的顺序，6的父亲1已经访问过了。
其实此时是要找当前节点的祖先，父亲也是祖先之一。
右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先，是哪个祖先呢？沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点。
(a) 假设此时走到了15节点，下一个访问的节点是17，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点；
(b) 假设此时走到了6节点，下一个访问的节点是8，但是此时 cur 是 parent 的右，不满足条件，继续向上查找，cur = parent，parent = parent->_parent，这时 cur 在1，parent 在8，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点
3.2 Begin() 和 End()
//中序遍历，找树的最左节点
Iterator Begin()
{
//Node* cur = _root;
Node* leftMost = _root;
while (leftMost->_left)
leftMost = leftMost->_left;
return Iterator(leftMost);
}
Iterator End()
{
return Iterator(nullptr);
}
ConstIterator Begin()const
{
//Node* cur = _root;
Node* leftMost = _root;
while (leftMost->_left)
leftMost = leftMost->_left;
return ConstIterator(leftMost);
}
ConstIterator End()const
{
return ConstIterator(nullptr);
}
Iterator Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_data > key)
cur = cur->_left;
else if (cur->_data < key)
cur = cur->_right;
else
return Iterator(cur);
}
return End();
}
四，红黑树相关接口的改造
4.1 Find 函数的改造
查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。
Iterator Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_data > key)
cur = cur->_left;
else if (cur->_data < key)
cur = cur->_right;
else
return Iterator(cur);
}
return End();
}
4.2 Insert 函数的改造
map 里的 operator[] 需要依赖 Insert 的返回值
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
return make_pair(Iterator(_root), true);
}
KeyOfT kot;
Node* cur = _root;
Node* parent = nullptr;
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(Iterator(cur), false);
}
cur = new Node(data);
Node* newnode = cur;
//此处省略变色+旋转部分的代码……
五，红黑树改造的完整代码
说明：由于代码太长，影响展示效果，所以插入部分的 变色+旋转 的代码此处省略，和红黑树的基本一模一样，请前往【C++】：红黑树深度剖析 — 手撕红黑树！
RBTree.h
#include <iostream>
#include <assert.h>
using namespace std;
//枚举颜色
enum Colour
{
RED,
BLACK
};
//节点类
template <class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//pair<K, V> _kv;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(BLACK)
{}
};
//迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
bool operator!=(const Self& s)
{
return s._node != _node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
//从局部的某一个过程考虑
Self& operator++()
{
if (_node->_right)
{
//右不为空，右子树的最左节点就是下一个访问的节点
Node* leftMost = _node->_right;
while (leftMost->_left)
leftMost = leftMost->_left;
_node = leftMost;
}
else
{
//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先
//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点
Node* cur = _node;
Node* parent = cur->_parent;
//循环找祖先
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
//K 是给find，erase用的，T 是给节点，插入用的
// KeyOfT 是由于下面需要比较，但是比较时不知道T的类型，
// set是key类型的比较，map是pair类型的比较，要统一变成key的比较
template <class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
//中序遍历，找树的最左节点
Iterator Begin()
{
//Node* cur = _root;
Node* leftMost = _root;
while (leftMost->_left)
leftMost = leftMost->_left;
return Iterator(leftMost);
}
Iterator End()
{
return Iterator(nullptr);
}
ConstIterator Begin()const
{
//Node* cur = _root;
Node* leftMost = _root;
while (leftMost->_left)
leftMost = leftMost->_left;
return ConstIterator(leftMost);
}
ConstIterator End()const
{
return ConstIterator(nullptr);
}
Iterator Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_data > key)
cur = cur->_left;
else if (cur->_data < key)
cur = cur->_right;
else
return Iterator(cur);
}
return End();
}
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
return make_pair(Iterator(_root), true);
}
KeyOfT kot;
Node* cur = _root;
Node* parent = nullptr;
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(Iterator(cur), false);
}
cur = new Node(data);
Node* newnode = cur;
//新增节点，颜色为红色
cur->_col = RED;
//此处省略变色+旋转部分的代码……
private:
Node* _root = nullptr;
};
六，set 的封装实现
set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。
为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可。
MySet.h
#include "RBTree.h"
namespace cc
{
template<class K>
class set
{
// 获取 set 里面的 key
struct SetOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, const K, SetOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetOfT>::ConstIterator 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();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, const K, SetOfT> _t;
};
}
//使用 const 迭代器
void Print(const cc::set<int>& s)
{
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
//测试代码
void Test_set()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
int a[] = { 16,3,7,11,9,26,18,14,15 };
cc::set<int> s;
for (auto e : a)
s.insert(e);
for (auto e : s)
cout << e << " ";
cout << endl;
Print(s);
}
七，map 的封装实现
map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可。
map 中 pair 的 first 不能修改，second 可以修改，在 pair 的第一个参数前加 const 即可。
MyMap.h
#include "RBTree.h"
namespace cc
{
template<class K, class V>
class map
{
//获取 pair 中的 key
struct MapOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapOfT>::ConstIterator 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();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator find(const K& key)
{
return _t.Find(key);
}
//给一个key，返回value的引用
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K,V>, MapOfT> _t;
};
}
//测试代码
void Test_map()
{
cc::map<string, string> dict;
dict.insert({ "left","左边" });
dict.insert({ "right","右边" });
dict.insert({ "insert","插入" });
dict["left"] = "剩余，左边";
cc::map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
//it->first += 'x'; //err
it->second += 'y'; //ok
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
