1.对红黑树进行改造

1.1treenode模板参数改变

之前构建treenode模板参数传的是class k,class v(set为k，k；map是k，v），现在直接用T代替

<code>template<class T> //这里直接传了T作为模板参数，T可能是pair<k,t>,也可能是k

struct RBTtreenode

{

RBTtreenode<T>* _left;

RBTtreenode<T>* _right;

RBTtreenode<T>* _parent;

//pair<K, V> kv;

T data;

color col;

RBTtreenode(const T& _data)

:_left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, data(_data)

, col(RED)

{}

};

2.构建红黑树的迭代器 

因为要构建const_iterator（不可修改内容） 和iterator（可修改内容）所以需要三个模板参数

//<T,T&,T*> iterator;//普通迭代器

//<T, const T&, const T*> const_iterator;//指向的东西不能改变

template<class T,class Ref,class Ptr>

 iterator内存的是node*类型的数据！！！！

2.1 重载operator*()   (set)

因为set传模板参数只传K，没有V，data类型是K，

所以用*直接取得data即可

<code>Ref operator*()

{

return _node->data;

}

 2.2 重载operator->()   (map)

因为map模板参数传的是K，pair<const K，T>,data类型是pair<const K，T>，

想取到K，则需要传回&data,再用->first取得K

Ptr operator->()

{

return &_node->data;

}

 2.3operator++()与operator--()

 这里以operator++（）做解释：

分三种情况：

1.如果右子树不为空，则找到右子树的最左节点

2.//如果右子树为空，且cur是parent的右子树，则先parent回溯至parent->_parent,再_node变为parent

3.//如果右子树为空，且cur是parent的左子树，则_node变为parent

iterator& operator++()

{

if (_node->_right)

{

//如果右子树不为空，则找到右子树的最左节点

node* cur = _node->_right;

while (cur && cur->_left)

{

cur = cur->_left;

}

_node = cur;

}

else

{

//如果右子树为空，且cur是parent的右子树，则先parent回溯至parent->_parent,再_node变为parent

//如果右子树为空，且cur是parent的左子树，则_node变为parent

node* cur = _node;

node* parent = cur->_parent;

while (parent && cur == parent->_right)

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

2.4.begin()&&end() 

iterator begin()

{

node* flag = root;

while (flag&&flag->_left)//flag可能为nullptr

{

flag = flag->_left;

}

return iterator(flag);

}

iterator end()

{

return iterator(nullptr); //end用nullptr去构造！！！！！！！！

}

const_iterator begin() const

{

node* flag = root;

while (flag && flag->_left)//flag可能为nullptr

{

flag = flag->_left;

}

return const_iterator(flag);

}

const_iterator end() const

{

return const_iterator(nullptr); //end用nullptr去构造！！！！！！！！

}

3.set.h封装

https://cplusplus.com/reference/set/set/?kw=set

#include"rbt.h"

namespace zone

{

template<class K>

class set

{

public:

struct setkeyoft //仿函数，用来取出红黑树节点data中的key

{

const K& operator()(const K& key)

{

return key;

}

};

//set这里的迭代器本质都是const_iterator，因为k要求无法修改

typedef typename RBTtree<K, K, setkeyoft>::const_iterator iterator;//记得要使用typename告诉编译器RBTtree<K, K, setkeyoft>::iterator这个是类型，不是函数

typedef typename RBTtree<K, K, setkeyoft>::const_iterator const_iterator;

iterator begin()const

{

return it.begin();

}

iterator end()const

{

return it.end();

}

pair<iterator,bool> insert(const K& key)

{

return it.insert(key);

}

void inorder()

{

it.inorder();

}

private:

RBTtree<K,K,setkeyoft> it;

};

}

3.1 仿函数setkeyoft

仿函数，用来取出红黑树节点data中的key，用于insert函数！！！！

3.2 iterator和const_iterator

//set这里的迭代器本质都是const_iterator，因为k要求无法修改

        typedef typename RBTtree<K, K, setkeyoft>::const_iterator iterator;

        typedef typename RBTtree<K, K, setkeyoft>::const_iterator const_iterator;

4.map.h封装 

https://cplusplus.com/reference/map/map/?kw=map

#include"rbt.h"

namespace zone

{

template<class K,class T>

class map

{

public:

struct setkeyoft

{

const K& operator()(const pair<K, T>& key)

{

return key.first;

}

};

//map这里的迭代器则使用的是iterator，因为k要求无法修改，但v可以修改，所以可以直接初始化时用pair<const K, T>

typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::iterator iterator;

typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::const_iterator const_iterator;

pair<iterator, bool> insert(const pair<K, T>& key)

{

return it.insert(key);

}

T& operator[](const K& key)

{

pair<iterator, bool>ret = insert(make_pair(key,T()));//insert返回一个pair，first是iterator，second是bool类型

return ret.first->second;

}

iterator begin()

{

return it.begin();

}

iterator end()

{

return it.end();

}

void inorder()

{

it.inorder();

}

private:

RBTtree<K,pair<const K,T>, setkeyoft> it;

};

}

5.insert函数 ！！！！！！！

RBT.h里insert函数的返回值是 pair<node*, bool>

但封装过后的map.h,set.h里

pair<iterator,bool> insert(const K& key)

{

return it.insert(key);

}

 返回值是pair<iterator,bool>

可见 pair<node*, bool>和pair<iterator(这里的iterator已经重命名了，本质是const_iteratir),bool>并不是同一类型，该如何解决呢？

1.如果T1和U类型一致，T2和V类型一致，那么就是拷贝构造！！！

2.如果不一致，也可以进行普通构造，前提是有可以用first来构建T1的函数！！！！！

回到刚才的问题：

可见 pair<node*, bool>和pair<iterator(这里的iterator已经重命名了，本质是const_iteratir),bool>并不是同一类型，该如何解决呢？

bool类型肯定可以用bool类型初始化，

iterator可以用node*进行初始化吗？

答案是可以的

<code>treeiterator(node* it)

:_node(it)

{}

相当于使用了隐式类型转换

 6.杂谈

类比指针：

1.iterator 可修改指向的数据，也可改变自身

2.const iterator  可修改指向的数据，但不可改变自身

3.const_iterator 不可修改指向的数据，但能改变自身

 7.代码全览

RBT.h

<code>#include<iostream>

using namespace std;

enum color

{

RED,

BLACK

}; //列举color的各种可能情况

template<class T> //这里直接传了T作为模板参数，T可能是pair<k,t>,也可能是k

struct RBTtreenode

{

RBTtreenode<T>* _left;

RBTtreenode<T>* _right;

RBTtreenode<T>* _parent;

//pair<K, V> kv;

T data;

color col;

RBTtreenode(const T& _data)

:_left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, data(_data)

, col(RED)

{}

};

//<T,T&,T*> iterator;//普通迭代器

//<T, const T&, const T*> const_iterator;//指向的东西不能改变：const_iterator,本身不能改变：const iterator

template<class T,class Ref,class Ptr>

struct treeiterator

{

typedef RBTtreenode<T> node;

typedef treeiterator<T,Ref,Ptr> iterator;

node* _node;

treeiterator(node* it)

:_node(it)

{}

Ref operator*()

{

return _node->data;

}

Ptr operator->()

{

return &_node->data;

}

iterator& operator++()

{

if (_node->_right)

{

//如果右子树不为空，则找到右子树的最左节点

node* cur = _node->_right;

while (cur && cur->_left)

{

cur = cur->_left;

}

_node = cur;

}

else

{

//如果右子树为空，且cur是parent的右子树，则先parent回溯至parent->_parent,再_node变为parent

//如果右子树为空，且cur是parent的左子树，则_node变为parent

node* cur = _node;

node* parent = cur->_parent;

while (parent && cur == parent->_right)

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

iterator& 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->_left)

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

bool operator!=(const iterator&s)

{

return _node != s._node;

}

};

template<class K, class T,class keyoft>

class RBTtree

{

public:

typedef treeiterator<T,T&,T*> iterator;

typedef treeiterator<T, const T&, const T*> const_iterator;//指向的东西不能改变

typedef RBTtreenode<T> node;

iterator begin()

{

node* flag = root;

while (flag&&flag->_left)//flag可能为nullptr

{

flag = flag->_left;

}

return iterator(flag);

}

iterator end()

{

return iterator(nullptr); //end用nullptr去构造！！！！！！！！

}

const_iterator begin() const

{

node* flag = root;

while (flag && flag->_left)//flag可能为nullptr

{

flag = flag->_left;

}

return const_iterator(flag);

}

const_iterator end() const

{

return const_iterator(nullptr); //end用nullptr去构造！！！！！！！！

}

pair<node*, bool> insert(const T& _data)//！！！！！！！！！

{

if (root == nullptr)

{

root = new node(_data);

root->col = BLACK;//规定根必须是黑的

return make_pair(root, true);

}

node* parent = nullptr; //比bst多了一个parent

node* cur = root;

keyoft type;//取出data的K类型的数据

while (cur)

{

parent = cur;

if (type(cur->data) < type(_data)) //这里取出key再进行比较

{

cur = cur->_right;

}

else if (type(cur->data) > type(_data))

{

cur = cur->_left;

}

else

{

return make_pair(cur,false);

}

}

cur = new node(_data);

cur->col = RED;//因为如果插入黑色的会使很多节点的一条路径上的黑色节点增多（相当于得罪了所有人），而插入红色则有可能只得罪父亲（如果父亲是红色的话）

if (type(parent->data) < type(_data))

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

node* newnode = cur;

//开始调整

while (parent && parent->col == RED)//parent为黑不需要调整,如果cur变成root，parent就不存在退出循环

{

node* grandparent = parent->_parent;//祖父一定存在，因为只有根节点是没有祖父的，而根节点一定是黑色的

if (parent == grandparent->_left)

{

// g

// p u

node* uncle = grandparent->_right; //父亲在左则叔叔在右

if (uncle && uncle->col == RED) //情况一.如果叔叔存在且为红色

{

//变色

parent->col = uncle->col = BLACK;

grandparent->col = RED;

//重置cur，parent，继续向上处理

cur = grandparent;//变为祖父

parent = cur->_parent;

}

else //叔叔不存在或为黑色，旋转加变色

{

// g

// p

// c

if (cur == parent->_left) //情况二.单旋

{

rotateR(grandparent);

parent->col = BLACK;

grandparent->col = RED;

}

// g

// p

// c

else //情况三.cur==parent->_right,双旋

{

rotateL(parent);//经历一次左旋后变成情况二!!!!!!!!!!!(cur和parent换位置）

rotateR(grandparent);

cur->col = BLACK;

grandparent->col = RED;

}

break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent

}

}

else

{

// g

// u p

//

node* uncle = grandparent->_left; //父亲在右则叔叔在左

if (uncle && uncle->col == RED)

{

parent->col = uncle->col = BLACK;

grandparent->col = RED;

//

cur = grandparent;

parent = cur->_parent;

}

else

{

// g

// u p

// c

if (cur == parent->_right)

{

rotateL(grandparent);

parent->col = BLACK;

grandparent->col = RED;

}

else

{

// g

// u p

// c

rotateR(parent);

rotateL(grandparent);

cur->col = BLACK;

grandparent->col = RED;

}

break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent

}

}

}

//1.如果parent和uncle都为RED，则可以一起变黑

// 2.parent为黑不处理

// 3.uncle为黑或不存在，parent为红，旋转+变色

root->col = BLACK;//最后以防万一让根变为黑

return make_pair(newnode, true);

}

void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）// 1.右右

{

node* subr = parent->_right;

node* subrl = subr->_left;

parent->_right = subrl;

subr->_left = parent;

node* ppnode = parent->_parent;

parent->_parent = subr;

if (subrl) //subrl可能为空！！！！！！！

{

subrl->_parent = parent;

}

if (parent == root) //即如果parent->_parent==nullptr

{

root = subr;

subr->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subr;

}

else if (ppnode->_right == parent)

{

ppnode->_right = subr;

}

subr->_parent = ppnode;

}

}

void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）// 2.左左

{

node* subl = parent->_left;

node* sublr = subl->_right;

parent->_left = sublr;

if (sublr) //sublr可能为空！！！！！！！

sublr->_parent = parent;

node* ppnode = parent->_parent;

subl->_right = parent;

parent->_parent = subl;

if (root == parent)

{

root = subl;

subl->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = subl;

}

else if (ppnode->_right == parent)

{

ppnode->_right = subl;

}

subl->_parent = ppnode;

}

}

void inorder()

{

_inorder(root);

}

void _inorder(node* root)

{

keyoft type;

if (root == nullptr)

return;

_inorder(root->_left);

cout << type(root->data)<< " ";

_inorder(root->_right);

}

bool check(node* it, int blacknum, int flag)

{

if (it == nullptr)

{

if (blacknum == flag)

return true;

else

return false;

}

else if (it->col == RED && it->_parent->col == RED)//十分巧妙，因为孩子的情况有很多，但父亲不是红就是黑，所以判断父亲更合适

return false;

else if (it->col == BLACK)

blacknum++;

return check(it->_left, blacknum, flag) && check(it->_right, blacknum, flag);

}

bool isbalance()

{

return _isbalance(root);

}

bool _isbalance(node* root)

{

if (root == nullptr)

return true;

else if (root->col == RED)

return false;

int blacknum = 0;

int flag = 0;

node* k = root;

while (k)

{

if (k->col == BLACK)

flag++;

k = k->_left;//这里十分巧妙，因为如果为红黑树，从某一节点到空的所有路径上的黑节点数量是一致的，所以可以先随便选一条路径，算出这一条路径上的黑节点数作为基准值，在由递归去和其他路径比较

}

return check(root, blacknum, flag);

}

private:

node* root = nullptr;

};

myset.h

#include"rbt.h"

namespace zone

{

template<class K>

class set

{

public:

struct setkeyoft //仿函数，用来取出红黑树节点data中的key

{

const K& operator()(const K& key)

{

return key;

}

};

//set这里的迭代器本质都是const_iterator，因为k要求无法修改

typedef typename RBTtree<K, K, setkeyoft>::const_iterator iterator;//记得要使用typename告诉编译器RBTtree<K, K, setkeyoft>::iterator这个是类型，不是函数

typedef typename RBTtree<K, K, setkeyoft>::const_iterator const_iterator;

iterator begin()const

{

return it.begin();

}

iterator end()const

{

return it.end();

}

pair<iterator,bool> insert(const K& key)

{

return it.insert(key);

}

void inorder()

{

it.inorder();

}

private:

RBTtree<K,K,setkeyoft> it;

};

}

mymap.h

#include"rbt.h"

namespace zone

{

template<class K,class T>

class map

{

public:

struct setkeyoft

{

const K& operator()(const pair<K, T>& key)

{

return key.first;

}

};

//map这里的迭代器则使用的是iterator，因为k要求无法修改，但v可以修改，所以可以直接初始化时用pair<const K, T>

typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::iterator iterator;

typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::const_iterator const_iterator;

pair<iterator, bool> insert(const pair<K, T>& key)

{

return it.insert(key);

}

T& operator[](const K& key)

{

pair<iterator, bool>ret = insert(make_pair(key,T()));//insert返回一个pair，first是iterator，second是bool类型

return ret.first->second;

}

iterator begin()

{

return it.begin();

}

iterator end()

{

return it.end();

}

void inorder()

{

it.inorder();

}

private:

RBTtree<K,pair<const K,T>, setkeyoft> it;

};

}

test.cpp

#include<iostream>

#include<vector>

#include<string>

using namespace std;

#include"myset.h"

#include"mymap.h"

void test1()

{

zone::set<int> it;

it.insert(1);

it.insert(3);

it.insert(5);

it.insert(2);

it.insert(4);

zone::set<int>::iterator arr = it.begin();

while (arr!=it.end() )

{

cout << *arr << " ";

++arr;

}

//it.inorder();

}

void test2()

{

zone::map<string,string> it;

it.insert(make_pair("sort","排序"));

it.insert(make_pair("right", "右"));

it.insert(make_pair("left", "左"));

it.insert(make_pair("middle", "中"));

zone::map<string,string>::iterator arr = it.begin();

while (arr != it.end())

{

arr->second += 'x';//map的v可修改

cout << arr->first << " ";

++arr;

}

//it.inorder();

}

void test3()

{

string arr[] = { "香蕉","苹果","西瓜","苹果","苹果","西瓜","苹果"};

zone::map<string, int> it;

for (auto e : arr)

{

it[e]++;

}

for (auto k : it)

{

++k.second;

cout << k.first << ":" << k.second << endl;

}

}

int main()

{

test3();

return 0;

}