深入浅出C++ ——红黑树模拟实现STL中的set与map

一、红黑树

    红黑树作为set和map的底层容器，既要实现插入key又要实现插入pair，所以做了稍许的改动，使其成为一颗泛型结构的红黑树，通过不同的实例化参数，实现set和map。如果要生成set，就传（key，key）；如果要生成map，就传（key，pair），由第二个参数来控制生成容器的结构。

---

改动

    在定义模板的红黑树节点时，由template<class K, class V> 改为template<class T>，因为是泛型，所以原本的pair<K, V> _kv;改为T _data;。红黑树的模板template<class K, class V>也改为template<class T> ，在内部代码中，将所有的pair<K, V>都改为T，kv改为data。

     在模拟实现set时，定义成员变量为RBTree<K, K> _t; ，在模拟实现map的时候，定义成员变量为RBTree<K, pair<K, V>> _t; 。但是在插入的过程中，比较大小时，不能用data来比较，因为对于map而言，data是pair，要用pair中的first来比较，可以使用仿函数来实现。

---

set的底层成员

RBTree<K, K, SetKeyOfT> _t；

---

map的底层成员

RBTree<K, pair<K, V>, MapKeyOfT> _t; 

---

红黑树的迭代器

     红黑树的begin迭代器是整棵树的最左侧节点，end迭代器是空。

     迭代器++分为两种情况，如果该节点右子树不为空，就找右子树的最左节点。如果该节点的右子树为空，就找祖先里面孩子不是祖先的右的那个。

     迭代器–分为两种情况，如果该节点右子树不为空，就找左子树的最右节点。如果该节点的右子树为空，就找祖先里面孩子不是祖先的左的那个。

---

泛型红黑树

#pragma once
enum Colour
{RED,BLACK
};template<class T>
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){}
};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) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}Self& operator++(){if (_node->_right){// 下一个就是右子树的最左节点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{// 找祖先里面孩子不是祖先的右的那个Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){// 下一个是左子树的最右节点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{// 孩子不是父亲的左的那个祖先Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
};template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}pair<iterator, bool> Insert(const T& data){KeyOfT kot;if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}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 make_pair(iterator(cur), false);}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);// 关键看叔叔if (parent == grandfater->_left){Node* uncle = grandfater->_right;// 情况一 : uncle存在且为红，变色+继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}// 情况二+三：uncle不存在 + 存在且为黑else{// 情况二：右单旋+变色//     g //   p   u// cif (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三：左右单旋+变色//     g //   p   u//     cRotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else // (parent == grandfater->_right){Node* uncle = grandfater->_left;// 情况一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}else{// 情况二：左单旋+变色//     g //   u   p//         cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三：右左单旋+变色//     g //   u   p//     cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}// 黑色节点数量基准值int benchmark = 0;return PrevCheck(_root, 0, benchmark);}private:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){//cout << blackNum << endl;//return;if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}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;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}private:Node* _root = nullptr;
};

---

二、用泛型红黑树模拟实现set

#include "TRBTree.hPP"
namespace Jared
{template<class K>class set{//仿函数实现比较struct SetKeyOfT{const K& operator()(const K& key){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;};
}

---

三、用泛型红黑树模拟实现map

#include "TRBTree.hPP"
namespace Jared
{template<class K, class V>class map{//仿函数实现比较struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;//typename告诉编译器这一段代码是类型，不是静态变量iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}