一. 整体框架梳理
所谓低层被高层封装就是低层类要作为高层类的成员变量。比如红黑树和迭代器，它们的成员变量都是一个树的节点；而map和set类的成员变量是同一颗红黑树，它们的接口都是通过直接或间接调用红黑树的接口实现的。
二. 节点类
节点类是一个类模板，模板参数ValueType就是节点存储的数据的类型。成员变量包括指向父亲、左右孩子的指针，节点的颜色和节点存储的数据。成员函数就只有一个构造函数，传入一个ValueType的数据来构造一个节点。
// 枚举定义颜色 enum COLOR { RED, BLACK }; // 节点的定义 template<class ValueType> struct RBTreeNode { // 构造函数，颜色默认给为红色 RBTreeNode(const ValueType& data) :_color(RED) ,_data(data) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) {} COLOR _color; ValueType _data; RBTreeNode<ValueType>* _parent; RBTreeNode<ValueType>* _left; RBTreeNode<ValueType>* _right; };
三. 迭代器
1. 迭代器的基本框架
底层封装一个树节点的指针_node，所以构造函数是传入一个树节点的指针让_node指向它。
template<class ValueType, class Ref, class Ptr> class RBTreeItetator { typedef RBTreeNode<ValueType> Node; typedef RBTreeItetator<ValueType, Ref, Ptr> self; public: RBTreeItetator(Node* node) :_node(node) {} private: Node* _node; };
为了实现const迭代器，模板参数除了节点的数据类型外还引入了数据类型的引用（Reference）和数据类型的指针（Pointer）。在迭代器重载解引用和箭头运算符时，不论外面传入的模板参数是什么，都返回Ref和Ptr，可以看到这两个模板参数的引入使得代码更加灵活，这是模板优点的体现，也是泛型编程思想的一个体现。
2. operator++ 和 operator- -
先看自增，我们想要这个迭代器指向下一个节点，根据中序遍历的规则可以得到下面结论：
如果右不为空，中序的下一个就是右子树的最左节点。
如果右为空，表示当前节点所在的子树已经遍历完成，下一个节点为沿着路径往上孩子是它的左的那个祖先。
自减操作的话，就是找前一个节点，和自增的思路相反，不再赘述。它们的实现如下：
// 前置自增操作 self& operator++() { if(_node->_right) { Node* subRL=_node->_right; while(subRL->_left) { subRL=subRL->_left; } _node=subRL; } else { Node* cur=_node; Node* parent=cur->_parent; while(parent && cur == parent->_right) { cur=parent; parent=parent->_parent; } _node=parent; } return *this; } // 后置自减操作 self& operator--() { if(_node->_left) { Node* subLR=_node->_left; while(subLR->_right) { subLR=subLR->_right; } _node=subLR; } else { Node* cur=_node; Node* parent=cur->_parent; while(parent && cur==parent->_left) { cur=parent; parent=parent->_parent; } _node=parent; } return *this; }
3. operator* 和 operator->
解引用就是返回节点中存储的数据的引用，箭头返回节点中存储数据的指针。
Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; }
编译器对箭头操作符的特殊处理
所谓迭代器就是模拟像指针一样的东西，我们希望通过解引用迭代器来直接获取所存储的数据对象本身，我们上面的实现确实做到了；我们也希望通过箭头操作符操作迭代器直接访问存储数据内的成员，在使用箭头操作符时会遇到一些问题。
4. operator== 和 operator!=
比较两个迭代器是否相等，就是比较底层的成员变量即节点对象是否相等。
bool operator==(const self& it) { return _node == it._node; } bool operator!=(const self& it) { return _node != it._node; }
5. 迭代器完整代码
// 迭代器 template<class ValueType, class Ref, class Ptr> class RBTreeItetator { typedef RBTreeNode<ValueType> Node; typedef RBTreeItetator<ValueType, Ref, Ptr> self; public: RBTreeItetator(Node* node) :_node(node) {} self& operator++() { if(_node->_right) { Node* subRL=_node->_right; while(subRL->_left) { subRL=subRL->_left; } _node=subRL; } else { Node* cur=_node; Node* parent=cur->_parent; while(parent && cur == parent->_right) { cur=parent; parent=parent->_parent; } _node=parent; } return *this; } self& operator--() { if(_node->_left) { Node* subLR=_node->_left; while(subLR->_right) { subLR=subLR->_right; } _node=subLR; } else { Node* cur=_node; Node* parent=cur->_parent; while(parent && cur==parent->_left) { cur=parent; parent=parent->_parent; } _node=parent; } return *this; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator==(const self& it) { return _node == it._node; } bool operator!=(const self& it) { return _node != it._node; } private: Node* _node; };
四. 红黑树
1. 红黑树基本框架
成员变量有两个：记录该树节点个数的_size和该树的根_root。
// 树的定义 template<class Key, class ValueType, class KeyOfValue> class RBTree { typedef RBTreeNode<ValueType> Node; public: typedef RBTreeItetator<ValueType, ValueType&, ValueType*> Iterator; typedef RBTreeItetator<ValueType, const ValueType&, const ValueType*> const_Iterator; RBTree() :_size(0) ,_root(nullptr) {} private: size_t _size; Node* _root; };
关于typedef的几点说明
我们对节点类重定义为Node，后面会经常用到为了方便写才重定义的，权限为private因为我们只在类内部使用。另外我们还对迭代器进行了重定义，包括const迭代器和非const迭代器，为了可读性和写起来便捷才重定义，权限为public因为有从外部读取的需要：
如何用一棵红黑树同时实现map和set？
通过对模板参数的巧妙设计可以实现。第一个模板参数Key是节点排序和比较的唯一标识，如果是set的话key就是它自己本身存储的数据，如果是map的话key就是键值对的第一个值。第二个模板参数是map和set存储的数据，map的话是pair键值对，set的话是key。
关于Insert中插入数据的比较方式
此时红黑树的第三个参数就起作用了，它是一个仿函数，map、set各自实现一个并传递给一同颗红黑树。KeyOfValue，顾名思义就是获取ValueType中的Key，即存储数据作为比较的唯一表示。虽然map和set的对KeyOfValue实现不同，但可以完美地匹配它们自己的ValuType，当插入时统一调用这个仿函数来获取Key进行比较，这又是一种泛型编程的体现。
第一个模板参数的作用？
第二个模板参数和第三个模板参数我们都在Insert()中实用到了，传入的第一个模板参数Key有什么用呢？在Find()中就会用到第一个模板参数，我们调用Find()时传入的实参类型就是Key。
2. begin()和end()
红黑树的成员变量是整棵树的根节点，begin()要返回第一个节点的迭代器，根据中序遍历的规则往前找就是去找左子树的最左节点；end()的话就返回一个空的迭代器。最后普通对象返回普通迭代器，const对象返回const迭代器，至于对象是普通的还是const的由在我们在创建map或set对象时它们的属性来决定，因为map和set底层封装红黑树，它们的对象如果是const的话，封装的红黑树也是const的，对应返回const迭代器。
Iterator Begin() { Node* subL=_root; while(subL && subL->_left) { subL=subL->_left; } return Iterator(subL); } const_Iterator Begin() const { Node* subL=_root; while(subL && subL->_left) { subL=subL->_left; } return const_Iterator(subL); } Iterator End() { return Iterator(nullptr); } const_Iterator End() const { return const_Iterator(nullptr); }
3. empty()和size()
红黑树除了根节点外还有一个记录当前节点数的成员变量_size。
empty()的话就是判断_size是否等于0。
size()的话直接返回_size的值就行。
size_t Size() const { return _size; } bool Empty() const { return _size == 0; }
4. Insert 和 Find
这些都是红黑树的基本操作，没有什么太多特别的和与其他类相关联的东西，相关代码放到下面的完整代码里。一定要说的话就是他们的返回值：
- Insert返回一个pair键值对，它的first为节点的迭代器，second为布尔值。如果插入成功first为新插入节点的迭代器，second为true；如果插入失败（要插入的Key已经存在），此时pair的first为那个已经存在的节点的迭代器，second为false。
- Find返回一个迭代器，如果找到了返回该节点的迭代器，找不到返回空迭代器，即end()
5. 红黑树完整代码
// 红黑树的定义 template<class Key, class ValueType, class KeyOfValue> class RBTree { typedef RBTreeNode<ValueType> Node; public: typedef RBTreeItetator<ValueType, ValueType&, ValueType*> Iterator; typedef RBTreeItetator<ValueType, const ValueType&, const ValueType*> const_Iterator; RBTree() :_size(0) ,_root(nullptr) {} Iterator Begin() { Node* subL=_root; while(subL && subL->_left) { subL=subL->_left; } return Iterator(subL); } const_Iterator Begin() const { Node* subL=_root; while(subL && subL->_left) { subL=subL->_left; } return const_Iterator(subL); } Iterator End() { return Iterator(nullptr); } const_Iterator End() const { return const_Iterator(nullptr); } size_t Size() const { return _size; } bool Empty() const { return _size == 0; } // 插入一个节点 pair<Iterator, bool> Insert(const ValueType& data) { // 第一步：按搜索树规则插入一个节点 // 1、空树的话插入节点作为根节点 // 2、不空的话，按搜索树规则找到插入的位置，然后插入 if(!_root) { _root=new Node(data); _root->_color=BLACK; ++_size; return make_pair(Iterator(_root), true); } // 寻找插入的位置 KeyOfValue kov; Node* parent=nullptr; Node* cur=_root; while(cur) { parent=cur; if(kov(cur->_data) == kov(data)) { return make_pair(Iterator(cur), false); } else if(kov(cur->_data) < kov(data)) { cur=cur->_right; } else if(kov(cur->_data) > kov(data)) { cur=cur->_left; } } // 找到后插入 Node* newNode=new Node(data); newNode->_parent=parent; if(kov(parent->_data) > kov(data)) { parent->_left=newNode; } else if(kov(parent->_data) < kov(data)) { parent->_right=newNode; } // 第二步：调整节点的颜色 // 1、如果父亲颜色为黑就不用调整 // 2、如果父亲节点颜色为红，调整方式由叔叔决定 // a、叔叔存在且为红 --> 把叔叔和父亲的颜色调整为黑，爷爷颜色调整为红，然后继续往上调整 // b、叔叔不存在或存在且为黑 --> 看爷爷、父亲、和cur的相对位置来决定用什么旋转，旋转后调整父亲和爷爷的颜色 cur=newNode; while(parent && parent->_color == RED) { // 既然进来了这个循环内部，说明父亲一定是红色，那么一定有爷爷且爷爷颜色为黑 Node* grandfather = parent->_parent; // 确定叔叔的位置 if(grandfather->_left == parent) { Node* uncle=grandfather->_right; if(uncle && uncle->_color == RED)// 叔叔存在且为红 { parent->_color=uncle->_color=BLACK; grandfather->_color=RED; cur=grandfather; parent=cur->_parent; } else // 叔叔不存在或者存在且为黑 { if(cur == parent->_right) { RotateL(parent); std::swap(parent,cur); } RotateR(grandfather); parent->_color=BLACK; grandfather->_color=RED; break; } } else if(grandfather->_right == parent) { Node* uncle=grandfather->_left; if(uncle && uncle->_color==RED)// 叔叔存在且为红 { uncle->_color=parent->_color=BLACK; grandfather->_color=RED; cur=grandfather; parent=cur->_parent; } else // 叔叔不存在或存在且为黑 { if(cur == parent->_left) { RotateR(parent); std::swap(parent,cur); } RotateL(grandfather); parent->_color=BLACK; grandfather->_color=RED; break; } } } _root->_color=BLACK; ++_size; return make_pair(Iterator(newNode), true); } KeyOfValue kov; Iterator Find(const Key& k) { Node* cur=_root; while(cur) { if(kov(cur->_data) > k) { cur=cur->_left; } else if(kov(cur->_data) < k) { cur=cur->_right; } else { return Iterator(cur); } } return Iterator(nullptr); } const_Iterator Find(const Key& k) const { Node* cur=_root; while(cur) { if(kov(cur->_data) > k) { cur=cur->_left; } else if(kov(cur->_data) < k) { cur=cur->_right; } else { return const_Iterator(cur); } } return const_Iterator(nullptr); } private: // 左单旋 void RotateL(Node* parent) { Node* subR=parent->_right; Node* subRL=subR->_left; parent->_right=subRL; if(subRL != nullptr) { subRL->_parent=parent; } subR->_left=parent; Node* pparent=parent->_parent; parent->_parent=subR; if(pparent == nullptr) { _root=subR; subR->_parent=nullptr; } else { subR->_parent=pparent; if(pparent->_left == parent) { pparent->_left=subR; } else if(pparent->_right == parent) { pparent->_right=subR; } } } // 右单旋 void RotateR(Node* parent) { Node* subL=parent->_left; Node* subLR=subL->_right; parent->_left=subLR; if(subLR != nullptr) { subLR->_parent=parent; } subL->_right=parent; Node* pparent=parent->_parent; parent->_parent=subL; if(pparent == nullptr) { _root=subL; subL->_parent=nullptr; } else { subL->_parent=pparent; if(pparent->_left == parent) { pparent->_left=subL; } else if(pparent->_right == parent) { pparent->_right=subL; } } } size_t _size; Node* _root; };
五. map和set
1. map、set的基本框架
它们两个的成员变量都是一颗红黑树，并且都自己实现仿函数KeyOfValue。不同点在于模板参数不同，map因为存储键值对所以有两个模板参数；set只有一个模板参数Key。
// map的基本框架 template<class K, class V> class MyMap { typedef pair<K, V> ValueType; struct KeyOfValue { const K& operator()(const ValueType& v) { return v.first; } } private: RBTree<K, ValueType, KeyOfValue> _t; }; // set的基本框架 template<class K> class MySet { typedef K ValueType; struct KeyOfValue { const K& operator()(const ValueType& k) { return k; } }; private: RBTree<K, ValueType, KeyOfValue> _t; };
2. map、set和红黑树之间的关系
map、set都有的接口包括begin()、end()、empty()、size()、Find、Insert等等，看到上面这些接口有没有觉得很熟悉？没错，这些都是上面红黑树已经实现了的接口，map和set因为底层是红黑树所以可以直接调用这些接口，至于有多直接，从它们两个的完整代码里可见一斑。
map和set相当于红黑树的的一件衣服，对内把红黑树装饰和保护了起来，对外使得使用者操作红黑树更加方便、容易理解。
3. map、set完整代码
map
这里要注意一下 [ ] 这个操作符的重载，这是map独有的，底层通过封装Insert实现。方括号内我们传入Key，如果存在的话返回Value的引用；如果不存在，则新插入这个节点，它的Value为对应类型的一个匿名对象，调用其默认构造函数。即该操作符的功能是无论如何都返回给你对应key的value。
template<class K, class V> class MyMap { typedef pair<K, V> ValueType; struct KeyOfValue { const K& operator()(const ValueType& v) { return v.first; } }; public: typedef typename RBTree<K, ValueType, KeyOfValue>::Iterator Iterator; typedef typename RBTree<K, ValueType, KeyOfValue>::const_Iterator const_Iterator; pair<Iterator, bool> Insert(const ValueType& v) { return _t.Insert(v); } Iterator Begin() { return _t.Begin(); } const_Iterator Begin() const { return _t.Begin(); } Iterator End() { return _t.End(); } const_Iterator End() const { return _t.End(); } size_t Size() const { return _t.Size(); } bool Empty() const { return _t.Empty(); } Iterator Find(const K& k) { return _t.Find(k); } const_Iterator Find(const K& k) const { return _t.Find(k); } V& operator[](const K& k) { pair<Iterator, bool> ret=_t.Insert(make_pair(k, V())); return ret.first->second; } private: RBTree<K, ValueType, KeyOfValue> _t; };
set
template<class K> class MySet { typedef K ValueType; struct KeyOfValue { const K& operator()(const ValueType& k) { return k; } }; public: typedef typename RBTree<K, ValueType, KeyOfValue>::Iterator Iterator; typedef typename RBTree<K, ValueType, KeyOfValue>::const_Iterator const_Iterator; pair<Iterator, bool> Insert(const ValueType& k) { return _t.Insert(k); } Iterator Begin() { return _t.Begin(); } const_Iterator Begin() const { return _t.Begin(); } Iterator End() { return _t.End(); } const_Iterator End() const { return _t.End(); } bool Empty() const { return _t.Empty(); } size_t Size() const { return _t.Size(); } Iterator Find(const K& k) { return _t.Find(k); } const_Iterator Find(const K& k) const { return _t.Find(k); } private: RBTree<K, ValueType, KeyOfValue> _t; };
