C++数据结构红黑树的示例分析

C++数据结构红黑树的示例分析

这篇文章给大家分享的是有关C++数据结构红黑树的示例分析的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

概念和性质

红黑树的概念： 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。它是通过控制节点颜色的方式来控制这棵树的相对平衡，保证了没有一条路径会比其它路径长出两倍。

红黑树的性质：

• 结点是红色或黑色。

• 根结点是黑色。

• 所有叶子都是黑色。（叶子是空结点）

• 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

• 从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点

上面的五个性质还可以用更通俗的语言描述为三句话：

• 根节点是黑色的

• 没有连续的红节点

• 每条路径的黑节点数目相同（每条路径指的是从根节点到黑色的空节点）

思考： 为什么红黑树中最长路径的长度不会超过最短路径节点个数的两倍？

最长路径： 该条路径上节点分布是一红一黑

最短路径： 该条路径上节点分布是全黑

假设每条路径黑色节点数为N，则最长路径为2N，最短路径为N，所以这样就推出红黑树中最长路径的长度不会超过最短路径节点个数的两倍。

红黑树的实现

红黑树节点定义

这里也是一个三叉链，其中每个节点包含颜色的元素在里面：

enumColor{RED,BLACK};template<classK,classV>structRBTreeNode{RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;pair<K,V>_kv;Color_color;RBTreeNode(constpair<K,V>&kv,Colorcolor=RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}};

????红黑树结构定义

里面只包含一个根节点的成员变量，和前面两棵树的结构定义没有什么大的区别，区别在于节点的定义：

template<classK,classV>classRBTree{typedefRBTreeNode<K,V>Node;public:private:Node*_root=nullptr;};

红黑树的插入

方法概述

第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点

第二步： 为了不破坏红黑树的规则，我们插入节点后要对红黑树进行相应的调整

思考： 我们插入节点应该默认插入红色节点好还是黑色节点好呢？ 答案是红色节点。为什么呢？我们要考虑哪种方式对红黑树的破坏性更大一点。如果是黑色，此时黑导致该条路径比其它路径上黑色节点数都多一个，这样下来调整红黑树的步骤代价似乎会有点大；如果是红色，不会破坏规则5，只是破坏规则4，可能会出现连续的红色节点，这样我们只需要调整该节点及其附近节点的颜色即可，代价没有前一种方式大，所以我们选择第二种方式。

调整节点颜色

第一种情况： 如果插入节点的父亲是黑色节点，那么可以直接结束，不需要继续调整了

第二种情况： 如果插入节点为的父亲为红色节点，就需要进行相应的调整 下面讨论父亲节点是祖父节点的左孩子的几种情形（是右孩子的情形和这个类型，大家可以自己推演一下，这里我们把父亲节点叫做p(parent)，祖父叫g(grandfather)，叔叔节点叫u(uncle)）：

情况1： p为红色（g肯定是存在的且为黑），u存在且为红

操作： 把p和u改成黑，g改成红，如果g为根节点就把g的颜色变成黑然后结束，如果g不为根节点，且g的父亲为黑色也节数，为红色就需要迭代向上调整，判断此时处于何种情况 具像图：

如果g的父亲为红，就迭代向上调整：cur = grandfather,grandfather = grandfather->parent

抽象图：抽象图中cur可能是新插入的节点，也可能是迭代调整上来的节点，这里g这棵子树每条路径黑色节点数是相同的，且调整后g这棵子树的每条路径黑色数相同且和之前一样。cur是parent的左孩子和右孩子是一样的，因为这里都是对颜色进行控制，和方向无关。

情况2： p为红色（g肯定是存在的且为黑），u不存在

操作： cur为parent的左孩子时，对g进行右单旋，然后将p的颜色改黑，g的颜色改红；cur为parent的右孩子时，先对p进行左单旋，然后对g进行右单旋，然后将cur的颜色改黑，g的颜色改红 具象图：此时cur一定为新增节点，因为g的右子树没有黑节点，所以cur的下面也不可能有黑节点 cur为parent的左孩子时 一条直线，此时进行右单旋

cur为parent的左孩子时 一条折线，此时进行左右双旋

上面的第二种情况可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。

情况3： p为红色（g肯定是存在的且为黑），u存在且为黑

操作： 如果cur为parent的左孩子，对g进行右单旋，然后将p的颜色改为黑，g的颜色改为红；如果cur为parent的右孩子，先对p进行左单旋，对g进行右单旋，然后将cur的颜色改为黑，g的颜色改为红

