完整代码
RBTree.h
#include<iostream> #include<cassert> using namespace std; enum Color//利用枚举来给红黑树配色 { RED, BLACK }; template<class T> struct RBTreeNode { RBTreeNode(const T& data) :_data(data) , _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦 , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; T _data; Color _color;//结点的配色 }; 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) {} //普通迭代器传给普通迭代器用的是默认生成的拷贝构造 //当迭代器是const的时候用的就是普通迭代器构造的const迭代器 RBTreeIterator(const iterator& s) :_node(s._node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { if (_node->_right)//右子树不为空 { Node* cur = _node->_right; while (cur->_left) { cur = cur->_left; } _node = cur; } else//左子树为空 { Node* parent = _node->_parent; Node* cur = _node; while (parent && parent->_left != cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } Self& operator--() { if (_node->_left)//左子树不为空 { Node* cur = _node->_left; while (cur && cur->_right) { cur = cur->_right; } _node = cur; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur != parent->_right) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } }; template<class K, class T, class KeyOFV> class RBTree { typedef RBTreeNode<T> Node; public: typedef RBTreeIterator<T, T&, T*> iterator; typedef RBTreeIterator<T, const T&, const T*> const_iterator; iterator begin() { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); } const_iterator begin()const { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return const_iterator(cur); } const_iterator end()const { return const_iterator(nullptr); } pair<iterator, bool> Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_color = BLACK; return make_pair(iterator(_root), true); } Node* cur = _root; Node* parent = nullptr; KeyOFV kot;//仿函数对象 while (cur) { if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(data);//这里默认是红色结点 Node* newnode = cur;//因为cur会变位置，所以储存一下新节点 if (kot(parent->_data) > kot(data)) { cur->_parent = parent; parent->_left = cur; } else if (kot(parent->_data) < kot(data)) { cur->_parent = parent; parent->_right = cur; } //如果父节点为空就代表cur是根节点，没必要调整了 //还要判断cur结点是否与父节点的颜色均为红色 while (parent && parent->_color == RED) { Node* grandfather = parent->_parent;//祖父结点 if (parent == grandfather->_left)//新增结点在祖父左 { Node* uncle = grandfather->_right; //情况一 if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在 { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather;//最后让cur等于祖父结点的位置 parent = cur->_parent; } else { if (parent->_left == cur)//情况二 { RotateR(grandfather);//右单旋 grandfather->_color = RED; parent->_color = BLACK; } else if (parent->_right == cur)//情况三 { RotateL(parent);//左单旋 RotateR(grandfather);//右单旋 cur->_color = BLACK; grandfather->_color = RED; } break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环 } } else//新增结点在祖父右 { Node* uncle = grandfather->_left; if (uncle && uncle->_color == RED)//情况一 { uncle->_color = BLACK; parent->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right)//情况二 { RotateL(grandfather); grandfather->_color = RED; parent->_color = BLACK; } else if (cur == parent->_left)//情况三 { RotateR(parent); RotateL(grandfather); cur->_color = BLACK; grandfather->_color = RED; } break; } } } _root->_color = BLACK; return make_pair(iterator(newnode), true); } void RotateL(Node* parent)//左单旋 { Node* pparent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; if (pparent) { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; } else { _root = subR; } subR->_parent = pparent; } void RotateR(Node* parent)//右单旋 { Node* pparent = parent->_parent; Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (pparent) { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; } else { _root = subL; } subL->_parent = pparent; } void Inorder() { _Inorder(_root); } bool IsBalanceTree() { if (_root == nullptr) return true; if (_root->_color != BLACK) { cout << "根不为黑色" << endl; return false; } int count = 0; Node* cur = _root; while (cur) { if (cur->_color == BLACK) count++; cur = cur->_left;//找一条路径上的黑节点 } _IsBalanceTree(_root, 0, count); } private: bool _IsBalanceTree(Node* root, int k, int sum)//验证 { if (root == nullptr) { if (k == sum)//这里代表当前路径点和最左边的路径点相同 return true; else { cout << "每条路径上黑色结点数量不同" << endl; } return false; } if (root->_color == BLACK) k++; if (root->_parent && root->_parent->_color == RED && root->_color == RED) { cout << root->_parent->_data.first << endl; return false; } return _IsBalanceTree(root->_left, k, sum) && _IsBalanceTree(root->_right, k, sum); } void _Inorder(Node* _root) { if (_root == nullptr) return; _Inorder(_root->_left); cout << _root->_data.first << ":" << _root->_data.second << endl; _Inorder(_root->_right); } Node* _root = nullptr; };
set.h
#include"RBTree.h" namespace baiye { template<class K> class set { struct setKeyOFV { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本 typedef typename RBTree<K, K, setKeyOFV>::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, setKeyOFV>::iterator, bool> it = _t.Insert(key);//这里接收的是普通迭代器 return pair<iterator, bool>(it.first, it.second);//这里用普通迭代器构造const迭代器 } private: RBTree<K, K, setKeyOFV> _t; }; void settest() { int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; set<int>s; for (auto& e : arr) { s.insert(e); } set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; } }
map.h
#include"RBTree.h" namespace baiye { template<class K, class V> class map { struct mapKeyOFV { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator; iterator begin() { return _p.begin(); } iterator end() { return _p.end(); } const_iterator begin()const { return _p.begin(); } const_iterator end()const { return _p.end(); } pair<iterator, bool> insert(const pair<const K, V>& kv) { return _p.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> it = insert(make_pair(key, V())); return it.first->second; } private: RBTree<K, pair<const K, V>, mapKeyOFV> _p; }; void maptest() { int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; map<int, int> m; for (auto& e : arr) { m.insert(make_pair(e, e)); } map<int, int>::iterator it = m.begin(); while (it != m.end()) { cout << it->first << " "; ++it; } cout << endl; } }
