C++红黑树

红黑树的定义

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。
通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路
径⻓出2倍，因⽽是接近平衡的。

红黑树的规则

1.每个结点不是红⾊就是⿊⾊
2. 根结点是⿊⾊的
3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的
红⾊结点。
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点

那么为什么红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍其实我们通过2，3点就可以看出，第一个节点是黑色，从根到任意子树的空节点中间不可能有连续的红节点，所以在极端场景下，我们以bh（black high)来代表一条路径黑色节点的数量，那么最短的路径就是bh（由规则4可知），最长的长度就是2*bh，我们可以通过画图来看看

总结：理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= x <= 2*bh。

红黑树的效率

假设N是红⿊树树中结点数量，h是最短路径的长度 ，那么高度肯定在2^h-1<=N<2^2*h-1这个范围里面
由此可以推到出h约等于logN，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 ，那么时间复杂度还是logN。

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜
⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红
⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的构造

我们先来看看红黑树的节点的结构

enum colour
{RED,BLACK
};
template<class key,class value>
struct RBtreenode
{pair<key, value> _kv;RBtreenode<key, value>* _left;RBtreenode<key, value>* _right;RBtreenode<key, value>* _pre_node;colour col;RBtreenode(const pair<key, value>& input_kv):_left(nullptr),_right(nullptr),_pre_node(nullptr),_kv(input_kv){}
};

这里我们用了一个枚举来枚举颜色，然后用一个pair键值对来存放相应节点的数据，用了三个指针来分别指向左边右边和上面。

红黑树的插入

下面我们以（c：新插入的节点 p：父亲节点 pre：父亲节点的上一个节点（也就是爷爷） u:叔叔节点）
其实插入的核心就是要在搜索二叉树的规则之下在加入红黑树的那4条规则，并且要一直维护这四条规则即可
如果是空树插⼊，新增结点是⿊⾊结点。如果是⾮空树插⼊，新增结点必须红⾊结点，因为⾮空树
插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的

⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束

⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是
红⾊，p为红，pre必为⿊，这三个颜⾊都固定了，关键的变化看u的情况，需要根据u分为以下⼏种情
况分别处理

情况1：变⾊

这种情况是最简单的只用变色

c为红，p为红，pre为⿊，u存在且为红，则将p和u变⿊，pre变红。在把pre当做新的c，继续往上更新。
分析：因为p和u都是红⾊，pre是⿊⾊，把p和u变⿊，左边⼦树路径各增加⼀个⿊⾊结点，pre再变红，相
当于保持pre所在⼦树的⿊⾊结点的数量不变，同时解决了c和p连续红⾊结点的问题，需要继续往上更新
是因为，pre是红⾊，如果pre的⽗亲还是红⾊，那么就还需要继续处理；如果pre的⽗亲是⿊⾊，则处理结束了；如果pre就是整棵树的根，再把pre变回⿊⾊。
只变⾊，不旋转。所以⽆论c是p的左还是右，p是pre的左还是右，都是上⾯的变⾊处理⽅式。
下面我们来画图看看

这种情况就要变色了

我们在画一个复杂的图看看

上面我们只展示了两种具体情况，在实际插入的过程中还会有很多种情况
下面把其中一个子树举例出来说明

再看看下面更全面的

为什么c不是新增节点，因为如果是新增的那么应该是红色，那么黑色节点的数量就对不上了

下面我们来讨论a,b,c,d,e子树hb的数量 首先hb等于0

下面来说说hb 等于1的情况，hb等于1就有很多种情况了
下面这是hb 等于1的子树的四种情况

如果是hb等于2那么情况就有上千万种了，这里就不作过多讲解

情况2单选加变色

c为红，p为红，pre为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则
c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上
来的。
分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解
决问题，需要旋转+变⾊。
我们来画图看看

如果p是pre的左，c是p的左，那么以g为旋转点进⾏右单旋，再把p变⿊，pre变红即可。p变成课这颗树新
的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
反过来p是pre的右c是p的右也是同样的处理方法
下面我们继续来画一个比较复杂且全面的图来看看

然后就是旋转
旋转完成之后的样子

然后变色
这样就旋转完成了

情况3 双旋加变色

这个和单旋不同的是一个是插入在p的左边，双旋的触发条件是插入在p的右边
c为红，p为红，pre为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则
c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，变⾊将c从⿊⾊变成红⾊，更新上来的。

分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解
决问题，需要旋转+变⾊。

如果p是pre的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以pre为旋转点进⾏右单旋，再把c变
⿊，pre变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且
不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
相反方向也是同样的处理方法，反之亦然
我们来画图看看

