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和set
pair <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为红，不可能是根,一定存在pparent
Node* uncle = nullptr;
//找叔叔节点
if (pparent->_right == parent)
uncle = parent->_parent->_left;
else
uncle = 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;
else
pparent->_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;
else
pparent->_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);//返回插入的节点的pair
return (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;
}如有问题欢迎留言！！！