解释： 假设此时a和b中黑色节点数为a，c的黑色节点数也一定为a，d和e的黑色节点数就是a-1，调整后cur和g的抽象图的黑色节点都是a，整体相等。 抽象图：此时cur一定为调整上来的节点，因为如果是新增节点的话，那么原来g这棵子树左右黑色节点数目不等，所以cur一定是调整上来的节点。 cur为parent的左孩子 一条直线，进行右单旋即可

cur为parent的右孩子 一条折线，此时进行左右双旋

和情况2一样，上面的第二种情况可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。

总结： 上面就是p是g的左孩子的所有情形，为g的右孩子是与这个类似。还有注意的是根节点最后一定要改为黑色。

插入代码实现

旋转代码如下： 这里就是上一篇博客的旋转代码，具体如下

//左单旋voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;//parent的右指向subR的左parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*ppNode=parent->_parent;parent->_parent=subR;subR->_left=parent;if(ppNode==nullptr){_root=subR;subR->_parent=nullptr;}else{if(ppNode->_left==parent)ppNode->_left=subR;elseppNode->_right=subR;subR->_parent=ppNode;}}//右单旋voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;//parent的左指向subL的右parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*ppNode=parent->_parent;parent->_parent=subL;subL->_right=parent;if(ppNode==nullptr){_root=subL;subL->_parent=nullptr;}else{if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;subL->_parent=ppNode;}}

插入代码实现如下：

pair<Node*,bool>Insert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv,BLACK);//根节点默认给黑returnmake_pair(_root,true);}Node*cur=_root;Node*parent=nullptr;while(cur){parent=cur;if(kv.first<cur->_kv.first)cur=cur->_left;elseif(kv.first>cur->_kv.first)cur=cur->_right;elsereturnmake_pair(nullptr,false);}//节点默认给红节点，带来的影响更小//给黑节点的话会影响每条路径的黑节点相同这条规则cur=newNode(kv);if(cur->_kv.first<parent->_kv.first){parent->_left=cur;cur->_parent=parent;}else{parent->_right=cur;cur->_parent=parent;}//调整颜色//情况一：p是红，g是黑，u存在且为红//调整后的几种情况：//1.如果g为根节点，把g的颜色改成黑，结束；//2.如果g不为根节点，//a.g的父节点为黑，结束；//b.g的父节点为红，迭代向上调整,继续判断是哪种情况（一和三）//cur=grandfather;//father=cur->father;//这里不管cur是在p的左边还是右边，都是一样的，关心的是颜色而不是位置//情况二：p是红，g是黑，u不存在/u为黑curpg三个是一条直线//调整方法（左边为例）：1.右单旋2.把p改成黑，g改成红//a.u不存在时，cur必定是新增节点//b.u存在时，cur必定是更新上来的节点//情况三：p是红，g是黑，u不存在/u为黑curpg三个是一条折线//调整方法（左边为例）：1.p左单旋2.g右单旋3.把cur改成黑，g改成红//a.u不存在时，cur必定是新增节点//b.u存在时，cur必定是更新上来的节点while(parent&&parent->_color==RED){Node*grandfather=parent->_parent;//左边if(grandfather->_left==parent){//红黑色的条件关键看叔叔Node*uncle=grandfather->_right;//u存在且为红if(uncle&&uncle->_color==RED){//调整p和u改成黑，g改成红parent->_color=uncle->_color=BLACK;grandfather->_color=RED;//迭代向上调整cur=grandfather;parent=cur->_parent;}else//u存在为黑/u不存在{//折线用一个左单旋处理1.p左单旋2.g右单旋3.把cur改成黑，g改成红curpg三个是一条折线if(cur==parent->_right){RotateL(parent);swap(parent,cur);}//直线curpg把p改成黑，g改成红//右单旋有可能是第三种情况RotateR(grandfather);parent->_color=BLACK;grandfather->_color=RED;}}//uncle在左边else{Node*uncle=grandfather->_left;if(uncle&&uncle->_color==RED){parent->_color=uncle->_color=BLACK;grandfather->_color=RED;//迭代向上调整cur=grandfather;parent=cur->_parent;}else{//折线用一个右单旋处理gpcurg变红p边黑if(cur==parent->_left){RotateR(parent);swap(parent,cur);}//直线gpcur把p改成黑，g改成红//左单旋有可能是第三种情况RotateL(grandfather);parent->_color=BLACK;grandfather->_color=RED;}}}_root->_color=BLACK;returnFind(kv.first);}

红黑树的删除

方法概述

第一步： 先按照二叉搜索树删除节点的方式找到要删除节点（也可能是替代节点）