下面这个就比较简单

来看看比较全面的

关于旋转的详细说明可以看看上一篇avl树
avl树

代码实现

#pragma once
# include<iostream>
# include <utility>
# include<assert.h>
using namespace std;
enum colour
{RED,BLACK
};
template<class key,class value>
struct RBtreenode
{pair<key, value> _kv;RBtreenode<key, value>* _left;RBtreenode<key, value>* _right;RBtreenode<key, value>* _pre_node;colour col;RBtreenode(const pair<key, value>& input_kv):_left(nullptr),_right(nullptr),_pre_node(nullptr),_kv(input_kv){}
};
template<class key, class value>
class RBtree
{typedef RBtreenode<key, value> node;
public:RBtree():_root(nullptr){}bool insert(const pair<key,value>& insert_kv){if(_root == nullptr){_root = new RBtreenode<key, value>(insert_kv);_root->col = BLACK;return true;}node* cur = _root;node* parent = nullptr;while (cur != nullptr){if (cur->_kv.first > insert_kv.first){parent = cur;cur = cur->_left;}else if(cur->_kv.first < insert_kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new node(insert_kv);cur->col = RED;if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_pre_node = parent;//插入完成while (parent != nullptr && parent->col == RED){node* grandfarther = parent->_pre_node;if (grandfarther->_left == parent){node* unclue = grandfarther->_right;if (unclue != nullptr && unclue->col == RED){parent->col = BLACK;unclue->col = BLACK;grandfarther->col = RED;cur = grandfarther;parent = cur->_pre_node;}else{if (parent->_left = cur){//旋转rotetR(grandfarther);parent->col = BLACK;grandfarther->col = RED;}else{rotetL(parent);rotetR(grandfarther);cur->col = BLACK;grandfarther->col = RED;}break;}}else{node* unclue = grandfarther->_left;if (unclue != nullptr && unclue->col == RED){parent->col = BLACK;unclue->col = BLACK;grandfarther->col = RED;cur = grandfarther;parent = cur->_pre_node;}else{if (parent->_right == cur){rotetL(grandfarther);grandfarther->col = RED;parent->col = BLACK;}else{rotetR(parent);rotetL(grandfarther);grandfarther->col = RED;cur->col = BLACK;}break;}}}_root->col = BLACK;return true;}void rotetR(node* parent){node* subl = parent->_left;node* sublr = subl->_right;node* pparent = parent->_pre_node;parent->_left = sublr;if (sublr != nullptr){sublr->_pre_node = parent;}parent->_pre_node = subl;subl->_right = parent;if (parent == _root){_root = subl;subl->_pre_node = nullptr;}else{if (pparent->_left == parent){pparent->_left = subl;}else{pparent->_right = subl;}subl->_pre_node = pparent;}}void rotetL( node* parent){node* subr = parent->_right;node* subrl = subr->_left;node* pparent = parent->_pre_node;parent->_right = subrl;if (subrl != nullptr){subrl->_pre_node = parent;}parent->_pre_node = subr;subr->_left = parent;if (parent == _root){_root = subr;subr->_pre_node = nullptr;}else{if (pparent->_left == parent){pparent->_left = subr;}else{pparent->_right = subr;}subr->_pre_node = pparent;}}这里我们可以来说说这个检查是否是红黑树的代码,首先检查是用递归来检查的，我们可以根据红黑树的定义再从根节点到任意空节点的黑色节点都是相同的，我们可以首先选取一段来计算黑色节点有多少个，然后以这个取一个定值去依次比较根据递归的性质来进行比较bool isRBtree(){node* cur = _root;参考值 int lefcount = 0;if (_root == nullptr){return true;}if (_root->col == RED){return false;}while (cur != nullptr){if (cur->col == BLACK){lefcount++;}cur = cur->_left;}return cheak(_root, 0, lefcount);}void _inoder_root(){inoder(_root);}private:node* _root;void inoder(node* root){if (root == nullptr){return;}inoder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;inoder(root->_right);}bool cheak(node* root, int blacknum, const int lefcount){if (root == nullptr){if (blacknum != lefcount){cout << "存在不相等的黑色节点" << endl;return false;}return true;}检查父母的颜色比检查孩子要轻松多了，孩子有两个，且有可能是空的if (root->col == RED && root->_pre_node->col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->col == BLACK){blacknum++;}return cheak(root->_left, blacknum, lefcount) && cheak(root->_right, blacknum, lefcount);}
};

完