关于红黑树的模拟实现，大家不清楚的先去看看博主的博客再来看这篇文章，因为set和map的封装底层都是利用用的红黑树。所以这里不会过多介绍红黑树的相关内容，而更多的是去为了契合STL中的红黑树去进行改造，让封装的set和map能够去复用我们的这份代码

DS进阶：AVL树和红黑树-CSDN博客

      在模拟实现之前，我们肯定要尝试去看看源码是如何实现的！我们会发现其实map和set的底层都是用的红黑树去封装的

      但是你可能会有这样的疑惑，map是kv模型，set是k模型，那难道stl底层封装了两颗红黑树么？？其实并不是的，创建stl的大佬们为了增加代码的复用性，想方设法地想让map和set同时复用一颗红黑树。而解决方法就是通过控制模版参数来区分map和set。

     既然底层是套的红黑树的壳子，我们就要来研究库里面的红黑树究竟通过了什么方法来让map和set都能够复用这份代码。

一、STL中的红黑树

1.1 利用模版参数控制和区分map和set

我们先来看看stl中的红黑树的模版参数，然后进行分析

   接下来我们来看看第三个模版参数的作用究竟是什么

总结：

第1个模版参数是为了帮助我们拿到Key的类型，因为find、erase的接口都是Key类型比较方便

第2个模版参数决定了红黑树节点中存的是key还是pair，以此来区分map和set

第3个模版参数是通过仿函数决定了是拿什么去进行比较，对set来说就是拿key，对pair来说就是拿他的first。

第4个模版参数是具体的比较逻辑，比如说我们传的是指针，但是我们并不想通过指针比而是通过指针解引用的类型比，就可以通过传这个仿函数去控制其比较的行为。

第5个是stl实现的一个堆内存管理器，是为了提高从堆区申请内存的效率，基本上所有的stl容器都会涉及到这个，所以目前暂时不需要太在意！

1.2 stl中的红黑树结构

在该图中，设置了一个哨兵节点，哨兵节点的左指向最小节点5，最大节点的右指向哨兵节点header， 为什么要这样设计呢？？

      STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，

可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位

置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？

能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最

后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

       但是这样虽然方便我们找到第一个节点和最后一个节点，但是每一次都要最最左端和最右端的节点进行和头节点之间的联系，其实比较麻烦，所以下面我们直接改造成不带哨兵节点的红黑树。去模拟实现迭代器。

1.3 改造并模拟实现红黑树的迭代器

但是最最关键的逻辑就是，实现++和--这样迭代器才能跑的起来，下面我们来进行分析

迭代器的封装

<code>template<class T,class Ref,class Ptr>

struct _RBTreeIterator

