[C++] 深入理解红黑树与代码实现

1. 红黑树的概念

红黑树是一颗二叉搜索树，具备二叉搜索树的所有性质。可以跳转至这篇文章了解二叉搜索树：

C++：深入理解二叉搜索树与代码实现

红黑树在二叉搜索树的基础上还具有以下性质：

1. 只有红色和黑色两种节点
2. 根节点为黑色
3. 任何一条路径都不会出现连续的红色节点
4. 任何一条路径上的黑色节点数量相同

红黑树在二叉搜索树的基础上，通过控制颜色来控制平衡，最长路径不超过最短路径的两倍。

为什么呢？
根据性质4，极端场景下的最短路径全是黑色节点，假设最短路径是b（black）；
由规则2，3可知，极端场景下的最长路径为一黑一红节点间隔组成，那么最长路径为2 * b；
但并不是每一棵红黑树的最长 / 最短路径都符合以上的极端情况，因此，假设任意一条路径长度为x，那么b <= x <= 2 * b。

2. 时间复杂度分析

假设N是红黑树中节点的数量，h是最短路径的长度，那么可以得出2^h -1 <= N < 2^(2*h) -1的结论，由此可以推断出 h 近似为logN。也就是说红黑树增删查改的最坏情况也就是走最长路径即2 * logN，时间复杂度的量级还是O(logN)。
红黑树和AVL树都是通过不同的方式使二叉搜索树尽量平衡，因此他们的效率位于同一档次；且红黑树对平衡的控制没那么严格，因此旋转次数更少，C++的STL中也更多使用红黑树作为底层容器。

3. 红黑树的实现

3.1 红黑树的结构

• 节点：红黑树仅仅在平衡规则部分与AVL树不同，因此红黑树的节点中没有平衡因子，而是用颜色作为枚举值来表示。剩余成员和AVL树相同（父节点指针，左右孩子指针，key / value）。
• 树：红黑树的成员为根节点。

以下是以key / value为例的红黑树框架：

// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现template<classK,classV>structRBTreeNode{// 这里更新控制平衡也要加入parent指针pair<K,V>_kv;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Colour _col;RBTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classK,classV>classRBTree{private:Node*_root=nullptr;typedefRBTreeNode<K,V>Node;public://...};

3.2 红黑树的插入

红黑树的插入逻辑和二叉搜索树相同，即找到一个合适的空位置插入。插入后仅需观察颜色是否符合规则即可：

1. 若为空树，插入的节点为根节点，颜色设置为黑，插入结束。
2. 不为空树，插入的节点颜色设置为红，如果父节点为黑，则符合条件，插入结束；若父节点为红，则不满足规则3（不能出现连续的红色节点），需要向上调整颜色 / 旋转。

对于是否需要旋转，主要观察的是uncle节点，也就是父节点的兄弟节点，如图：

（插入的是x节点，parent节点为6，uncle节点为15，grandparent节点为10）

3.2.1 情况一：仅变色

当uncle节点存在且为红色时，仅需变色即可：

1. 如果grandparent节点的父节点仍然是红色，则一直向上更新；
2. 如果父节点为黑色，则停止更新；
3. 最坏情况是一路向上更新到了根节点，此时需要将根节点变为黑色，停止更新。

3.2.2 情况二：旋转 + 变色

当uncle节点不存在或者为黑色时，需要旋转 + 变色。

我们可以通过uncle节点的状态来推断cur节点的性质：如果uncle节点不存在，则cur节点一定是新增节点；如果uncle节点存在且为黑，则cur节点一定不是新增节点。假设法证明如下：

• 旋转：究竟需要单旋还是双旋，判断条件和AVL树相同。即看cur，parent，grandparent节点是否在一条直线上，如果在，则单旋；否则双旋。
• 变色：要解决连续红色节点的问题，同时还要保证各条路径上的黑色节点数量相同，接下来我们具体情况具体分析。

⭕左单旋：

当g，p，c节点呈一条直线，且p，c均为右孩子节点时，需要进行左单旋。旋转后p，c节点均为红色，为了避免出现连续红色节点，需要将p节点变为黑色，原先左边路径有两个黑色节点，为了保持一致，需要更改g的颜色为红色。

由于之前证明了c节点一定不是新增节点，因此旋转前每条路径的黑色节点个数是符合规则4（任意路径黑色节点数量相同）的，只需要保持原先路径的黑色节点数量不变即可，不需要改变c节点的颜色。

⭕右单旋：

右单旋的场景就是左单旋的水平翻转，变色规则相同：

⭕左右双旋:

当p为g的右孩子节点，c为p的左孩子节点时，需要进行左右双旋。旋转后p，c节点均为红色，为了保证没有连续的红色节点，并且路径上黑色节点数量一致，需要将c节点变为黑色，g节点变为红色。

