1.红黑树源码
我们使用上节课的红黑树源码来封装map和set.
因为map存的是（key,value）,set存的是（key）,为了我们set和map使用同一个类模板（红黑树），所以我们先要修改红黑树结点中存的数据类型，我们使用模板来初始化，根据实列化来决定结点中存的是pair,还是只有一个数据
做出修改：代码中所有key的地方用data代替，而data的数据类型是T，当是set实列化的时候T就是int(一种)，当是map的时候T就是pair,比方说pair<string,int>
#include<iostream> #include<string> using namespace std; 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) , _col(RED) {} }; template<class T> class rbtree { typedef rbtreenode<T> node; public: void spinleft(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 (ppnode == nullptr) { _root = subr; subr->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subr; subr->_parent = ppnode; } else { ppnode->_right = subr; subr->_parent = ppnode; } } } void spinright(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 (ppnode == nullptr) { _root = subl; subl->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subl; subl->_parent = ppnode; } else { ppnode->_right = subl; subl->_parent = ppnode; } } } void spinlr(node* parent) { node* subl = parent->_left; node* sublr = subl->_right; //int bf = sublr->_bf; spinleft(parent->_left); spinright(parent); /* if (bf == 1) { subl->_bf = -1; sublr->_bf = 0; parent->_bf = 0; } else if (bf == -1) { subl->_bf = 0; sublr->_bf = 0; parent->_bf = 1; } else { subl->_bf = 0; sublr->_bf = 0; parent->_bf = 0; }*/ } void spinrl(node* parent) { node* subr = parent->_right; node* subrl = subr->_left; //int bf = subrl->_bf; spinright(subr); spinleft(parent); /* if (bf == 1) { parent->_bf = -1; subr->_bf = 0; subrl->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subr->_bf = 1; subrl->_bf = 0; } else { subr->_bf = 0; subrl->_bf = 0; parent->_bf = 0; }*/ } bool insert(const T& data) { if (_root == nullptr) { _root = new node(data); _root->_col = BLACK; return true; } node* cur = _root; node* parent = nullptr; while (cur) { if (cur->_data > data) { parent = cur; cur = cur->_left; } else if (cur->_data < data) { parent = cur; cur = cur->_right; } else { return false; } } cur = new node(data); if (parent->_data > data) { parent->_left = cur; } else { parent->_right = 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 = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { spinright(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinleft(parent); spinright(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { spinleft(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinright(parent); spinleft(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } bool Check(node* cur) { if (cur == nullptr) return true; if (cur->_col == RED && cur->_parent->_col == RED) { cout << cur->_key<< "存在连续的红色节点" << endl; return false; } return Check(cur->_left) && Check(cur->_right); } bool IsBalance() { if (_root && _root->_col == RED) return false; return Check(_root); } void inorder() { _inorder(_root); } void _inorder(node* root) { if (root == nullptr) return; _inorder(root->_left); cout << root->_data << endl; _inorder(root->_right); } node* Find(const T& data) { node* cur = _root; node* parent = nullptr; while (cur) { if (cur->_data > data) { parent = cur; cur = cur->_left; } else if (cur->_data < _data) { parent = cur; cur = cur->_right; } else { return cur; } } return nullptr; } private: int treeheight(node* root) { if (root == nullptr) return 0; int leftheight = treeheight(root->_left); int rightheight = treeheight(root->_right); return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } node* _root = nullptr; }; int main() { rbtree<int>st; int a[] = //{ 16,3,1 };//测试右旋 //{ 16,32,58 };//测试左旋 //{ 8,3,1,10,6,4};//测试右左旋 { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 }; for (auto e : a) { st.insert(e); } st.inorder(); int ret = st.IsBalance(); cout << endl; cout << ret; }
2.set和map类的简单封装
#pragma once #include"rbtree.h" namespace zjw { template<class K,class V> class map { public: private: rbtree<K,pair<K,V>>_st; }; }
#pragma once #include"rbtree.h" namespace zjw { template<class K> class set { public: private: rbtree<K, K>_st; }; }
3.map和set调用底层rbtree的insert函数
#pragma once #include"rbtree.h" namespace zjw { template<class K,class V> class map { public: bool insert(cosnt pair<K, V>& kv) { return _st.insrt(kv); } private: rbtree<K,pair<K,V>>_st; }; }
#pragma once #include"rbtree.h" namespace zjw { template<class K> class set { public: bool insert(const K& key) { return _st.insert(key); } private: rbtree<K, K>_st; }; }
4.阶段测试
5._data的元素提取
因为我们不管是map还是set,他们插入都是根据第一个模板参数比较大小，来确定插入当前结点的左还是右，但是为什么之前的代码没有报错？？
因为如果是map的话，pair也是可以比较大小的，规则是第一个大的大。第一个一样大，就比较第二个，第二个谁大就大
但是我们回顾之前的map和set都是按照第一个比较，所以我们可以这样做。在map和set类中定义内部类，如果rbtree中有需要比较data大小时，初始化一个内部类取data第一个内容来比较，我们只需要在map和set中初始化一个内部类对象即可返回data的第一个内容。
在rbtree中需要比较_data的地方都需要使用类对象来返回data的第一个内容
#pragma once #include<iostream> #include<string> using namespace std; 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) , _col(RED) {} }; template<class K,class T,class OFKEY> class rbtree { typedef rbtreenode<T> node; public: void spinleft(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 (ppnode == nullptr) { _root = subr; subr->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subr; subr->_parent = ppnode; } else { ppnode->_right = subr; subr->_parent = ppnode; } } } void spinright(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 (ppnode == nullptr) { _root = subl; subl->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subl; subl->_parent = ppnode; } else { ppnode->_right = subl; subl->_parent = ppnode; } } } void spinlr(node* parent) { node* subl = parent->_left; node* sublr = subl->_right; //int bf = sublr->_bf; spinleft(parent->_left); spinright(parent); /* if (bf == 1) { subl->_bf = -1; sublr->_bf = 0; parent->_bf = 0; } else if (bf == -1) { subl->_bf = 0; sublr->_bf = 0; parent->_bf = 1; } else { subl->_bf = 0; sublr->_bf = 0; parent->_bf = 0; }*/ } void spinrl(node* parent) { node* subr = parent->_right; node* subrl = subr->_left; //int bf = subrl->_bf; spinright(subr); spinleft(parent); /* if (bf == 1) { parent->_bf = -1; subr->_bf = 0; subrl->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subr->_bf = 1; subrl->_bf = 0; } else { subr->_bf = 0; subrl->_bf = 0; parent->_bf = 0; }*/ } bool insert(const T& data) { OFKEY sk; if (_root == nullptr) { _root = new node(data); _root->_col = BLACK; return true; } node* cur = _root; node* parent = nullptr; while (cur) { if (sk(cur->_data) > sk(data)) { parent = cur; cur = cur->_left; } else if (sk(cur->_data) < sk(data)) { parent = cur; cur = cur->_right; } else { return false; } } cur = new node(data); if (sk(parent->_data) > sk(data)) { parent->_left = cur; } else { parent->_right = 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 = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { spinright(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinleft(parent); spinright(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { spinleft(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinright(parent); spinleft(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } bool Check(node* cur) { if (cur == nullptr) return true; if (cur->_col == RED && cur->_parent->_col == RED) { cout << cur->_data << "存在连续的红色节点" << endl; return false; } return Check(cur->_left) && Check(cur->_right); } bool IsBalance() { if (_root && _root->_col == RED) return false; return Check(_root); } void inorder() { _inorder(_root); } void _inorder(node* root) { if (root == nullptr) return; _inorder(root->_left); cout << root->_data << endl; _inorder(root->_right); } node* Find(const T& data) { OFKEY sk; node* cur = _root; node* parent = nullptr; while (cur) { if (sk(cur->_data) > sk(data)) { parent = cur; cur = cur->_left; } else if (sk(cur->_data) < sk(data)) { parent = cur; cur = cur->_right; } else { return cur; } } return nullptr; } private: int treeheight(node* root) { if (root == nullptr) return 0; int leftheight = treeheight(root->_left); int rightheight = treeheight(root->_right); return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } node* _root = nullptr; };
6.迭代器
template<class T,class Pef,class Ptr> struct _rbtreeIterator { typedef rbtreenode<T> node; typedef _rbtreeIterator<T, Pef, Ptr> Self; Node* _node; public: _rbtreeIterator(Node* node) :_node(node) { //默认构造 } Self& operator++() { //迭代器++ } Self& operator--() { //迭代器-- } bool operator!=(Self& s) { //两个结点是否是同一结点 } Pef operator*() { //重载* } Ptr operator->() { //重载-> } };
上面迭代器封装在list里面有说过
template<class T,class Pef,class Ptr> struct _rbtreeIterator { typedef rbtreenode<T> node; typedef _rbtreeIterator<T, Pef, Ptr> Self; Node* _node; public: _rbtreeIterator(Node* node) :_node(node) { //默认构造 } Self& operator++() { //迭代器++ } Self& operator--() { //迭代器-- } bool operator!=(Self& s) { //两个结点是否是同一结点 return _node != s._node; } Pef operator*() { //重载* return _node->_data; } Ptr operator->() { //重载-> return &_node->_data } };
重点说一下迭代器++和–，
Self& operator++() { //迭代器++ if (_node->_right) { Node* next = _node->_right; while (next->_left) { next = next->_left; } _node = next; } }
如果_node没有右结点的话，迭代器++下一个位置应该是哪里呢？
比方说_node在6的位置
Self& operator++() { //迭代器++ if (_node->_right) { Node* next = _node->_right; while (next->_left) { next = next->_left; } _node = next; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right)//循环找孩子是父亲左的父亲，该父亲是下一个迭代器的结点 { cur = parent; parent = parent->_parent; } _node = parent; } return *this; }
同理–
Self& operator--() { //迭代器-- if (_node->_left) { Node* next = _node->_left; while (next->_right) { next = next->_right; } _node = next; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; }
红黑树调用迭代器
template<class K,class T,class OFKEY> class rbtree { typedef rbtreenode<T> node; typedef _rbtreeIterator<T, T&, T*> iterator; public: iterator begin() { //红黑树根结点的最左结点为最小 node* cur = _root->_left; while (cur) { cur = cur->_left; } return iterator(cur); } iterator end() { //空 return iterator(nullptr); }
7.set迭代器测试
#pragma once #include"rbtree.h" namespace zjw { template<class K> class set { struct SETOFKEY { const K& operator()(const K&key) { return key; } }; public: typedef typename rbtree<K, K, SETOFKEY>::iterator iterator; bool insert(const K& key) { return _st.insert(key); } iterator begin() { return _st.begin(); } iterator end() { return _st.end(); } private: rbtree<K, K,SETOFKEY>_st; }; void testset() { set<int>s; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 }; for (auto e : a) { s.insert(e); } set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << endl; ++it; } } }
#include<iostream> #include<string> #include"mymap.h" #include"myset.h" using namespace std; int main() { //zjw::testmap(); zjw::testset(); }
8.map迭代器测试
#pragma once #include"rbtree.h" namespace zjw { template<class K,class V> class map { struct MAPOFKEY { const K& operator()(const pair<K,V>&kv) { return kv.first; } }; public: typedef typename rbtree<K, pair<K,V>, MAPOFKEY>::iterator iterator; bool insert(const pair<K, V>& kv) { return _st.insert(kv); } iterator begin() { return _st.begin(); } iterator end() { return _st.end(); } private: rbtree<K,pair<K,V>, MAPOFKEY>_st; }; void testmap() { map<string, int>sr; sr.insert(make_pair("b", 1)); sr.insert(make_pair("think", 1)); sr.insert(make_pair("cool", 1)); map<string, int>::iterator it = sr.begin(); // //auto it = dic.begin(); while (it != sr.end()) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; } }
#include<iostream> #include<string> #include"mymap.h" #include"myset.h" using namespace std; int main() { zjw::testmap(); //zjw::testset(); }
9.实现map重载operator[]
根据map的insert我们需要修改底层的rbtree的insert实现
返回的是pair<iterator,bool>，这个类型在之前的map|set中有讲过
所以修改rbtree为(只展示修改部分)
pair<iterator,bool> insert(const T& data) { OFKEY sk; if (_root == nullptr) { _root = new node(data); _root->_col = BLACK; return make_pair(iterator(_root),true); //true代表没有，插入,_root是要插入的结点 } node* cur = _root; node* parent = nullptr; while (cur) { if (sk(cur->_data) > sk(data)) { parent = cur; cur = cur->_left; } else if (sk(cur->_data) < sk(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur),false);//查找，发现红黑树中有，则插入失败，cur为当前存在的结点 } } cur = new node(data); node* flag = cur;//标记防止下边旋转找不到要插入的结点 if (sk(parent->_data) > sk(data)) { parent->_left = cur; } else { parent->_right = 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 = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { spinright(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinleft(parent); spinright(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { spinleft(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinright(parent); spinleft(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return make_pair(iterator(flag),true);//flag为新插入节点的地址 }
而set为了让map可以重载operator[],set的insert返回值也应该是pair<iterator,bool>
测试map的operator[]
void test_map() { string arr[] = { "string","string","apple" ,"apple", "blalala","blalala" }; map<string, int>countmap; for (auto& e : arr) { countmap[e]++; } for (auto& kv : countmap) { cout << kv.first << ":" << kv.second << endl; } }
10.红黑树实现析构
~rbtree() { destroy(_root); } void destroy(node* root) { if (root == nullptr) return; destroy(root->_left); destroy(root->_right); root = nullptr; }
后序析构
11.红黑树的拷贝构造
rbtree(rbtree<K, T, OFKEY>&st) { _root = copy(st._root); } node* copy(node* root) { if (root == nullptr) return nullptr; node* cur = new node(root->data); cur->_col = root->_col; cur->_left=copy(root->_left); if (cur->_left) cur->_left->_parent = cur; cur->_right = copy(root->_right); if (cur->_right) cur->_right->_parent = cur; return root; }
先序遍历一个一个拷贝构造
12红黑树的赋值
rbtree < K, T, OFKEY >operator=(rbtree<K, T, OFKEY>& st) { swap(_root, st._root); }
赋值的话，老的红黑树不用了，直接交换两个头节点的地址
13.源码分享
rbtree.cpp
#include<iostream> #include<string> #include"mymap.h" #include"myset.h" using namespace std; int main() { //zjw::testmap(); //zjw::test_set(); // zjw::test_map(); }
rbtree.h
#pragma once #include<iostream> #include<string> using namespace std; 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) , _col(RED) {} }; template<class T,class Pef,class Ptr> struct _rbtreeIterator { typedef rbtreenode<T> Node; typedef _rbtreeIterator<T, Pef, Ptr> Self; Node* _node; public: _rbtreeIterator(Node* node) :_node(node) { //默认构造 } Self& operator++() { //迭代器++ if (_node->_right) { Node* next = _node->_right; while (next->_left) { next = next->_left; } _node = next; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } Self& operator--() { //迭代器-- if (_node->_left) { Node* next = _node->_left; while (next->_right) { next = next->_right; } _node = next; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } bool operator!=(const Self& s) const { //两个结点是否是同一结点 return _node != s._node; } Pef operator*() { //重载* return _node->_data; } Ptr operator->() { //重载-> return &_node->_data; } }; template<class K,class T,class OFKEY> class rbtree { public: typedef rbtreenode<T> node; typedef _rbtreeIterator<T, T&, T*> iterator; //typedef _rbtreeIterator<T, const T&,const T*> con_iterator; ~rbtree() { destroy(_root); } void destroy(node* root) { if (root == nullptr) return; destroy(root->_left); destroy(root->_right); root = nullptr; } rbtree < K, T, OFKEY >operator=(rbtree<K, T, OFKEY>& st) { swap(_root, st._root); } node* copy(node* root) { if (root == nullptr) return nullptr; node* cur = new node(root->data); cur->_col = root->_col; cur->_left=copy(root->_left); if (cur->_left) cur->_left->_parent = cur; cur->_right = copy(root->_right); if (cur->_right) cur->_right->_parent = cur; return root; } iterator begin() { //红黑树根结点的最左结点为最小 node* cur = _root; while (cur->_left) { cur = cur->_left; } return iterator(cur); } iterator end() { //空 return iterator(nullptr); } //con_iterator begin() const //{ // //红黑树根结点的最左结点为最小 // node* cur = _root; // while (cur->_left) // { // cur = cur->_left; // } // return con_iterator(cur); //} //con_iterator end() const //{ // //空 // return con_iterator(nullptr); //} void spinleft(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 (ppnode == nullptr) { _root = subr; subr->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subr; subr->_parent = ppnode; } else { ppnode->_right = subr; subr->_parent = ppnode; } } } void spinright(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 (ppnode == nullptr) { _root = subl; subl->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subl; subl->_parent = ppnode; } else { ppnode->_right = subl; subl->_parent = ppnode; } } } void spinlr(node* parent) { node* subl = parent->_left; node* sublr = subl->_right; //int bf = sublr->_bf; spinleft(parent->_left); spinright(parent); /* if (bf == 1) { subl->_bf = -1; sublr->_bf = 0; parent->_bf = 0; } else if (bf == -1) { subl->_bf = 0; sublr->_bf = 0; parent->_bf = 1; } else { subl->_bf = 0; sublr->_bf = 0; parent->_bf = 0; }*/ } void spinrl(node* parent) { node* subr = parent->_right; node* subrl = subr->_left; //int bf = subrl->_bf; spinright(subr); spinleft(parent); /* if (bf == 1) { parent->_bf = -1; subr->_bf = 0; subrl->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subr->_bf = 1; subrl->_bf = 0; } else { subr->_bf = 0; subrl->_bf = 0; parent->_bf = 0; }*/ } pair<iterator,bool> insert(const T& data) { OFKEY sk; if (_root == nullptr) { _root = new node(data); _root->_col = BLACK; return make_pair(iterator(_root),true); //true代表没有，插入,_root是要插入的结点 } node* cur = _root; node* parent = nullptr; while (cur) { if (sk(cur->_data) > sk(data)) { parent = cur; cur = cur->_left; } else if (sk(cur->_data) < sk(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur),false);//查找，发现红黑树中有，则插入失败，cur为当前存在的结点 } } cur = new node(data); node* flag = cur;//标记防止下边旋转找不到要插入的结点 if (sk(parent->_data) > sk(data)) { parent->_left = cur; } else { parent->_right = 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 = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { spinright(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinleft(parent); spinright(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_left) { spinleft(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { spinright(parent); spinleft(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return make_pair(iterator(flag),true);//flag为新插入节点的地址 } bool Check(node* cur) { if (cur == nullptr) return true; if (cur->_col == RED && cur->_parent->_col == RED) { cout << cur->_data << "存在连续的红色节点" << endl; return false; } return Check(cur->_left) && Check(cur->_right); } bool IsBalance() { if (_root && _root->_col == RED) return false; return Check(_root); } void inorder() { _inorder(_root); } void _inorder(node* root) { if (root == nullptr) return; _inorder(root->_left); cout << root->_data << endl; _inorder(root->_right); } node* Find(const T& data) { OFKEY sk; node* cur = _root; node* parent = nullptr; while (cur) { if (sk(cur->_data) > sk(data)) { parent = cur; cur = cur->_left; } else if (sk(cur->_data) < sk(data)) { parent = cur; cur = cur->_right; } else { return cur; } } return nullptr; } private: int treeheight(node* root) { if (root == nullptr) return 0; int leftheight = treeheight(root->_left); int rightheight = treeheight(root->_right); return leftheight > rightheight ? leftheight + 1 : rightheight + 1; } node* _root = nullptr; };
mymap.h
#pragma once #include"rbtree.h" namespace zjw { template<class K,class V> class map { struct MAPOFKEY { const K& operator()(const pair<K,V>&kv) { return kv.first; } }; public: typedef typename rbtree<K, pair< K,V>, MAPOFKEY>::iterator iterator; //typedef typename rbtree<K, pair<const K, V>, MAPOFKEY>::con_iterator con_iterator; iterator begin() { return _st.begin(); } iterator end() { return _st.end(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _st.insert(kv); } V& operator[](const K& key) { pair<iterator,bool> ret=_st.insert(make_pair(key, V())); return ret.first->second; } /* con_iterator begin() const { return _st.begin(); } con_iterator end() const { return _st.end(); }*/ private: rbtree<K, pair< K, V>, MAPOFKEY>_st; }; void test_map() { string arr[] = { "string","string","apple" ,"apple", "blalala","blalala" }; map<string, int>countmap; for (auto& e : arr) { countmap[e]++; } for (auto& kv : countmap) { cout << kv.first << ":" << kv.second << endl; } } //void testmap() //{ // //map< string, int>sr; // //sr.insert(make_pair("b", 1)); // //sr.insert(make_pair("think", 1)); // //sr.insert(make_pair("cool", 1)); // //map< string, int>::con_iterator it = sr.begin(); // //auto it = dic.begin(); // //while (it != sr.end()) // //{ // // it->second += 1; // // // // cout << it->first << ":" << it->second << endl; // // ++it; // //} // //cout << endl; // // //} }
myset.h
#pragma once #include"rbtree.h" namespace zjw { template<class K> class set { struct SETOFKEY { const K& operator()(const K& key) { return key; } }; public: typedef typename rbtree<K, K, SETOFKEY>::iterator iterator; //typedef typename rbtree<K, const K, SETOFKEY>::con_iterator con_iterator; pair<iterator, bool> insert(const K& key) { return _st.insert(key); } iterator begin() { return _st.begin(); } iterator end() { return _st.end(); } /* con_iterator begin() const { return _st.begin(); } con_iterator end() const { return _st.end(); }*/ private: rbtree<K, K, SETOFKEY>_st; }; //void PrintSet(const set<int>& s) //{ // for (auto e : s) // { // //e += 1; // cout << e << endl; // } //} //void test_set() //{ // set<int> s; // s.insert(4); // s.insert(2); // s.insert(5); // s.insert(15); // s.insert(7); // s.insert(1); // s.insert(5); // s.insert(7); // set<int>::iterator it = s.begin(); // while (it != s.end()) // { // // cout << *it << endl; // ++it; // } // PrintSet(s); //} } //set<int>::iterator it = s.begin(); //while (it != s.end()) //{ // //*it += 5; // cout << *it << " "; // ++it; //} //cout << endl; //void testset() //{ // set< int>s; // int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 }; // for (auto e : a) // { // s.insert(e); // } // set<int>::iterator it = s.begin(); // while (it != s.end()) // { // // cout << *it << endl; // ++it; // } //}