第二步： 然后为了不破坏红黑树的几条规则，要对节点的颜色进行相应地调整

调整颜色

第一种情况： 删除节点（也可能是替代节点）（之后都叫delNode），如果该节点为红色，则直接删除退出即可，delNode没找到也可以直接退出

第二种情况： delNode为黑色（最多只有一个孩子且为红色，因为替代节点最多只有一个孩子），delNode有一个孩子时，删除delNode节点，然后把孩子节点的颜色改成黑色，也可直接结束

第三种情况： delNode为黑色，且没有孩子时，有下面几种情况（兄弟节点叫b(brother)，父亲节点叫p(parent)）（下面是cur是parent的左孩子的情形，右孩子的情形和它类似，不介绍）：

情况1： p为黑，b为红，两个孩子存在且一定为黑

操作： 对p进行左单旋，然后将p的颜色改成红，b的颜色改成黑

分析： 调整之前抽象三角形的黑色节点都是a，因为cur下面有一个节点要被删除，所以cur下面少了一个黑色节点，也就是p的左边少了一个黑色节点，调整后b两边的黑色节点数不变，cur下面黑色节点数还是少了一个，但是它的兄弟是黑色节点，后面可以通过对cur进行检索，使用其它情况解决这个问题。

抽象图：

情况2： p为红，b为黑，b的两个孩子存在且一定为黑

操作： 把p的颜色改成黑，b的颜色改成红

分析： 调整前，p左边少了一个黑色的节点，调整后，p的左边补上了一个黑色节点，且p的右边的黑色节点数不变，这里可以结束

抽象图：

情况3： p为黑色，且b为黑色，b的两个孩子为黑

操作： 把b的颜色改为红

分析： 调整之前，p左边是缺少一个黑色节点的，调整后，两边黑色节点数相同，但是此时p的右边也少了一个黑色节点，此时p的父亲g，g的右边是比左边多一个黑色节点的，所以需要迭代向上调整，把cur变成p，继续对cur进行检索

抽象图：

情况4： p为任意颜色，b的颜色为黑，b的右孩子为红色

操作： 对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑

分析： 调整前，a和b的黑色节点数都是x，c,d,e的黑色节点个数为x+1，也就是p的左边少了一个黑色的节点，调整后，p两边的黑色节点都是x+1，b两边的黑色节点都是x+2，整体都调整好了，所以这里可以结束

抽象图：

情况5： p为任意颜色，b的颜色为黑，b的左孩子为红色

操作： 先对b进行右单旋，然后把b改红，bL改黑，然后对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑（情况4）

分析： 和情况四其实是一样的，情况4的b和bR是直线，这里是折线，要通过右单旋变成直线，然后就转为情况4

抽象图：

总结： 删除就是以上几种情况，一般是左边少一个黑色节点，就靠右边补一个，结束，或者右边减少一个，然后两边整体少一个，对父亲节点进行检索。

删除代码实现

代码实现如下：