⭕右左双旋：

右左双旋的场景就是左右双旋的水平翻转，变色规则相同：

红黑树插入代码实现：

boolInsert(constpair<K,V>&kv){//根if(!_root){_root=newNode(kv);_root->_col=BLACK;returntrue;}//非根Node*cur=_root;Node*parent=nullptr;while(cur){if(cur->kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}//新建节点cur=newNode(kv);cur->_col=RED;if(parent->_kv.first<kv.first)//右{parent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;//旋转调整while(parent&&parent->_col=RED){Node*grandfather=parent->_parent;//p在g左if(parent==grandfather->_left){Node*uncle=grandfather->_right;//u存在且为红->变色继续向上处理if(uncle&&uncle->_col==RED){parent->_col=BLACK;uncle->_col=BLACK;grandfather->_col=RED;cur=grandfather;parent=grandfather->_parent;}else//u不存在或为黑{if(cur==parent->_left){RotateR(grandfather);parent->_col=BLACK;grandfather->_col=RED;}else{RotateL(parent);RotateR(grandfather);cur->_col=BLACK;grandfather->_col=RED;}break;}}//p在g右else{Node*uncle=grandfather->_left;//仅变色if(uncle&&uncle->_col==RED){parent->_col=BLACK;uncle->_col=BLACK;grandfather->_col=RED;cur=parent;parent=grandfather;}else//旋转 + 变色{if(cur==parent->_right){RotateL(grandfather);parent->_col=BLACK;grandfather->_col=RED;}else{RotateR(parent);RotateL(grandfather);cur->_col=BLACK;grandfather->_col=RED;}break;}}}//一律设置为黑_root->_col=BLACK;returntrue;}//右旋voidRotateR(Node*pParent){Node*parent=pParent;Node*subL=parent->_left;Node*subLR=subL->_right;//1.parent和subLRparent->_left=subLR;if(subLR){subLR->_parent=parent;}Node*parentParent=parent->_parent;//2.parent和subLparent->_parent=subL;subL->_right=parent;//3.subL和parentParentif(parentParent==nullptr){_root=subL;subL->_parent=nullptr;}else{if(parentParent->_left==parent){parentParent->_left=subL;}else{parentParent->_right=subL;}subL->_parent=parentParent;}}//左旋voidRotateL(Node*pParent){Node*parent=pParent;Node*subR=parent->_right;Node*subRL=subR->_left;//1.parent和subRLparent->_right=subRL;if(subRL){subRL->_parent=parent;}//2.parent和subRNode*parentParent=parent->_parent;parent->_parent=subR;subR->_left=parent;//3.subR和parentParentif(parentParent==nullptr){_root=subR;subR->_parent=nullptr;}else{if(parentParent->_left==parent){parentParent->_left=subR;}else{parentParent->_right=subR;}subR->_parent=parentParent;}}

在写双旋代码的过程中，可以按照以下顺序实现，思路更清晰：

1. parent节点和subRL / subLR节点
2. parent节点和subR / subL节点
3. subR / subL节点和parentParent节点

3.3 红黑树的查找

按照二叉搜索树的规则查找即可，时间复杂度为O(logN)：

//查找Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_kv.first>key){cur=cur->_left;}elseif(cur->_kv.first<key){cur=cur->_right;}else{returncur;}}returnnullptr;}

4. 红黑树的验证

红黑树的验证主要根据四点规则开展，满足了规则就能保证最长路径不超过最短路径的两倍：

1. 规则1无需多言，2可以直接检查根；
2. 规则3前序遍历检查，遇到红⾊结点查孩⼦会涉及分类讨论和是否存在的问题，比较麻烦，因此采用检查⽗节点的颜⾊的方式是否合法；
3. 规则4可以通过前序遍历，并用形参记录根到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。

代码验证：

boolCheck(Node*root,intblackNum,constintrefNum){if(root==nullptr){// 前序遍历走到空时，意味着一条路径走完了//cout << blackNum << endl;if(refNum!=blackNum){cout<<"存在黑色结点的数量不相等的路径"<<endl;returnfalse;}returntrue;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了if(root->_col==RED&&root->_parent->_col==RED){cout<<root->_kv.first<<"存在连续的红色结点"<<endl;returnfalse;}if(root->_col==BLACK){blackNum++;}returnCheck(root->_left,blackNum,refNum)&&Check(root->_right,blackNum,refNum);}boolIsBalance(){if(_root==nullptr)returntrue;if(_root->_col==RED)returnfalse;// 参考值intrefNum=0;Node*cur=_root;while(cur){if(cur->_col==BLACK){++refNum;}cur=cur->_left;}returnCheck(_root,0,refNum);}

// 本期内容就到这里啦，如果对你有帮助，请三连支持！我是青云，我们下期见^_~