迭代器的设计
红黑树的迭代器属于双向迭代器，各种操作都类似于list，较为特殊的就是++和--，这两个操作完全依据红黑树的节点的排列法则
先处理++，根据红黑树的中序遍历：左子树-根-右子树
如果右子树不为空，可直接到右子树中寻找键值最小的节点便是根节点++之后的节点
如果右子树不存在，并且此时节点还是父节点的右节点，向上找到的祖先便是++之后的节点；如果此时节点是父节点的左节点，那么父节点便是++之后的节点
--操作于此相同
这里还需要注意一点的是红黑树的迭代器中存在着构造函数
当普通迭代器调用时，权限缩小，此时是拷贝构造；当const迭代器调用时，此时是构造函数
_RBTreeIterator(const iterator& s) :_node(s._node) {}
迭代器的完整代码如下
template<class T> struct _RBTreeIterator { typedef RBTreenode<T> node; typedef _RBTreeIterator<T, Ref, Ptr> Self; typedef _RBTreeIterator<T, T&, T*> iterator; node* _node; _RBTreeIterator(node* node) :_node(node) {} _RBTreeIterator(const iterator& s) :_node(s._node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { if (_node->_right) { node* min = _node->_right; while (min->_left) { min = min->_left; } _node = min; } else { node* cur = _node; node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; } Self& operator--() { if (_node->_left) { node* max = _node->_left; while (max->_right) { max = max->_right; } _node = max; } else { node* cur = _node; node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } };
结构
红黑树本质是二叉搜索树，每个节点存储的数据是键值对pair<key,value>，键值key唯一标识节点不可修改，实质value保存信息可以修改；
STL规定，begin()和end()代表一段前闭后开的区间，对红黑树进行中序遍历之后，可以得到有序序列，因此：begin()可以放在红黑树中最小节点的位置，end()可以放在最大节点的下一个位置（这里直接设置为空指针）
begin()
iterator begin() { node* left = _root; while (left && left->_left) { left = left->_left; } return iterator(left); }
end()
插入
插入操作的返回值是键值对pair
pair<iterator,bool> insert (const value_type& val);
红黑树是在二叉树搜索树的基础上加上其平衡条件，因此红黑树的插入可分两步：
按照二叉搜索树的规则插入新节点
检测新节点插入之后，红黑树的性质是否被破坏
新增节点必须是红色的，如果双亲结点的颜色是黑色，则没有违反红黑树规则，不需要调整；如果双亲结点是红色，此时就违反了双亲结点的规则3不能有连续的红色节点，需要进行调整；根据叔叔节点的情况，调整的情景也分为3种：
约定：新增节点为cur，父节点为p，祖父节点为g，叔叔节点为u
cur为红,p为红,g为黑,u存在且为红
调整操作：将父节点 p和叔叔节点 u改为黑色，祖父节点 g改为红色；将祖父节点 u作为新增节点，继续向上调整
cur为红,p为红,g为黑,u不存在/存在且为黑
调整操作：如果父节点 p是祖父节点 g的左节点，新增节点cur是父节点p的左节点，进行左单旋；相反，父节点 p是祖父节点 g的右节点，新增节点cur是父节点p的右节点，进行左单旋
以父节点 p为轴点进行左单旋；将父节点 p改为黑色，祖父节点 g改为红色；父节点 p作为新增节点继续向上调整
cur为红,p为红,g为黑,u不存在/存在且为黑
调整操作：如果父节点p是祖父节点g的左节点，新增节点cur是父节点p的右节点，则以父节点p为轴心进行左单旋；如果父节点p是祖父节点g的右节点，新增节点cur是父节点p的左节点，则以父节点p为轴心进行右单旋
以父节点p为轴心进行左单旋，转换成情景二进行调整
pair<iterator, bool>insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } node* parent = nullptr; node*newnode=node(cur); node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return make_pair(iterator(cur),false); } } cur = new node(kv); node* newnode = cur; cur->_col = RED; if (parent->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } while (parent && parent->_col == RED) { node* grandfather = parent->_parent; if (parent == grandfather->_left) { node* uncle = grandfather->_right; //情景1，叔叔存在且为红 if (uncle && uncle->_col == RED) { parent->_col == uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { //情景2 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { //情景3 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 { if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return make_pair(iterator(newnode), true); }
红黑树模拟实现set与map
通过红黑树来模拟实现这两种容器，首先要解决的一个问题就是：set的节点中存储的数据是key(也是value)，而map中存储的是键值对pair<key,value>；所以在红黑树中先要修改节点中存储数据的类型，使得当模板根据不同的类型，实现不同的容器
节点改造如下
enum Color { RED, BLACK, }; template<class T> struct RBTreenode { T _data;//数据类型 RBTreenode<T>* _left; RBTreenode<T>* _right; RBTreenode<T>* _parent; Color _col; RBTreenode(const T& data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED) {} };
节点修改之后，还会出现一个问题，在进行插入操作时，会将待插入节点的键值与根节点的键值进行比较，但是由于此时节点中的数据类型是data，如果是模拟实现set那么不会出现任何问题；如果是模拟实现map，编译器也不清楚data是表示键值还是实值，而且键值对pair中的比较大小的函数，并不是只比较键值大小
所以这时便需要想办法将键值对中的键值取出来；解决办法：在红黑树模板中加上一个模板参数KeyofT，创建仿函数；当实现set是data的是键值也是实值，当实现map时取出键值对pair中的键值即可
改造红黑树如下
//map->RBTree<K,pair<const K,V>,MapKeyofT> _t //set->RBTree<K,K,SetKeyofT> _t 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*>const_iterator; ~RBTree() { ...... } iterator begin() { node* left = _root; while (left && left->_left) { left = left->_left; } return iterator(left); } iterator end() { return iterator(nullptr); } const_iterator begin() const { node* left = _root; while (left && left->_left) { left = left->left; } return const_iterator(left); } const_iterator end() const { return const_iterator(nullptr); } pair<iterator, bool>insert(const T& data) { ...... return make_pair(iterator(newnode), true); } private: node* _node = nullptr; };
模拟实现map
template<class K,class V> class map { //获取键值 struct MapkeyofT { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, MapkeyofT>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapkeyofT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() { return _t.begin(); } const_iterator end() { return _t.end(); } pair<iterator, bool>insert(const pair<const 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<const T, V>, MapkeyofT> _t; };
模拟实现set
template<class K> class set { struct SetkeyofT { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree<K, K, SetkeyofT>::const_iterator iterator; typedef typename RBTree<K, K, SetkeyofT>::const_iterator const_iterator; iterator begin() const { return _t.begin(); } iterator end() const { return _t.end(); } pair<iterator, bool>insert(const K& key) { pair<typename RBTree<K, K, SetkeyofT>::iterator, bool>ret = _t.insert(); return pair<iterator, bool>(ret.first, ret.second); } private: RBTree<K, K, SetkeyofT> _t; };
