文章目录
- 1. 红黑树的迭代器
- 2. 改造红黑树
- 3. map 的模拟实现
- 4. set 的模拟实现
在 C++ STL 库中,map 与 set 的底层为红黑树,那么在不写冗余代码的情况下使用红黑树同时实现 map 与 set 便是本文的重点。
1. 红黑树的迭代器
迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器,需要考虑以下问题:
-
begin() 与 end()
STL 明确规定,begin() 与 end() 代表的是一段前闭后开的区间,而对红黑树进行中序遍历后,可以得到一个有序的序列,因此:begin() 可以放在红黑树中最小节点(即最左侧节点)的位置,end() 放在最大节点(最右侧节点)的下一个位置。
iterator begin() { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return iterator(subLeft); } const_iterator begin() const { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return const_iterator(subLeft); } iterator end() { return iterator(nullptr); } const_iterator end() const { return const_iterator(nullptr); }
-
operator++() 与 operator--()
Self& operator++() { if (_node->_right) { // 右子树的中序第一个(最左节点) Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else { // 祖先里面孩子是父亲左的那个 Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } Self& operator--() { // 跟++逻辑相反 return *this; }
2. 改造红黑树
#pragma once enum Color { RED, BLACK }; template struct RBTreeNode { RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Color _col; T _data; RBTreeNode(const T& data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} }; template struct RBTreeIterator { typedef RBTreeNode Node; typedef RBTreeIterator Self; Node* _node; RBTreeIterator(Node* node) : _node(node) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { if (_node->_right) { // 右子树的中序第一个(最左节点) Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else { // 祖先里面孩子是父亲左的那个 Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } Self& operator--() { // 跟++逻辑相反 return *this; } bool operator!=(const Self& s) { return _node != s._node; } bool operator==(const Self& s) { return _node == s._node; } }; // set->RBTree // map->RBTree // 因为关联式容器中存储的是的键值对,因此 // K为key的类型 // T:如果是map,则为pair;如果是set,则为K // KeyOfT仿函数,取出T对象中的key template class RBTree { typedef RBTreeNode Node; public: typedef RBTreeIterator iterator; typedef RBTreeIterator const_iterator; iterator begin() { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return iterator(subLeft); } const_iterator begin() const { Node* subLeft = _root; while (subLeft && subLeft->_left) { subLeft = subLeft->_left; } return const_iterator(subLeft); } iterator end() { return iterator(nullptr); } const_iterator end() const { return const_iterator(nullptr); } iterator Find(const K& key) { KeyOfT kot; Node* cur = _root; while (cur) { if (kot(cur->_data) _right; } else if (kot(cur->_data) > key) { cur = cur->_left; } else { return iterator(cur); } } return end(); } pair Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } KeyOfT kot; Node* parent = nullptr; Node* cur = _root; while (cur) { if (kot(cur->_data) _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; if (kot(parent->_data) _right = cur; } else { parent->_left = cur; } cur->_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 // c if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return make_pair(iterator(newnode), true); } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (parent == _root) { _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; subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } } private: Node* _root = nullptr; };
3. map 的模拟实现
map 的底层结构就是红黑树,因此在 map 中直接封装一棵红黑树,然后将其接口包装下即可。
#pragma once #include "RBTree.h" namespace tjq { template class map { struct MapKeyOfT { const K& operator()(const pair& kv) { return kv.first; } }; public: typedef typename RBTree::iterator iterator; typedef typename RBTree::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } pair insert(const pair& kv) { return _t.Insert(kv); } iterator find(const K& key) { return _t.Find(key); } V& operator[](const K& key) { pair ret = insert(make_pair(key, V())); return ret.first->second; } private: RBTree _t; }; }
4. set 的模拟实现
set 的底层为红黑树,因此只需在 set 内部封装一棵红黑树,即可将该容器实现出来。
#pragma once #include "RBTree.h" namespace tjq { template class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree::iterator iterator; typedef typename RBTree::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } pair insert(const K& key) { return _t.Insert(key); } iterator find(const K& key) { return _t.Find(key); } private: RBTree _t; }; }
END
-