RBTree.h

#pragma once#include<iostream>
#include<vector>
using namespace std;enum colar
{   red,black
};template<class T>//有效参数就一个 
struct RBTreeNode
{RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _co(red){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;colar _co;};template<class T,class ref,class ptr>
struct _Tree_iterator
{typedef RBTreeNode<T> Node;typedef _Tree_iterator<T,ref,ptr> self;Node* _cur;_Tree_iterator(Node* tmp):_cur(tmp){}self& operator++(){//将当前节点看作父节点再分析if (_cur->_right == nullptr)//向上返回（前提是父的左孩子）如果是右孩子则表明父亲已经遍历过了{Node* parent = _cur->_parent;while (parent && parent->_right == _cur)//parent可能为空{_cur = parent;parent = _cur->_parent;}//指向parent指向的left等于_cur 或者parent为空（遍历结束）_cur = parent;}else//自己就属于父节点，找右子树的最左节点{Node* tmp = _cur->_right;while (tmp->_left)//tmp不可能为空{tmp = tmp->_left;}_cur = tmp;}return *this;}self& operator--()//相较于operator++而言就是 右子树 根 左子树 的遍历方式{if (_cur->_left == nullptr)//表明当前节点遍历完成，向上返回……{Node* parent = _cur->_parent;while (parent&&parent->_left == _cur){_cur = parent;parent = parent->_parent;}_cur = parent;}else{//找左子树的最右节点_cur = _cur->_left;while (_cur->_right){_cur = _cur->_right;}}return *this;}ref operator*(){return _cur->_data;}ptr operator->(){return &_cur->_data;}bool operator!=(const self& tmp){return _cur != tmp._cur;}
};template<class K, class T,class Com_T>
class RBTree
{typedef RBTreeNode<T> Node;public:typedef _Tree_iterator<T,T&,T*> iterator;typedef _Tree_iterator<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 cbegin()const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator cend()const {return const_iterator(nullptr);}//pair <iterator, bool> insert(const T& data)//data类型取决于T，而T又取决于map和setpair <Node*, bool> insert(const T& data)//data类型取决于T，而T又取决于map和set{Node* newroot = new Node(data);//默认为红if (_root == nullptr){_root = newroot;_root->_co = black;//设为黑return make_pair(newroot,true);}Node* parent = _root, * cur = _root;//插入数据Com_T com;while (1){parent = cur;if (com(cur->_data) > com(data))//这里data的类型可能是pair（不确定）{cur = cur->_left;if (cur == nullptr){parent->_left = newroot;newroot->_parent = parent;break;}}else if (com(cur->_data) < com(data)){cur = cur->_right;if (cur == nullptr){parent->_right = newroot;newroot->_parent = parent;break;}}else{return make_pair(cur, false);//数据相同返回相同数据的迭代器（类似是查找数据）}}//父节点的判断cur = newroot;//当前节点就是新插入的节点while (parent && parent->_co == red)//父亲节点可能不存在{Node* pparent = parent->_parent;//parent为红，不可能是根,一定存在pparentNode* uncle = nullptr;//找叔叔节点if (pparent->_right == parent)uncle = parent->_parent->_left;elseuncle = parent->_parent->_right;if (uncle && uncle->_co == red)//叔叔存在且为红{//变色parent->_co = uncle->_co = black;pparent->_co = red;//祖父节点有可能是根节点//继续向上更新处理cur = pparent;parent = cur->_parent;}else//叔叔节点为空或为黑{//旋转if (pparent->_left == parent && parent->_left == cur){//右单旋RotateR(pparent);parent->_co = black;pparent->_co = red;}else if (pparent->_right == parent && parent->_right == cur){//左单旋RotateL(pparent);parent->_co = black;pparent->_co = red;}else if (pparent->_right == parent && parent->_left == cur){//右左双旋RotateR(parent);RotateL(pparent);cur->_co = black;pparent->_co = red;}else if (pparent->_left == parent && parent->_right == cur){//左右双旋RotateL(parent);RotateR(pparent);cur->_co = black;pparent->_co = red;}break;//旋转之后新的根节点都是黑色}}_root->_co = black;//循环体内很有可能将根节点改为红return make_pair(newroot, true);}void RotateL(Node* parent)//左单旋{Node* cur = parent->_right;Node* curl = cur->_left;Node* pparent = parent->_parent;//提前记录parent->_right = curl;if (curl){curl->_parent = parent;}cur->_left = parent;parent->_parent = cur;//处理pparent与parent的连接if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = cur;elsepparent->_right = cur;cur->_parent = pparent;}}void RotateR(Node* parent)//右单旋{{Node* cur = parent->_left;Node* curr = cur->_right;Node* pparent = parent->_parent;//提前记录parent->_left = curr;if (curr){curr->_parent = parent;}cur->_right = parent;parent->_parent = cur;//处理pparent与parent的连接if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = cur;elsepparent->_right = cur;cur->_parent = pparent;}}}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}// 根节点->当前节点这条路径的黑色节点的数量bool Check(Node* cur, int blacknum, int ref_val){if (cur == nullptr){if (blacknum == ref_val)return true;cout << "每条路径的黑色节点个数不同" << endl;return false;}Node* parent = cur->_parent;if (cur->_co == red && parent->_co == red)//向上判断，向下判断的节点可能为空或其它的。return false;if (cur->_co == black)blacknum++;return Check(cur->_left, blacknum, ref_val) && Check(cur->_right, blacknum, ref_val);}bool Is_balance(){if (_root->_co == red)return false;if (_root == nullptr)return true;//不能出现连续红节点//每条路径黑色节点要保证相同int blacknum = 0;//必须传值，相当于是每个节点都有一个变量表示从根到当前的黑节点个数int ref_val = 0;//参考值,求出任意一条路径中黑色节点数目Node* cur = _root;while (cur){if (cur->_co == black)ref_val++;cur = cur->_left;}return Check(_root, blacknum, ref_val);}private:Node* _root=nullptr;
};

Set.h

#include"RBTree.h"template<class  key>
class set
{
public:struct setCom//仿函数{const key& operator()(const key& k){return k;}};//typedef _Tree_iterator<key> iterator;typedef typename RBTree<key, key, setCom>::const_iterator iterator;typedef typename RBTree<key, key, setCom>::const_iterator const_iterator;//对类模版取内嵌类型，加typename是为了告诉编译器这里是类型pair<iterator,bool> insert(const key& k)//此时pair的第一个参数类型是const_iterator{return _s.insert(k);//insert返回pair<Node*,bool>会构造出pair<iterator,bool>}iterator begin()const{return _s.cbegin();}iterator end()const{return _s.cend();}private:RBTree<key, key, setCom> _s;//封装红黑树
};

Map.h

#include"RBTree.h"template<class  key,class val>
class map
{
public:struct mapCom//仿函数{const key& operator()(const pair<key,val>& p){return p.first;}}; //typedef _Tree_iterator<pair<key,val>> iterator;typedef typename RBTree<key, pair<const key, val>, mapCom>::iterator iterator;typedef typename RBTree<key, pair<const key, val>, mapCom>::const_iterator const_iterator;//对类模版取内嵌类型，加typename是为了告诉编译器这里是类型pair<iterator, bool> insert(const pair<key, val>& kv){return _m.insert(kv);}iterator begin(){return _m.begin();}iterator end(){return _m.end();}const_iterator cbegin()const{return _m.cbegin();}const_iterator cend()const{return _m.cend();}val& operator[](const key& k){pair<key, val> tmp(k, val());//val给缺省值,tmp是创建变量pair<iterator,bool> ret = insert(tmp);//返回插入的节点的pairreturn (ret.first)->second;}private: RBTree<key, pair<const key, val>,mapCom> _m;//封装红黑树(参数类型决定着红黑树的数据类型)
};  

test.cpp（测试）

#include"Map.h"
#include"Set.h"
#include<string>void test_set()
{set<int> s;s.insert(4);s.insert(1);s.insert(2);s.insert(3);s.insert(2);s.insert(0);s.insert(10);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;
}void test_map()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("sort", "xx"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("right", "右边"));map<string, string>::const_iterator it = dict.cbegin();while (it != dict.cend()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;string arr[] = { "㽶", "香蕉","ƻ", "香蕉", "ƻ", "香蕉", "ƻ", "ƻ", "香蕉", "ƻ", "㽶", "ƻ", "㽶" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;
}int main()
{//test_set();test_map();return 0;
}

如有问题欢迎留言！！！