目录
一.红黑树的改造
二.模拟实现set
三.模拟实现map
四.整体代码
1.RBTree.h
2.MySet.h
3.MyMap.h
4.Test.cpp
一.红黑树的改造
map和set底层都是通过红黑树实现的,但是set中存放是key,map中为key,value,我们不会去写两棵红黑树来实现他们,因为代码会重复,我们需要对红黑树内部进行改造
template<class K,class T,class KOfT>为了可以同时处理set和map,我们传一个T过去,是set的时候为key,map为pair<K,V>
对于set和map他们的排序,set可以直接通过key来排序,而map的排序规则与set不同,先比较key,如果相同比较value,所以我们传一个KOfT
struct SetKeyOfT{const K& operator()(const K& k){return k;}};struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};通过KOfT来分别处理set和map的排序
红黑树的迭代器
iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}operator++与operator--
Self& operator++(){//如果右不为空,中序的下一个就是右子树的最左节点//如果右为空,表示_node所在子树访问完,下一个节点在他的祖先中找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 = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){//与++基本相反return *this;}set和map的实现都是对红黑树的复用,所以理解红黑树是关键
二.模拟实现set
set的实现通过对红黑树的复用即可完成
template<class K>class set{struct SetKeyOfT{const K& operator()(const K& k){return k;}};public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> Insert(const K& k){return _t.Insert(k);}private:RBTree<K, K, SetKeyOfT> _t;};三.模拟实现map
template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> Insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};四.整体代码
1.RBTree.h
#pragma onceenum Colour{BLACK,RED,};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 Ref, class Ptr>struct __TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node) :_node(node) { }Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//如果右不为空,中序的下一个就是右子树的最左节点//如果右为空,表示_node所在子树访问完,下一个节点在他的祖先中找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 = cur->_parent;parent = parent->_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;}};template<class K,class T,class KOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T, T&, T*> iterator;typedef __TreeIterator<T, const T&, const T*> const_terator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}pair<iterator, bool> Insert(const T& data){//按照搜索树的规则插入if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}KOfT koft;Node* parent = nullptr;Node* cur = _root;while (cur){if (koft(cur->_data) < koft(data)){parent = cur;cur = cur->_right;}else if (koft(cur->_data) > koft(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);Node* newnode = cur;if (koft(parent->_data) < koft(cur->_data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//新增节点红的cur->_col = RED;while (parent && parent->_col == RED){//红黑树的关键看叔叔Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//情况一:uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}//情况二或情况三:uncle不存在或者uncle存在且为黑else{//情况三:双旋->变为单旋if (cur == parent->_right){RotateL(parent);swap(parent, cur);}//第二种情况(有可能为第三种情况变化而来)RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}else{Node* uncle = grandfather->_left;//情况一:uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}//情况二或情况三:uncle不存在或者uncle存在且为黑else{//情况三:双旋->变为单旋if (cur == parent->_left){RotateR(parent);swap(parent, cur);}//第二种情况(有可能为第三种情况变化而来)RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;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;//原来parent为根,现在subR为根//parent为树的子树,sunR替代parentif (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_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 (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}bool IsValidRBTree(){Node* pRoot = _root;// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_col){cout << "违反红黑树性质：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0; Node* pCur = pRoot;while (pCur){if (BLACK == pCur->_col)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);}bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount){//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == pRoot->_col)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && RED == pParent->_col && RED == pRoot->_col){cout << "违反性质：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);}iterator Find(const K& data){KOfT koft;Node* cur = _root;while (cur){if (koft(cur->_data) < koft(data)){cur = cur->_right;}else if (koft(cur->_data) > koft(data)){cur = cur->_left;}else{return iterator(cur);}}return iterator(nullptr);}private:Node* _root = nullptr;};2.MySet.h
#pragma once#include"RBTree.h"namespace wzyl{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& k){return k;}};public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> Insert(const K& k){return _t.Insert(k);}private:RBTree<K, K, SetKeyOfT> _t;};void test_set(){set<int> s;s.Insert(1);s.Insert(3);s.Insert(2);s.Insert(4);s.Insert(5);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}}3.MyMap.h
#pragma once#include"RBTree.h"namespace wzyl{template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> Insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};void test_map(){map<int, int> m;m.Insert(make_pair(1, 1));m.Insert(make_pair(2, 2));m.Insert(make_pair(4, 4));m.Insert(make_pair(3, 3));m.Insert(make_pair(5, 5));map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (auto e : m){cout << e.first << ":" << e.second << endl;}cout << endl;string strs[] = { "西瓜","苹果" ,"西瓜", "葡萄", "西瓜", "橘子", "西瓜", "苹果", "西瓜", "橘子" };map<string, int> countmap;for (auto& str : strs){countmap[str]++;}for (auto kv : countmap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}}4.Test.cpp
#include<iostream>using namespace std;#include"MyMap.h"#include"MySet.h"int main(){wzyl::test_map();wzyl::test_set();return 0;}