{

typedef RBTreeNode<T> Node;

typedef _RBTreeIterator<T, Ref, Ptr> Self; //返回一个自身的迭代器

typedef _RBTreeIterator<T, T&, T*> iterator; //用来转化成const迭代器

Node* _node;

_RBTreeIterator(Node* node) //利用节点去构造迭代器

:_node(node)

{}

// 1、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造

// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;

// 支持普通迭代器构造const迭代器的构造函数

_RBTreeIterator(const iterator& it) //隐私类型转化

:_node(it._node)

{}

Ref operator*()

{

return _node->_data; //解引用拿到对应的东西 map拿到pair set拿到key

}

Ptr operator->() //返回对应的指针类型

{

return &operator*();

}

bool operator!=(const Self& s)

{

return _node != s._node;//判断两个迭代器是否相同

}

bool operator==(const Self& s)

{

return _node == s._node;//判断两个迭代器是否相同

}

Self& operator++() //实现迭代器的++

{

if (_node->_right)

{

//如有右不为空，那么就去找到 右子树的最左路节点

Node* subright = _node->_right;

while (subright->_left) subright = subright->_left; //找到最左路节点

_node = subright;

}

else

{

//右为空，沿着到根的路径，找孩子是父亲左的那个祖先

Node* cur = _node;

Node* parent = cur->_parent;

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

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

Self operator++(int) //实现迭代器的后置++

{

Self temp = *this;

++*this;

return temp;

}

Self& operator--() //实现迭代器的-- 右 根 左

{

if (_node->_left)

{

//如有左不为空，那么就去找到 左子树的最右路节点

Node* subright = _node->_left;

while (subright->_right) subright = subright->_right; //找到最左路节点

_node = subright;

}

else

{

//左为空，沿着到根的路径，找孩子是父亲右的那个祖先

Node* cur = _node;

Node* parent = cur->_parent;

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

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

Self operator--(int) //实现迭代器的后置--

{

Self temp = *this;

--*this;

return temp;

}

};

1.4 红黑树实现的全部代码 

enum Colour

{

RED,

BLACK,

};

template<class T> //T表示传的是K还是pair

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 _RBTreeIterator

{

typedef RBTreeNode<T> Node;

typedef _RBTreeIterator<T, Ref, Ptr> Self; //返回一个自身的迭代器

typedef _RBTreeIterator<T, T&, T*> iterator; //用来转化成const迭代器

Node* _node;

_RBTreeIterator(Node* node) //利用节点去构造迭代器

:_node(node)

{}

// 1、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造

// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;

// 支持普通迭代器构造const迭代器的构造函数 为的是隐式类型转化

_RBTreeIterator(const iterator& it) //隐私类型转化 为了set去服务的 因为set的普通迭代器也是const迭代器

:_node(it._node)

{}

Ref operator*()

{

return _node->_data; //解引用拿到对应的东西 map拿到pair set拿到key

}

Ptr operator->() //返回对应的指针类型

{

return &operator*();

}

bool operator!=(const Self& s)

{

return _node != s._node;//判断两个迭代器是否相同

}

bool operator==(const Self& s)

{

return _node == s._node;//判断两个迭代器是否相同

}

Self& operator++() //实现迭代器的++

{

if (_node->_right)

{

//如有右不为空，那么就去找到 右子树的最左路节点

Node* subright = _node->_right;

while (subright->_left) subright = subright->_left; //找到最左路节点

_node = subright;

}

else

{

//右为空，沿着到根的路径，找孩子是父亲左的那个祖先

Node* cur = _node;

Node* parent = cur->_parent;

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

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

Self operator++(int) //实现迭代器的后置++

{

Self temp = *this;

++*this;

return temp;

}

Self& operator--() //实现迭代器的-- 右 根 左

{

if (_node->_left)

{

//如有左不为空，那么就去找到 左子树的最右路节点

Node* subright = _node->_left;

while (subright->_right) subright = subright->_right; //找到最左路节点

_node = subright;

}

else

{

//左为空，沿着到根的路径，找孩子是父亲右的那个祖先

Node* cur = _node;

Node* parent = cur->_parent;

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

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

Self operator--(int) //实现迭代器的后置--

{

Self temp = *this;

--*this;

return temp;

}

};

//K是为了单独拿到key的类型 因为find erase 的接口都是key 而第二个模版参数T决定是这边传的是pair还是key

template<class K, class T,class KeyOfT> //KeyofT 取出来比较的是k 还是pair中的k

class RBTree

{

typedef RBTreeNode<T> Node;

public:

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

typedef _RBTreeIterator<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 begin() const

{

Node* cur = _root;

while (cur && cur->_left) cur = cur->_left;

//找到最左路的节点

return const_iterator(cur);

}

const_iterator end() const

{

return const_iterator(nullptr);

}

~RBTree()

{

_Destroy(_root);

_root = nullptr;

}

iterator Find(const K& key) const

{

Node* cur = _root;

KeyOfT kot;//控制 是在pair中拿key还是直接拿key

while (cur)

{

if (kot(cur->_data) < key) cur = cur->_right; //我比你小，你往右找

else if (kot(cur->_data) > key) cur = cur->_left; //我比你大，你往左找

else return iterator(cur);

}

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);

}

KeyOfT kot;//控制 是在pair中拿key还是直接拿key

//如果不为空树

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

if (kot(cur->_data) > kot(data)) //如果我比你大，到左子树去

{

parent = cur;

cur = cur->_left;

}

else if (kot(cur->_data) < kot(data)) //比你小，你去右子树

{

parent = cur;

cur = cur->_right;

}

else return make_pair(iterator(cur), false);//相等

}

//此时肯定是对应地接在parent的后面

cur = new Node(data);

Node* newnode = cur;//记住新加入的节点

if (kot(parent->_data)> kot(data)) parent->_left = cur; //比父亲小连左边

else parent->_right = cur; //比父亲大连右边

//别忘了父亲指针

cur->_parent = parent;

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

//情况1，如果u为存在且为红

if (grandfather->_left == parent)//如果p是g的左边，u就在右边

{

Node* uncle = grandfather->_right;

//情况1，如果u为存在且为红 p u变黑，g变红 向上调整

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

{

parent->_col = BLACK;

uncle->_col = BLACK;

grandfather->_col = RED;

//继续向上调整

cur = grandfather;

parent = cur->_parent;

}

else //情况2或者情况3， u为黑或者不存在 旋转+变色

{

if (cur == parent->_left) //情况2 右单旋+p变黑 g变红

{

// g

// p u

// c

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else //情况3 右左双旋 c变黑 g变红

{

// g

// p u

// c

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;//情况2和情况3都要跳出循环

}

}

else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边 几乎一样，就是旋转的逻辑不同

{

Node* uncle = grandfather->_left;

//情况1，如果u为存在且为红 p u变黑，g变红 向上调整

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

{

parent->_col = BLACK;

uncle->_col = BLACK;

grandfather->_col = RED;

//继续向上调整

cur = grandfather;

parent = cur->_parent;

}

else//情况2或者情况3， u为黑或者不存在 旋转+变色

{

if (cur == parent->_right) //情况2 左单旋+p变黑 g变红

{

// g

// p u

// c

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else //情况3 左右双旋 c变黑 g变红

{

// g

// p u

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;//情况2和情况3都要跳出循环

}

}

}

_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错

return make_pair(iterator(newnode), true);

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

bool IsBalance()

{

if (_root && _root->_col == RED)

{

cout << "根节点颜色是红色" << endl;

return false;

}

int benchmark = 0;//找到一条路径作为基准值 然后看看其他路径是否相等

Node* cur = _root;

while (cur)

{

if (cur->_col == BLACK)

++benchmark;

cur = cur->_left;

}

// 连续红色节点

return _Check(_root, 0, benchmark);

}

int Height()

{

return _Height(_root);

}

private:

void _Destroy(Node* root)

{

if (root == nullptr) return;

//后序遍历销毁

_Destroy(root->_left);

_Destroy(root->_right);

delete root;

}

int _Height(Node* root)

{

if (root == nullptr)

return 0;

int leftH = _Height(root->_left);

int rightH = _Height(root->_right);

return leftH > rightH ? leftH + 1 : rightH + 1;

}

bool _Check(Node* root, int blackNum, int benchmark)

{

if (root == nullptr)

{

if (benchmark != blackNum)

{

cout << "某条路径黑色节点的数量不相等" << endl;

return false;

}

return true;

}

if (root->_col == BLACK)

{

++blackNum;

}

if (root->_col == RED

&& root->_parent

&& root->_parent->_col == RED)

{

cout << "存在连续的红色节点" << endl;

return false;

}

return _Check(root->_left, blackNum, benchmark)

&& _Check(root->_right, blackNum, benchmark);

}

void _InOrder(Node* root)

{

if (root == nullptr)

{

return;

}

_InOrder(root->_left);

cout << root->_kv.first << " ";

_InOrder(root->_right);

}

//旋转代码和AVL树是一样的，只不过不需要搞平衡因子

void RotateL(Node* parent)

{

//旋转前，先记录对应的节点

Node* subR = parent->_right;

Node* subRL = subR->_left;

Node* ppnode = parent->_parent;//子树的前驱节点

//先让b变成30的边

parent->_right = subRL;

if (subRL) subRL->_parent = parent;

//让30变成60的左边

subR->_left = parent;

parent->_parent = subR;

//此时与前驱节点连接起来 如果前驱节点为空，直接改变根

if (ppnode == nullptr)

{

_root = subR;

_root->_parent = nullptr;

}

//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边

else

{

if (ppnode->_left == parent) ppnode->_left = subR;

else ppnode->_right = subR;

//向上连接

subR->_parent = ppnode;

}

}

void RotateR(Node* parent)

{

//旋转前，先记录对应的节点

Node* subL = parent->_left;

Node* subLR = subL->_right;

Node* ppnode = parent->_parent;//子树的前驱节点

//先让b变成60的左边

parent->_left = subLR;

if (subLR) subLR->_parent = parent;

//让60变成30的右边

subL->_right = parent;

parent->_parent = subL;

//此时与前驱节点连接起来 如果前驱节点为空，直接改变根

if (ppnode == nullptr)

{

_root = subL;

_root->_parent = nullptr;

}

//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边

else

{

if (ppnode->_left == parent) ppnode->_left = subL;

else ppnode->_right = subL;

//向上连接

subL->_parent = ppnode;

}

}

Node* _root = nullptr;

};

二、set的模拟实现

前面我们已经将架子搭好了，这个时候就可以直接开始用了！！

namespace cyx

{

template<class K>

class set

{

struct SetKeyofT

{

const K& operator()(const K& key) //为了跟map保持一致

{

return key;

}

};

public:

typedef typename RBTree< K,K,SetKeyofT>::const_iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题

typedef typename RBTree< K, K, SetKeyofT>::const_iterator const_iterator;

iterator begin()

{

return _t.begin();

}

iterator end()

{

return _t.end();

}

const_iterator begin() const

{

return _t.begin();

}

const_iterator end() const

{

return _t.end();

}

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

{

return _t.Insert(key);

}

private:

RBTree<K, K, SetKeyofT> _t;

};

void test_set1()

{

int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };

set<int> s;

for (auto e : a)

{

s.insert(e);

}

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

while (it != s.end())

{

cout << *it << " ";

//*it = 1;

++it;

}

cout << endl;

for (auto e : s)

{

cout << e << " ";

}

cout << endl;

}

}

注意：

1、在没有实例化的时候 ，编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题

 2、对于insert返回值的改造，本质上是为了map去服务的，set只是配合而已。

三、map的模拟实现

3.1 insert的改装

在stl中 insert的返回值是pair<iterator,bool> 一开始我不太能理解为什么要这么设计。后来我明白了其实本质上为了后面重载[ ]的实现做铺垫。我们可以通过返回值去拿到iterator，并对对应节点的value进行直接修改！！

<code>//先用搜索树的逻辑插入节点，然后再去更新平衡因子。

pair<iterator,bool> Insert(const T& data)

{

//如果为空树，新节点就是根

if (_root == nullptr)

{

_root = new Node(data);

_root->_col = BLACK;

return make_pair(iterator(_root),true);

}

KeyOfT kot;//控制 是在pair中拿key还是直接拿key

//如果不为空树

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

if (kot(cur->_data) > kot(data)) //如果我比你大，到左子树去

{

parent = cur;

cur = cur->_left;

}

else if (kot(cur->_data) < kot(data)) //比你小，你去右子树

{

parent = cur;

cur = cur->_right;

}

else return make_pair(iterator(cur), false);//相等

}

//此时肯定是对应地接在parent的后面

cur = new Node(data);

Node* newnode = cur;//记住新加入的节点

if (kot(parent->_data)> kot(data)) parent->_left = cur; //比父亲小连左边

else parent->_right = cur; //比父亲大连右边

//别忘了父亲指针

cur->_parent = parent;

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

//情况1，如果u为存在且为红

if (grandfather->_left == parent)//如果p是g的左边，u就在右边

{

Node* uncle = grandfather->_right;

//情况1，如果u为存在且为红 p u变黑，g变红 向上调整

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

{

parent->_col = BLACK;

uncle->_col = BLACK;

grandfather->_col = RED;

//继续向上调整

cur = grandfather;

parent = cur->_parent;

}

else //情况2或者情况3， u为黑或者不存在 旋转+变色

{

if (cur == parent->_left) //情况2 右单旋+p变黑 g变红

{

// g

// p u

// c

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else //情况3 右左双旋 c变黑 g变红

{

// g

// p u

// c

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;//情况2和情况3都要跳出循环

}

}

else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边 几乎一样，就是旋转的逻辑不同

{

Node* uncle = grandfather->_left;

//情况1，如果u为存在且为红 p u变黑，g变红 向上调整

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

{

parent->_col = BLACK;

uncle->_col = BLACK;

grandfather->_col = RED;

//继续向上调整

cur = grandfather;

parent = cur->_parent;

}

else//情况2或者情况3， u为黑或者不存在 旋转+变色

{

if (cur == parent->_right) //情况2 左单旋+p变黑 g变红

{

// g

// p u

// c

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else //情况3 左右双旋 c变黑 g变红

{

// g

// p u

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;//情况2和情况3都要跳出循环

}

}

}

_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错

return make_pair(iterator(newnode), true);

}

3.2 重载[ ]的实现

V& operator[](const K& key)

{

pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造

return ret.first->second;

}

通过insert拿到对应位置的迭代器，然后指向其second 这样就可以直接进行修改了。 

3.3 模拟实现的代码

namespace cyx

{

template<class K, class V>

class map

{

struct MapKeyofT

{

const K& operator()(const pair<const K, V>& kv) //为了跟map保持一致

{

return kv.first;

}

};

public:

//模版类型的内嵌类型 加typename

typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题

typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator const_iterator;

iterator begin()

{

return _t.begin();

}

iterator end()

{

return _t.end();

}

const_iterator begin() const

{

return _t.begin();

}

const_iterator end() const

{

return _t.end();

}

V& operator[](const K& key)

{

pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造

return ret.first->second;

}

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

{

return _t.Insert(kv);

}

private:

RBTree<K, pair<const K,V>, MapKeyofT> _t;

};

void test_map()

{

map<string, string> dict;

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

dict.insert(make_pair("left", "左边"));

dict.insert(make_pair("right", "右边"));

dict.insert(make_pair("hello", "你好"));

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

cout << it->first<<endl;

it++;

cout << it->first << endl;

it--;

cout << it->first << endl;

while (it != dict.end())

{

cout << it->first << ":" << it->second << endl;

++it;

}

//for(auto&kv:dict) cout << kv.first << ":" << kv.second << endl;

}

void test_map2()

{

string arr[] = { "西瓜", "梨子", "香蕉", "香蕉", "苹果", "西瓜", "梨子", "香蕉", "西瓜", "西瓜", "苹果", "火龙果", "橙子", "梨子"};

map<string, int> countMap;

for (auto& e : arr)

{

++countMap[e];

}

for (auto& kv : countMap)

{

//kv.second = 2; 控制first不能被修改 或者是key不能被修改

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

}

}

}