目录
一、STL源码中的红黑树
二、红黑树如何封装set和map？
三、改造红黑树节点定义以及红黑树
四、仿函数解决插入函数中比较大小的问题
五、封装代码
一、STL源码中的红黑树
在《C++红黑树》的代码中，我们模拟实现的红黑树节点是有两个模板参数Key和Value的，而红黑树类中也是传入两个模板参数Key和Value的，分别对应红黑树节点的Key和Value。
但实际上STL源码中的红黑树节点仅有一个模板参数Value，红黑树类中有两个模板参数Key和Value，仅仅将红黑树类的模板参数Value传给红黑树节点。
以下是STL中红黑树的部分源码：
二、红黑树如何封装set和map？
既然红黑树节点中只有一个参数Value，那么set和map容器又是如何通过红黑树实现的呢？
set容器只需要一个模板参数Key，将Key分别传给红黑树的Key和Value，则红黑树节点中保存的就是Key。
map容器需要两个模板参数Key和T，将Key和T组成一个键值对Value，再将Key和Value分别传给红黑树，则红黑树节点中保存的就是键值对Value，即pair<Key, T>。
以下是STL中set容器部分源码：
以下是STL中map容器部分源码：
综上所述，我们就可以使用红黑树简单封装一下set和map容器：
此处的红黑树是STL源码中的红黑树，和之前模拟实现的红黑树不同
封装简单示例图：
代码：
//RBTreeNode
template<class T>
struct RBTreeNode {T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;//构造函数RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};
//RBTree
template<class K,class T>
class RBTree {typedef RBTreeNode<T> Node;
private:Node* _root = nullptr;
};
//set
namespace bit {template<class K>class set {private:RBTree::RBTree<K, K> _t;};
}
//map
namespace bit {template<class K, class V>class map {private:RBTree::RBTree<K, pair<K, V>> _t;};
}三、改造红黑树节点定义以及红黑树
//RBTreeNode
template<class T>
struct RBTreeNode {T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;//构造函数RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}
};
//RBTree
template<class K,class T>
class RBTree {typedef RBTreeNode<T> Node;
private:Node* _root = nullptr;
};四、仿函数解决插入函数中比较大小的问题
在红黑树的插入函数中，会先按照二叉搜索树的规则进行插入，那么就要比较新插入节点和其他节点的Key值大小。对于set容器，其节点存放的就是Key直接比较即可，但是对于map容器，其节点存放的是键值对。尽管键值对支持直接比较，但是其比较方法与我们预期的比较方法不同。
问题在于，set容器和map容器都是使用统一模型的红黑树，在比较节点值的时候，我们并不知道其中存放的是Key还是键值对<Key, Value>，也就是我们并不知道当前红黑树实现的是set容器还是map容器。
如图所示代码为在《C++红黑树》模拟实现的红黑树插入函数。对于set容器，节点中存放的是_data，而_data就是Key，可以直接比较；对于map容器，节点中存放的是_data，_data是一个键值对，而我们需要比较的是_data.first。
思考：对于上述问题，能不能使用函数重载解决？
答案：不可以，因为红黑树节点中保存的是类型都是_data，不满足函数重载条件
解决方法：在set容器和map容器类中分别添加一个仿函数，用于返回节点中的_data的Key值。同时需要在红黑树类的模板参数中增加仿函数类
//set
namespace bit
{template<class K>class set {private://内部类：提供仿函数，用于返回红黑树中_data的key值（_data可能是key或者pair<key,value>）//对于set而言，_data就是keystruct SetKeyOFT{const K& operator()(const K& key){return key;}};private:RBTree::RBTree<K, K, SetKeyOFT> _t;};
}//map
namespace bit
{template<class K,class V>class map {private://内部类：提供仿函数，用于返回红黑树中_data的key值（_data可能是key或者pair<key,value>）//对于set而言，_data就是keyclass MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};private:RBTree::RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}五、封装代码
RBTree.h
#pragma once
#include <iostream>
using namespace std;
//模拟STL源码中的红黑树版本//枚举颜色enum Colour {RED,BLACK};//红黑树节点template<class T>struct RBTreeNode {T _data;//键值对RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;//构造函数RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};//红黑树迭代器类（此处的迭代器实现和list容器迭代器实现基本一样）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){}//*Ref operator*(){return _node->_data;}//->Ptr operator->(){return &_node->_data;}//!=bool operator!=(const Self& s){return _node != s._node;}//++Self& operator++(){if (_node->_right){//下一个，右树的最左节点Node* leftMin = _node->_right;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{//下一个，孩子等于父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}};//红黑树类template<class K, class T, class KeyOfT>class RBTree {typedef RBTreeNode<T> Node;public://迭代器实现typedef __RBTreeIterator<T, T&, T*> Iterator;//迭代器begin，应当返回最左节点（中序遍历视角下）Iterator Begin(){Node* leftMin = _root;while (leftMin&&leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}//迭代器endIterator End(){return Iterator(nullptr);}//插入bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}//使用仿函数KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);cur->_col = RED; // 新增节点给红色if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// parent的颜色是黑色也结束while (parent && parent->_col == RED){// 关键看叔叔Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{if (cur == parent->_left){// g // p u// c RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g // p u// c RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;//需要旋转节点的左孩子Node* subLR = subL->_right;//需要旋转节点的左孩子的右孩子//Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_left = subLR;//将旋转节点左孩子的右孩子给成旋转节点的左孩子if (subLR)subLR->_parent = parent;//父亲节点也需要修改（但前提是旋转节点左孩子的右孩子存在，所以有个判断条件）subL->_right = parent;//将旋转节点给成旋转节点左孩子的右孩子Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_parent = subL;//父亲节点也需要修改if (parent == _root)//parent是根节点{_root = subL;_root->_parent = nullptr;}else//parent是子树{if (ppNode->_left == parent)//旋转节点是左节点，则将subL作为左节点ppNode->_left = subL;else//旋转节点是右节点，则将subL作为右节点ppNode->_right = subL;subL->_parent = ppNode;}//parent->_bf = subL->_bf = 0;//最后旋转后的节点平衡因子为0}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;//旋转节点的右孩子Node* subRL = subR->_left;//旋转节点右孩子的左孩子//Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_right = subRL;//将旋转节点右孩子的左孩子给成旋转节点的右孩子if (subRL)subRL->_parent = parent;//父亲节点也需要修改（但前提是旋转节点右孩子的左孩子存在，所以有个判断条件）subR->_left = parent;//将旋转节点给成旋转节点的右孩子的左孩子Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_parent = subR;//父亲节点也需要修改if (parent == _root)//旋转节点是根节点{_root = subR;_root->_parent = nullptr;}else//旋转节点是子树{if (ppNode->_left == parent)//旋转节点是左节点，则将subR作为左节点ppNode->_left = subR;else//旋转节点是右节点，则将subR作为右节点ppNode->_right = subR;subR->_parent = ppNode;}//subR->_bf = parent->_bf = 0;//最后旋转后的节点平衡因子为0}//判断平衡bool IsBalance(){if (_root->_col == RED){return false;}int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://检查平衡bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
Myset.h
#pragma once
#include <iostream>
#include "RBTree.h"
namespace bit
{template<class K>class set {private://内部类：提供仿函数，用于返回红黑树中_data的key值（_data可能是key或者pair<key,value>）//对于set而言，_data就是keystruct SetKeyOFT{const K& operator()(const K& key){return key;}};public://插入函数bool insert(const K& key){return _t.Insert(key);}//迭代器实现typedef typename RBTree<K, const K, SetKeyOFT>::Iterator iterator;//beginiterator begin(){return _t.Begin();}//enditerator end(){return _t.End();}private:RBTree<K, const K, SetKeyOFT> _t;};
}Mymap.h
#pragma once
#include <iostream>
#include "RBTree.h"
namespace bit
{template<class K,class V>class map {private://内部类：提供仿函数，用于返回红黑树中_data的key值（_data可能是key或者pair<key,value>）//对于set而言，_data就是keystruct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://插入函数bool insert(const pair<K, V>& kv){return _t.Insert(kv);}//迭代器实现typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Iterator iterator;//beginiterator begin(){return _t.Begin();}//enditerator end(){return _t.End();}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}test.cpp
#include <iostream>
#include <string>
#include "Myset.h"
#include "Mymap.h"
using namespace std;
//void test()
//{
// bit::set<int> s;
// s.insert(1);
// s.insert(2);
// s.insert(3);
// s.insert(1);
// s.insert(2);
// s.insert(3);
// s.insert(8);
// s.insert(100);
// s.insert(0);
//
// bit::set<int>::iterator it = s.begin();
// while (it != s.end())
// {
// std::cout << *it << " ";
// ++it;
// }
// std::cout << std::endl;
//
//}
void test2()
{bit::map<string, int> m;m.insert({ "榴莲",1 });m.insert({ "辣条",2 });m.insert({ "西瓜",3 });bit::map<string, int>::iterator it2 = m.begin();while (it2 != m.end()){std::cout << it2->first << ":" << it2->second << std::endl;++it2;}std::cout << std::endl;
}
int main()
{//test();test2();return 0;
}
