C++ RBTree红黑树的性质与实现方法是什么

免费教程 2024年05月09日 9:58

这篇文章主要讲解了“C++RBTree红黑树的性质与实现方法是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C++RBTree红黑树的性质与实现方法是什么”吧！

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是平衡的。（既最长路径长度不超过最短路径长度的 2 倍）

ps:树的路径是从根节点走到空节点（此处为NIL 节点）才算一条路径

二、红黑树的性质

每个结点不是红色就是黑色

根结点是黑色的

如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的红色结点）

对于每个结点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

每个叶子结点都是黑色的（此处的叶子结点指的是空节点,NIL节点），如果是空树，空节点也是黑色，符合第一个性质

理解最长路径长度不超过最短路径长度的 2 倍：

根据第三个性质：红黑树不会出现连续的红色结点，根据第四个性质：从每个结点到所有后代结点的路径上包含相同数目的黑色结点。

极端场景：最短路径上全黑，一条路径黑色节点的数量，最长路径上是一黑一红相间的路径

三、红黑树节点的定义

三叉链结构，对比AVL数节点的定义，把平衡因子替换成节点颜色，采用枚举的方式：

//结点颜色enumColor{RED,BLACK,};template<classK,classV>structRBTreeNode{pair<K,V>_kv;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Color_col;RBTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};

这里可以清楚的看到，构造结点时默认设置为红色,问题来了：

如果插入的是黑色结点那就是不符合第四个性质（路径上均包含相同的黑色结点），此时我们必须要去进行维护每条路径的黑色结点

如果插入的是红色结点那就是不符合第三个性质（没有出现连续的红色结点），但是我们并不一定需要调整，如果根刚好为黑色，就不需要进行调整。

所以如果插入为红色结点，不一定会破坏结构，但是如果插入黑色结点我们就必须去进行维护了

四、红黑树的插入

红黑树插入的操作部分和AVL树的插入一样：

找到待插入位置

将待插入结点插入到树中

调整：若插入结点的父结点是红色的，我们就需要对红黑树进行调整

前两步大差不差

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

关键在于对红黑树进行调整：为了能够展示出各种情况，这里有一个基本的模型：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红 :

cur为红，p为红，g为黑，u存在且为红

关键看u结点，根结点的颜色为黑色，不能有连续的红色结点，所以上面的情况已经出现连续的红色结点了，此时我们需要进行调整：

把p结点改为黑色，同时把u结点也改为黑色（符合性质四：每条路径上的黑色节点数量相同），最后在把g结点改为红色；如果g是子树的话，g一定会有双亲，为了维持每条路径上黑色节点的数量，g必须变红，不然会多出一个黑色节点，在把g结点当做cur结点继续往上调整，当g为根结点时，在把g置为黑色：

代码实现：

