前言
基于之前的红黑树和map、set的相关知识，本节我们使用红黑树来模拟实现STL中的map和set。
一、迭代器
使用迭代器可以方便我们对数据结构进行遍历，它使数据结构的底层实与用户的使用分离（封装了底层实现），因此我们要给红黑树增加一个迭代器。
1.begin()和end()
STL中明确规定，begin()和end()代表的是一段前闭后开的区间。我们知道对红黑树进行中序遍历可以得到一个有序的序列，因此begin()可以放置在红黑树的最小节点处（即，最左节点），end()应该放置在红黑树最大节点的下一个位置。但是最大结点的下一个位置是什么呢？这个位置是nullptr吗？答案是不能是nullptr，因为对end()位置进行–操作要能找到最后一个元素，如果设置为nullptr就找不到最后一个结点了。
我们可以给红黑树增加一个header结点，让最大结点的next指向它
但是我们只是对它进行模拟，理解它的底层原理即可，为了不要让代码太过复杂，我们本次模拟实现就不设定header结点，直接让end()为nullptr即可（不实现–）。
2.operator++()
找迭代器的下一个结点（它的值一定比当前结点的值大）
template<class T, class Ref, class Ptr> 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) {} 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 = _node->_parent; while (parent && cur == parent->_right) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; } bool operator!=(const Self& s) { return _node != s._node; } bool operator==(const Self& s) { return _node == s._node; } };
二、改造红黑树
namespace Jinger { enum Colour//结点颜色 { RED, BLACK, }; template<class K,class V> struct RBTreeNode//红黑树结点 { pair<K, V> _kv; typedef RBTreeNode<K, V> Node; RBTreeNode(const pair<K,V>& kv) :_kv(kv) , _parent(nullptr) , _left(nullptr) , _right(nullptr) , _colour(RED) {} Node* _parent; Node* _left; Node* _right; Colour _colour; }; template<class K, class V> struct __RBTreeIterator//迭代器 { typedef RBTreeNode<K,V> Node; typedef __RBTreeIterator<K,V> Self; Node* _node; __RBTreeIterator(Node* node) :_node(node) {} pair<K,V>& operator*() { return _node->_kv; } pair<K, V>* operator->() { return &_node->_kv; } Self& operator++() { if (_node->_right) { _node = _node->_right; } else { Node* parent = _node->_parent; if (_node == parent->_left) { _node = parent; } else { while (parent && _node == parent->_right) { _node = parent; parent = parent->_parent; } _node = parent; } } return *this; } bool operator!=(const Self& s) { return _node != s._node; } }; template<class K,class V> struct RBTree { typedef RBTreeNode<K,V> Node; typedef __RBTreeIterator<K,V> iterator; RBTree() :_root(nullptr) {} //左旋 void RotateL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; parent->_right = SubRL; if (SubRL) { SubRL->_parent = parent; } Node* Grandpa = parent->_parent; SubR->_left = parent; parent->_parent = SubR; if (!Grandpa) { _root = SubR; SubR->_parent = nullptr; } else { if (parent == Grandpa->_left) { Grandpa->_left = SubR; } else { Grandpa->_right = SubR; } } SubR->_parent = Grandpa; } //右旋 void RotateR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; Node* Grandpa = parent->_parent; parent->_parent = SubL; parent->_left = SubLR; if (SubLR) { SubLR->_parent = parent; } if (!Grandpa) { _root = SubL; SubL->_parent = nullptr; } else { if (parent == Grandpa->_left) { Grandpa->_left = SubL; } else { Grandpa->_right = SubL; } } SubL->_right = parent; } iterator begin() { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); } bool insert(const pair<K, V>& kv) { Node* newnode = new Node(kv); if (!_root)//空树 { _root = newnode; _root->_colour = BLACK; } else { Node* parent = _root; Node* cur = _root; while (cur) { parent = cur; if (cur->_kv.first > kv.first) { cur = cur->_left; } else if (cur->_kv.first < kv.first) { cur = cur->_right; } else { return false; } } if (parent->_kv.first > kv.first) { parent->_left = newnode; } else { parent->_right = newnode; } newnode->_parent = parent; cur = newnode; parent = cur->_parent; if (parent->_colour == BLACK)//如果父亲的结点为黑色 { return true; } while (parent && parent->_colour == RED)//如果parent为空，说明此时cur为根节点(如果调整到父节点为黑色就不需要再调整了） { Node* g = parent->_parent;//祖父 Node* u = nullptr;//叔叔结点 if (parent == g->_left)//如果父亲是祖父的左孩子，那么叔叔是祖父的右孩子 { u = g->_right; } else { u = g->_left; } if (u && u->_colour == RED) { g->_colour = RED; u->_colour = parent->_colour = BLACK; cur = g; parent = cur->_parent; } else//叔叔不存在/叔叔的结点为黑色 { //parent是g的右孩子，cur是parent的右孩子(左单旋) if (parent == g->_right && cur == parent->_right) { RotateL(g); parent->_colour = BLACK; g->_colour = RED; } //parent是g的左孩子，cur是parent的左孩子(右单旋) else if (parent == g->_left && cur == parent->_left) { RotateR(g); parent->_colour = BLACK; g->_colour = RED; } //parent是g的左孩子，cur是parent的右孩子(左右双旋) else if (parent == g->_left && cur == parent->_right) { RotateL(parent); RotateR(g); cur->_colour = BLACK; g->_colour = RED; } //parent是g的右孩子，cur是parent的左孩子(右左双旋) else if (parent == g->_right && cur == parent->_left) { RotateR(parent); RotateL(g); cur->_colour = BLACK; g->_colour = RED; } break; } } } _root->_colour = BLACK;//性质2要求根节点的颜色为黑色 return true; } void inoder() { _inorder(_root); } void _inorder(Node* root) { if (!root) return; _inorder(root->_left); cout << root->_kv.first << ":" << root->_kv.second<< " "; _inorder(root->_right); } bool _isbalance(Node* root, int count, const int& leftcount) { if (root == nullptr) { if (count != leftcount) { cout << "每条路径黑色结点数不相同，违反了性质4" << endl; return false; } else { return true; } } if (root->_colour == RED && root->_parent->_colour == RED) { cout << "父亲结点和cur都是红色，违反了性质3" << endl; return false; } if (root->_colour == BLACK) { count++; } bool left = _isbalance(root->_left, count, leftcount); bool right = _isbalance(root->_right, count, leftcount); return left && right; } bool isBalance() { if (_root == nullptr) { return true; } if (_root->_colour == RED) { cout << "根节点为红色，违反了性质2" << endl; return false; } int leftcount = 0; Node* cur = _root; while (cur->_left) { if (cur->_colour == BLACK) { leftcount++; } cur = cur->_left; } cout << leftcount << endl; return _isbalance(_root, 0, leftcount); } private: Node* _root; }; }
三、map的模拟实现
map的底层结构就是一个红黑树，因此在map中直接封装一个红黑树，然后包装一下它的借口即可。
namespace Jinger { 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; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } pair<iterator, bool> insert(const pair<const K, V>& kv) { return _t.insert(kv); } V& operator[](const K& k) { pair<iterator, bool> ret = _t.insert(make_pair(k, V())); return ret.first->second; } iterator& find(const K& k) { _t.find(k); } private: Jinger::RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; }
四、set的模拟实现
set的底层结构就是一个红黑树，因此在map中直接封装一个红黑树，然后包装一下它的借口即可。
namespace Jinger { 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(key); return pair<iterator, bool>(ret.first, ret.second); } private: RBTree<K, K, SetKeyOfT> _t; }; }
总结
以上就是今天要讲的内容，本文介绍了如何用红黑树模拟实现map和set的相关概念。本文作者目前也是正在学习C++相关的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出，也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！
