关于红黑树的模拟实现，大家不清楚的先去看看博主的博客再来看这篇文章，因为set和map的封装底层都是利用用的红黑树。所以这里不会过多介绍红黑树的相关内容，而更多的是去为了契合STL中的红黑树去进行改造，让封装的set和map能够去复用我们的这份代码
DS进阶：AVL树和红黑树-CSDN博客
在模拟实现之前，我们肯定要尝试去看看源码是如何实现的！我们会发现其实map和set的底层都是用的红黑树去封装的
但是你可能会有这样的疑惑，map是kv模型，set是k模型，那难道stl底层封装了两颗红黑树么？？其实并不是的，创建stl的大佬们为了增加代码的复用性，想方设法地想让map和set同时复用一颗红黑树。而解决方法就是通过控制模版参数来区分map和set。
既然底层是套的红黑树的壳子，我们就要来研究库里面的红黑树究竟通过了什么方法来让map和set都能够复用这份代码。
一、STL中的红黑树
1.1 利用模版参数控制和区分map和set
我们先来看看stl中的红黑树的模版参数，然后进行分析
接下来我们来看看第三个模版参数的作用究竟是什么
总结：
第1个模版参数是为了帮助我们拿到Key的类型，因为find、erase的接口都是Key类型比较方便
第2个模版参数决定了红黑树节点中存的是key还是pair，以此来区分map和set
第3个模版参数是通过仿函数决定了是拿什么去进行比较，对set来说就是拿key，对pair来说就是拿他的first。
第4个模版参数是具体的比较逻辑，比如说我们传的是指针，但是我们并不想通过指针比而是通过指针解引用的类型比，就可以通过传这个仿函数去控制其比较的行为。
第5个是stl实现的一个堆内存管理器，是为了提高从堆区申请内存的效率，基本上所有的stl容器都会涉及到这个，所以目前暂时不需要太在意！
1.2 stl中的红黑树结构
在该图中，设置了一个哨兵节点，哨兵节点的左指向最小节点5，最大节点的右指向哨兵节点header， 为什么要这样设计呢？？
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位
置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最
后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：
但是这样虽然方便我们找到第一个节点和最后一个节点，但是每一次都要最最左端和最右端的节点进行和头节点之间的联系，其实比较麻烦，所以下面我们直接改造成不带哨兵节点的红黑树。去模拟实现迭代器。
1.3 改造并模拟实现红黑树的迭代器
但是最最关键的逻辑就是，实现++和--这样迭代器才能跑的起来，下面我们来进行分析
迭代器的封装
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)
{}
// 1、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造
// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
// 支持普通迭代器构造const迭代器的构造函数
_RBTreeIterator(const _RBTreeIterator<T, T&, T*>& it) //隐私类型转化
:_node(it._node)
{}
Ref operator*()
{
return _node->_data; //解引用拿到对应的东西 map拿到pair set拿到key
}
Ptr operator->() //返回对应的指针类型
{
return &operator*();
}
bool operator!=(const Self& s)
{
return _node != s._node;//判断两个迭代器是否相同
}
bool operator==(const Self& s)
{
return _node == s._node;//判断两个迭代器是否相同
}
Self& operator++() //实现迭代器的++
{
if (_node->_right)
{
//如有右不为空，那么就去找到 右子树的最左路节点
Node* subright = _node->_right;
while (subright->_left) subright = subright->_left; //找到最左路节点
_node = subright;
}
else
{
//右为空，沿着到根的路径，找孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
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 && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};1.4 红黑树实现的全部代码
enum Colour
{
RED,
BLACK,
};
template<class T> //T表示传的是K还是pair
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
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)
{}
// 1、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造
// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
// 支持普通迭代器构造const迭代器的构造函数
_RBTreeIterator(const _RBTreeIterator<T, T&, T*>& it) //隐私类型转化
:_node(it._node)
{}
Ref operator*()
{
return _node->_data; //解引用拿到对应的东西 map拿到pair set拿到key
}
Ptr operator->() //返回对应的指针类型
{
return &operator*();
}
bool operator!=(const Self& s)
{
return _node != s._node;//判断两个迭代器是否相同
}
bool operator==(const Self& s)
{
return _node == s._node;//判断两个迭代器是否相同
}
Self& operator++() //实现迭代器的++
{
if (_node->_right)
{
//如有右不为空，那么就去找到 右子树的最左路节点
Node* subright = _node->_right;
while (subright->_left) subright = subright->_left; //找到最左路节点
_node = subright;
}
else
{
//右为空，沿着到根的路径，找孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
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 && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
//K是为了单独拿到key的类型 因为find erase 的接口都是key 而第二个模版参数T决定是这边传的是pair还是key
template<class K, class T,class KeyOfT> //KeyofT 取出来比较的是k 还是pair中的k
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef _RBTreeIterator<T, T&, T*> iterator;
typedef _RBTreeIterator<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);
}
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
Node* Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;//控制 是在pair中拿key还是直接拿key
while (cur)
{
if (kot(cur->_data) < key) cur = cur->_right; //我比你小，你往右找
else if (kot(cur->_data) > key) cur = cur->_left; //我比你大，你往左找
else return cur;
}
return nullptr;//说明找不到
}
//先用搜索树的逻辑插入节点，然后再去更新平衡因子。
pair<iterator,bool> Insert(const T& data)
{
//如果为空树，新节点就是根
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
KeyOfT kot;//控制 是在pair中拿key还是直接拿key
//如果不为空树
Node* parent = nullptr;
Node* cur = _root;
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);//相等
}
//此时肯定是对应地接在parent的后面
cur = new Node(data);
Node* newnode = cur;//记住新加入的节点
if (kot(parent->_data)> kot(data)) parent->_left = cur; //比父亲小连左边
else parent->_right = cur; //比父亲大连右边
//别忘了父亲指针
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//情况1，如果u为存在且为红
if (grandfather->_left == parent)//如果p是g的左边，u就在右边
{
Node* uncle = grandfather->_right;
//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else //情况2或者情况3， u为黑或者不存在 旋转+变色
{
if (cur == parent->_left) //情况2 右单旋+p变黑 g变红
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //情况3 右左双旋 c变黑 g变红
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//情况2和情况3都要跳出循环
}
}
else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边 几乎一样，就是旋转的逻辑不同
{
Node* uncle = grandfather->_left;
//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//情况2或者情况3， u为黑或者不存在 旋转+变色
{
if (cur == parent->_right) //情况2 左单旋+p变黑 g变红
{
// g
// p u
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //情况3 左右双旋 c变黑 g变红
{
// g
// p u
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//情况2和情况3都要跳出循环
}
}
}
_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错
return make_pair(iterator(newnode), true);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根节点颜色是红色" << endl;
return false;
}
int benchmark = 0;//找到一条路径作为基准值 然后看看其他路径是否相等
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;
cur = cur->_left;
}
// 连续红色节点
return _Check(_root, 0, benchmark);
}
int Height()
{
return _Height(_root);
}
private:
void _Destroy(Node* root)
{
if (root == nullptr) return;
//后序遍历销毁
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool _Check(Node* root, int blackNum, int 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);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
//旋转代码和AVL树是一样的，只不过不需要搞平衡因子
void RotateL(Node* parent)
{
//旋转前，先记录对应的节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* ppnode = parent->_parent;//子树的前驱节点
//先让b变成30的边
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
//让30变成60的左边
subR->_left = parent;
parent->_parent = subR;
//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
if (ppnode == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
else
{
if (ppnode->_left == parent) ppnode->_left = subR;
else ppnode->_right = subR;
//向上连接
subR->_parent = ppnode;
}
}
void RotateR(Node* parent)
{
//旋转前，先记录对应的节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppnode = parent->_parent;//子树的前驱节点
//先让b变成60的左边
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
//让60变成30的右边
subL->_right = parent;
parent->_parent = subL;
//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
if (ppnode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
else
{
if (ppnode->_left == parent) ppnode->_left = subL;
else ppnode->_right = subL;
//向上连接
subL->_parent = ppnode;
}
}
Node* _root = nullptr;
};
二、set的模拟实现
前面我们已经将架子搭好了，这个时候就可以直接开始用了！！
namespace cyx
{
template<class K>
class set
{
struct SetKeyofT
{
const K& operator()(const K& key) //为了跟map保持一致
{
return key;
}
};
public:
typedef typename RBTree< K,K,SetKeyofT>::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K&key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyofT> _t;
};
注意：
1、在没有实例化的时候 ，编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题
2、对于insert返回值的改造，本质上是为了map去服务的，set只是配合而已。
三、map的模拟实现
3.1 insert的改装
在stl中 insert的返回值是pair<iterator,bool> 一开始我不太能理解为什么要这么设计。后来我明白了其实本质上为了后面重载[ ]的实现做铺垫。我们可以通过返回值去拿到iterator，并对对应节点的value进行直接修改！！
//先用搜索树的逻辑插入节点，然后再去更新平衡因子。
pair<iterator,bool> Insert(const T& data)
{
//如果为空树，新节点就是根
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
KeyOfT kot;//控制 是在pair中拿key还是直接拿key
//如果不为空树
Node* parent = nullptr;
Node* cur = _root;
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);//相等
}
//此时肯定是对应地接在parent的后面
cur = new Node(data);
Node* newnode = cur;//记住新加入的节点
if (kot(parent->_data)> kot(data)) parent->_left = cur; //比父亲小连左边
else parent->_right = cur; //比父亲大连右边
//别忘了父亲指针
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//情况1，如果u为存在且为红
if (grandfather->_left == parent)//如果p是g的左边，u就在右边
{
Node* uncle = grandfather->_right;
//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else //情况2或者情况3， u为黑或者不存在 旋转+变色
{
if (cur == parent->_left) //情况2 右单旋+p变黑 g变红
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //情况3 右左双旋 c变黑 g变红
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//情况2和情况3都要跳出循环
}
}
else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边 几乎一样，就是旋转的逻辑不同
{
Node* uncle = grandfather->_left;
//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else//情况2或者情况3， u为黑或者不存在 旋转+变色
{
if (cur == parent->_right) //情况2 左单旋+p变黑 g变红
{
// g
// p u
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //情况3 左右双旋 c变黑 g变红
{
// g
// p u
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//情况2和情况3都要跳出循环
}
}
}
_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错
return make_pair(iterator(newnode), true);
}3.2 重载[ ]的实现
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造
return ret.first->second;
}通过insert拿到对应位置的迭代器，然后指向其second 这样就可以直接进行修改了。
3.3 模拟实现的代码
namespace cyx
{
template<class K, class V>
class map
{
struct MapKeyofT
{
const K& operator()(const pair<const K, V>& kv) //为了跟map保持一致
{
return kv.first;
}
};
public:
//模版类型的内嵌类型 加typename
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造
return ret.first->second;
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K,V>, MapKeyofT> _t;
};