boolErase(constK&key){//如果树为空，删除失败if(_root==nullptr)returnfalse;Node*parent=nullptr;Node*cur=_root;Node*delNode=nullptr;Node*delNodeParent=nullptr;while(cur){//小于往左边走if(key<cur->_kv.first){parent=cur;cur=cur->_left;}elseif(key>cur->_kv.first){parent=cur;cur=cur->_right;}else{//找到了，开始删除//1.左右子树都为空直接删除可以归类为左为空//2.左右子树只有一边为空左为空，父亲指向我的右，右为空，父亲指向我的左//3.左右子树都不为空取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除if(cur->_left==nullptr){//要删除节点为根节点时，直接把右子树的根节点赋值给——root//根节点的话会导致parent为nullptrif(_root==cur){_root=_root->_right;if(_root){_root->_parent=nullptr;_root->_color=BLACK;}returntrue;}else{delNode=cur;delNodeParent=parent;}}elseif(cur->_right==nullptr){if(_root==cur){_root=_root->_left;if(_root){_root->_parent=nullptr;_root->_color=BLACK;}returntrue;}else{delNode=cur;delNodeParent=parent;}}else{//找右子树中最小的节点Node*rightMinParent=cur;Node*rightMin=cur->_right;//去右子树找while(rightMin->_left){rightMinParent=rightMin;rightMin=rightMin->_left;}//swap(cur->_key,rightMin->_key);//替代删除cur->_kv=rightMin->_kv;delNode=rightMin;delNodeParent=rightMinParent;}break;}}//没找到if(cur==nullptr)returnfalse;//1.替代节点为红，直接删除（看上面）//2.替代节点为黑（只能有一个孩子或两个孩子）//i)替代节点有一个孩子不为空（该孩子一定为红）,把孩子的颜色改成黑//ii)替代节点的两个孩子都为空cur=delNode;parent=delNodeParent;if(cur->_color==BLACK){if(cur->_left)//左孩子不为空{cur->_left->_color=BLACK;}elseif(cur->_right){cur->_right->_color=BLACK;}else//替代节点的两个孩子都为空{while(parent){//cur是parent的左if(cur==parent->_left){Node*brother=parent->_right;//p为黑if(parent->_color==BLACK){Node*bL=brother->_left;Node*bR=brother->_right;//SL和SR一定存在且为黑if(brother->_color==RED)//b为红，SL和SR都为黑b的颜色改黑，p的颜色改红情况a{RotateL(parent);brother->_color=BLACK;parent->_color=RED;//没有结束，还要对cur进行检索}elseif(bL&&bR&&bL->_color==BLACK&&bR->_color==BLACK)//b为黑，孩子存在{//且孩子也为黑把brother改成红色，迭代GP比GU小1情况bbrother->_color=RED;cur=parent;parent=parent->_parent;}//bL存在为红，bR不存在或bR为黑情况e右旋后变色转为情况delseif(bL&&bL->_color==RED&&(!bR||(bR&&bR->_color==BLACK))){RotateR(brother);bL->_color=BLACK;brother->_color=RED;}elseif(bR&&bR->_color==RED)//右孩子为红，进行一个左旋，然后把右孩子的颜色改成黑色情况d{RotateL(parent);swap(brother->_color,parent->_color);bR->_color=BLACK;break;}else{//curpb都是黑，且b无孩子，迭代更新//parent是红就结束brother->_color=RED;cur=parent;parent=parent->_parent;}}//p为红b一定为黑else{Node*bL=brother->_left;Node*bR=brother->_right;if(bL&&bR&&bL->_color==BLACK&&bR->_color==BLACK)//b的孩子全为黑情况cp变黑，b变红结束{brother->_color=RED;parent->_color=BLACK;break;}//bL存在为红，bR不存在或bR为黑情况e右旋后变色转为情况delseif(bL&&bL->_color==RED&&(!bR||(bR&&bR->_color==BLACK))){RotateR(brother);bL->_color=BLACK;brother->_color=RED;}elseif(bR&&bR->_color==RED)//右孩子为红，进行一个左旋，然后把右孩子的颜色改成黑色情况d{RotateL(parent);//swap(brother->_color,parent->_color);brother->_color=parent->_color;parent->_color=BLACK;bR->_color=BLACK;break;}else//cur为黑，p为红，b为黑调整颜色，结束{parent->_color=BLACK;brother->_color=RED;break;}}}else{Node*brother=parent->_left;//p为黑if(parent->_color==BLACK){Node*bL=brother->_left;Node*bR=brother->_right;//SL和SR一定存在且为黑if(brother->_color==RED)//b为红，SL和SR都为黑b的颜色改黑，p的颜色改红情况a{RotateR(parent);brother->_color=BLACK;parent->_color=RED;//没有结束，还要对cur进行检索}elseif(bL&&bR&&bL->_color==BLACK&&bR->_color==BLACK)//b为黑，孩子存在{//且孩子也为黑把brother改成红色，迭代GP比GU小1情况bbrother->_color=RED;cur=parent;parent=parent->_parent;}//右孩子存在且为红，但左孩子不存在或为黑情况e右旋后变色转为情况delseif(bR&&bR->_color==RED&&(!bL||(bL&&bL->_color==BLACK))){RotateL(brother);brother->_color=RED;bR->_color=BLACK;}elseif(bL&&bL->_color==RED)//左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色情况d{RotateR(parent);swap(brother->_color,parent->_color);bL->_color=BLACK;break;}else{//curpb都是黑，且b无孩子，迭代更新//if(parent==_root)//p是根节点，把b变红否则迭代brother->_color=RED;cur=parent;parent=parent->_parent;}}//p为红b一定为黑else{Node*bL=brother->_left;Node*bR=brother->_right;if(bL&&bR&&bL->_color==BLACK&&bR->_color==BLACK)//b的孩子全为黑情况cp变黑，b变红结束{brother->_color=RED;parent->_color=BLACK;break;}//右孩子存在且为红，但左孩子不存在或为黑情况e右旋后变色转为情况delseif(bR&&bR->_color==RED&&(!bL||(bL&&bL->_color==BLACK))){RotateL(brother);brother->_color=RED;bR->_color=BLACK;}elseif(bL&&bL->_color==RED)//左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色情况d{RotateR(parent);//swap(brother->_color,parent->_color);brother->_color=parent->_color;parent->_color=BLACK;bL->_color=BLACK;break;}else//cur为黑，p为红，b为黑调整颜色，结束{parent->_color=BLACK;brother->_color=RED;break;}}}}}}delNodeParent=delNode->_parent;//删除if(delNode->_left==nullptr){if(delNodeParent->_left==delNode)delNodeParent->_left=delNode->_right;elsedelNodeParent->_right=delNode->_right;if(delNode->_right)//右不为空，就让右节点的父指针指向delNodeParentdelNode->_right->_parent=delNodeParent;}else{if(delNodeParent->_left==delNode)delNodeParent->_left=delNode->_left;elsedelNodeParent->_right=delNode->_left;if(delNode->_left)//右不为空，就让右节点的父指针指向delNodeParentdelNode->_left->_parent=delNodeParent;}deletedelNode;delNode=nullptr;returntrue;}

红黑树的查找

这里比较简单，直接上代码：

boolFind(constK&key){if(_root==nullptr)returnfalse;Node*cur=_root;while(cur){//小于往左走if(key<cur->_kv.first){cur=cur->_left;}//大于往右走elseif(key>cur->_kv.first){cur=cur->_right;}else{//找到了returntrue;}}returnfalse;}

红黑树的验证

这里通过递归计算出每条路径的节点个数来进行比较，同时验证其他的性质是否符合，从而验证是否红黑树：

boolIsValidRBTree(){//空树也是红黑树if(_root==nullptr)returntrue;//判断根节点的颜色是否为黑色if(_root->_color!=BLACK){cout<<"违反红黑树的根节点为黑色的规则"<<endl;returnfalse;}//计算出任意一条路径的黑色节点个数size_tblackCount=0;Node*cur=_root;while(cur){if(cur->_color==BLACK)++blackCount;cur=cur->_left;}//检测每条路径黑节点个数是否相同第二个参数记录路径中黑节点的个数return_IsValidRBTree(_root,0,blackCount);}bool_IsValidRBTree(Node*root,size_tk,size_tblackCount){//走到空就判断该条路径的黑节点是否等于blackCountif(root==nullptr){if(k!=blackCount){cout<<"违反每条路径黑节点个数相同的规则"<<endl;returnfalse;}returntrue;}if(root->_color==BLACK)++k;//判断是否出现了连续两个红色节点Node*parent=root->_parent;if(parent&&root->_color==RED&&parent->_color==RED){cout<<"违反了不能出现连续两个红色节点的规则"<<endl;returnfalse;}return_IsValidRBTree(root->_left,k,blackCount)&&_IsValidRBTree(root->_right,k,blackCount);}

实例演示：

voidTestRBTree(){//srand((size_t)time(nullptr));RBTree<int,int>rbt;//inta[]={1,2,3,4,5,6,7,8,9,10,5,7,8,11,12,13};//inta[]={16,3,7,11,9,26,18,14,15};//inta[]={4,2,6,1,3,5,15,7,16,14};//inta[]={10,9,8,7,6,5,4,3,2,1};vector<int>a;for(size_ti=0;i<13;++i){//a.push_back(rand());a.push_back(i);}//inta[]={4,2,6,7,3,5};/*vector<int>v;v.reserve(100000);for(size_ti=1;i<=v.capacity();++i){v.push_back(i);}*/for(autoe:a){intbegin=clock();rbt.Insert(make_pair(e,e));intend=clock();cout<<"插入数据"<<e<<"后："<<"树的高度："<<rbt.Height()<<"是否为红黑树："<<rbt.IsValidRBTree();cout<<"用时："<<end-begin<<"ms"<<endl;}cout<<"-------------------------------------------------------"<<endl;for(autoe:a){intbegin=clock();rbt.Erase(e);intend=clock();cout<<"删除数据"<<e<<"后："<<"树的高度："<<rbt.Height()<<"是否为红黑树："<<rbt.IsValidRBTree();cout<<"用时："<<end-begin<<"ms"<<endl;}//cout<<rbt.IsValidRBTree()<<endl;//rbt.InOrder();}

代码运行结果如下：

AVL树和红黑树的比较

总结： AVL树是严格意义上的平衡，红黑树是相对的平衡，两者都很高效，但后者用的更多，因为它旋转更是，实现相对简单，付出的代价少一点。

感谢各位的阅读！关于“C++数据结构红黑树的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！