while(parent&&parent->_col==RED){Node*grandfater=parent->_parent;if(parent==grandfater->_left){Node*uncle=grandfater->_right;//情况一：u存在且为红if(uncle&&uncle->_col==RED){parent->_col=uncle->_col=BLACK;grandfater->_col=RED;cur=grandfater;parent=cur->_parent;}else//其他情况{}}else//parent==grandfater->_right{Node*uncle=grandfater->_left;if(uncle&&uncle->_col==RED){parent->_col=uncle->_col=BLACK;grandfater->_col=RED;cur=grandfater;parent=cur->_parent;}else{}}}_root->_col=BLACK;

情况二：cur为红，p为红，g为黑，u不存在/u为黑，gpc在同一侧：

此时u的情况：

如果u结点不存在，则cur一定是新增结点，因为如果cur不是新增结点：则cur和p一定有一个节点时黑色，就不满足每条路径都有相同的黑色结点的性质。

如果u结点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色，在其子树调整过程中变为了红色

如果p为g的左孩子，cur为p的左孩子，则进行右单旋转；

如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，

同时，p、g变色–p变黑，g变红

以下情况：u不存在，cur为新增节点，进行右单旋：

以下情况：u结点存在且为黑：

情况三: cur为红，p为红，g为黑，u不存在/u为黑，gpc不在同一侧:

这时候我们就需要进行双旋了：

p为g的左孩子，cur为p的右孩子，对p做左单旋转；

p为g的右孩子，cur为p的左孩子，对p做右单旋转; 旋转之后则转换成了情况2，在继续进行调整即可

五、代码实现

送上源码：

#pragmaonce#include<iostream>#include<assert.h>#include<time.h>usingnamespacestd;enumColor{RED,BLACK,};template<classK,classV>structRBTreeNode{pair<K,V>_kv;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Color_col;RBTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};template<classK,classV>classRBTree{typedefRBTreeNode<K,V>Node;public:boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);_root->_col=BLACK;returntrue;}Node*parent=nullptr;Node*cur=_root;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;cur->_parent=parent;}else{parent->_left=cur;cur->_parent=parent;}while(parent&&parent->_col==RED){Node*grandfater=parent->_parent;if(parent==grandfater->_left){Node*uncle=grandfater->_right;//情况一：u存在且为红if(uncle&&uncle->_col==RED){parent->_col=uncle->_col=BLACK;grandfater->_col=RED;//向上调整cur=grandfater;parent=cur->_parent;}else{//情况2if(cur==parent->_left){RotateR(grandfater);parent->_col=BLACK;grandfater->_col=RED;}//情况3else{//g//p//cRotateL(parent);RotateR(grandfater);cur->_col=BLACK;grandfater->_col=RED;}break;}}else//parent==grandfater->_right{Node*uncle=grandfater->_left;//情况1：u存在且为红色if(uncle&&uncle->_col==RED){uncle->_col=parent->_col=BLACK;grandfater->_col=RED;//向上调整cur=grandfater;parent=cur->_parent;}else{//情况2：u不存在/u存在为黑色//g//p//cif(cur==parent->_right){RotateL(grandfater);grandfater->_col=RED;parent->_col=BLACK;}//情况3//g//p//celse{RotateR(parent);RotateL(grandfater);cur->_col=BLACK;grandfater->_col=RED;}break;}}}//根变黑_root->_col=BLACK;returntrue;}voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==nullptr){_root=subR;_root->_parent=nullptr;}else{if(ppNode->_left==parent){ppNode->_left=subR;}else{ppNode->_right=subR;}subR->_parent=ppNode;}}voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*ppNode=parent->_parent;parent->_parent=subL;subL->_right=parent;if(ppNode==nullptr){_root=subL;_root->_parent=nullptr;}else{if(ppNode->_left==parent){ppNode->_left=subL;}else{ppNode->_right=subL;}subL->_parent=ppNode;}}voidInOrder(){_InOrder(_root);}void_InOrder(Node*root){if(root==nullptr)return;_InOrder(root->_left);cout<<root->_kv.first<<":"<<root->_kv.second<<endl;_InOrder(root->_right);}boolCheck(Node*root,intblackNum,intref){if(root==nullptr){//cout<<blackNum<<endl;if(blackNum!=ref){cout<<"违反规则：本条路径的黑色结点的数量根最左路径不相等"<<endl;returnfalse;}returntrue;}if(root->_col==RED&&root->_parent->_col==RED){cout<<"违反规则：出现连续的红色结点"<<endl;returnfalse;}if(root->_col==BLACK){++blackNum;}returnCheck(root->_left,blackNum,ref)&&Check(root->_right,blackNum,ref);}boolIsBalance(){if(_root==nullptr){returntrue;}if(_root->_col!=BLACK){returnfalse;}intref=0;Node*left=_root;while(left){if(left->_col==BLACK){++ref;}left=left->_left;}returnCheck(_root,0,ref);}private:Node*_root=nullptr;};voidTestRBTree1(){//inta[]={8,3,1,10,6,4,7,14,13};inta[]={16,3,7,11,9,26,18,14,15};//inta[]={4,2,6,1,3,5,15,7,16,14};RBTree<int,int>t;for(autoe:a){t.Insert(make_pair(e,e));}t.InOrder();cout<<t.IsBalance()<<endl;}voidTestRBTree2(){srand(time(0));constsize_tN=100000;RBTree<int,int>t;for(size_ti=0;i<N;i++){size_tx=rand();t.Insert(make_pair(x,x));}cout<<t.IsBalance()<<endl;}