喜欢的点赞,收藏,关注一下把!
1.红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
AVL树是严格平衡的,因为只要不平衡就旋转保持绝对平衡。
红黑树确保没有一条路径会比其他路径长出俩倍的意思是:最长路径不超过最短路径的2倍
那最长路径不超过最短路径的2倍该如何确保呢?
这是由红黑树的性质来保证的。
2.红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的
- 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
这里首先说明一下,我们所说的路径是指从根节点到NULL,而不是到叶子节点。
前两条性质很简单。我们着重说第3,第4条性质。
3.如果一个节点是红色的,则它的两个孩子结点是黑色的
从这条性质可以得到什么样的消息呢?
这个性质就是说没有连续的红色节点,还需要注意的是,并没有说黑的节点的孩子必须是红色的。(不要脑补)
4.对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
这条性质的意思是每条路径上都包含相同数量的黑色节点。
前4条性质,就可以帮我们确保红黑树最长路径不超过最短路径的2倍了,为什么这样说呢?
先想一想这样一个问题:一颗红黑树如果只看黑色节点,满足什么状态?
根据性质4,每条路径上都包含相同数量的黑色节点。
如果只看黑色,是不是接近满二叉树状态。
极限情况下:
最短路径:全黑,一条路径黑色节点的数量
根据性质3和性质4,那最长路径就出来了。
最长路径:一黑一红相间的路径
5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点,就是NIL节点)
红黑树的叶子节点和我们所熟知的叶子节点是不一样。
那就按照我们所熟知的叶子节点,我就给它黑色的,会有什么样的后果?
此时这颗树是不是违背了性质4:每条路径上都有包含相同数量黑色节点。(刚才已经说明这个路径指的是到NULL)
如果换成下面这个情况,再看性质5,是不是就明白了。
我们再说一说近似平衡。那红黑树性能最优情况,最差情况是什么样的呢?
最优情况: 左右平衡
这颗红黑树是一个全黑或者每条路径都是一黑一红间隔的满二叉树
最差情况: 左右越不平衡
假设这颗红黑树,左子树全黑,右子树一黑一红,长的是短的2倍
极限一点考虑,如果我们只考虑全黑呢,是不是就接近满二叉树。
全黑的路径长度是h,只有一两条一黑一红间隔的路径
2^h-1+ 红色节点=N ----->log2N
最长路径是不是就是2log2N
严格来说红黑树没有AVL效率好,但是这几乎不影响。
假设有10亿个数
log2n=10亿,n=30,AVL树只要找30次,就拿红黑树最差情况中最长路径那也只是60次,这相对于计算机CPU每秒上亿次计算有影响吗?并没有。
所以严格来说红黑树比AVL树效率差,但整体来说我们并不觉得差多少。
虽然红黑树没有AVL树效率那么好,但是AVL也带来了一个问题,AVL是通过不平衡就旋转保持绝对平衡的,但旋转是有代价的。而红黑树并不是这样,只是近似平衡,少了很多旋转。
3.红黑树节点的定义
//枚举
enum Coloer
{
RED,
BLACK
};
template<class T,class V>
struct RBTreeNode
{
pair<T, V> _kv;
RBTreeNode<T, V>* _left;
RBTreeNode<T, V>* _right;
RBTreeNode<T, V>* _parent;
Coloer _col;
RBTreeNode(const pair<T,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};
4.红黑树的插入
红黑树也是一颗二叉搜索树,所以我们还是按照以往的方式进行插入。不懂的可以看二叉搜索树有详细讲解。
先写一个框架,我们在慢慢完善内容
template<class T,class V>
class RBTree
{
typedef RBTreeNode<T, V> Node;
public:
bool Insert(const pair<T, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//红黑树根是黑色
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
//新插节点给红色还是黑色?
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//检测红黑树性质是否遭到破坏
return true;
}
private:
Node _root = nullptr;
};
现在框架还差一步,才真正完成。
新插节点,它应该是什么颜色?
如果是黑的行不行?
其实不能是黑色,插入黑色这条路径一定多一个黑色节点,那其他路径都少了一个,这样调整起来太麻烦了。所以插入节点颜色一定是红色,如果父亲是黑色那没什么问题,不用调整,父亲是红色,违反性质3,那就处理一下。
接下来我们就插入红色节点如果父亲是红色,而破坏性质3,对红黑树分讨论。
约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
情形一
cur为红,p为红,g为黑,u存在且为红
孩子是红的,父亲是红的,祖父一定是黑色,这个时候叔叔就是我们的关键。
注意,在插入的时候,叔叔一直是我们关注的重点,它是影响我们调整的方向。
那情况一该怎么解决呢?
两个红色不能相连,所以我们需要把父亲变黑,但是父亲变黑的,祖父原本就是黑色。那这条路径就多了一个黑色节点。因此我们需要把祖父变红,
但是叔叔那条路径就少了一个黑色节点,那把叔叔也变黑。
如果g是根节点,调整完成后,需要将就改成黑色。
如果g是子树,g一定有父亲,且g的父亲如果是红色,则需要继续向上调整
情形一解决方式:将p,u改成黑色,g改成红色,然后把g当初cur,继续向上调整。
上面是抽象图,我们接下来看看具体图
情形二
cur为红,p为红,g为黑,u不存在/u存在且为黑
u的情况有两种:
1.如果u节点不存在,那cur一定是新插入节点,因为如果cur不是新插入节点,则cur和p一定右一个节点颜色是黑的,就不满足性质4,每条路径黑色节点个数相同。
2.如果u存在,则一定是黑色,因为改成u存在且为红色我们已经分析过了
情形二解决方法:
p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色–p变黑,g变红
注意,旋转+变色调整之后,就不需要向上继续调整了,因为我们把这个子树的根变成黑色的了。
并且注意没,刚才所说的都是cur和p都在同一侧,所以都是单旋情况。
情形三
cur为红,p为红,g为黑,u不存在/u存在且为黑
虽然和情形二是一样,但是这次cur和p不在同一侧,双旋
情形三解决方法:
p为g的左孩子,cur为p的右孩子,则针对p做左单旋转,再以cur做右旋
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转,再以cur做左旋
cur、g变色–cur变黑色,g变红色
注意只要是旋转+变色都不需要向上调整了,直接结束调整即可。
插入的完整代码
下面这部分代码是写的时候需要注意的东西,所以单独拿出来说一下
bool Insert(const pair<T, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//红黑树根是黑色
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//调整
while (parent && parent->_col == RED) //所以这里parent判断一下
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//情形一
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent; //注意此时grandfather可能为根,那parent就有可能是野指针了
}
}
}
_root->_col = BLACK;//此时还需要把_root变成黑色,不过不管什么时候根都是黑色,所以在外面给一下
return true;
}
完整代码
bool Insert(const pair<T, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//红黑树根是黑色
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//调整
while (parent && parent->_col == RED) //所以这里parent判断一下
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//情形一
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent; //注意此时grandfather可能为根,那parent就有可能是野指针了
}
else
{
//这里不需要再管uncle存再不存在了,旋转变色都与它无关
if (cur == parent->_left)//情形二,不管uncle存不存,cur和parent在同一侧都单旋
{
RotaleR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情形三,不管uncle存不存,cur和parent在异侧双旋
{
RotaleL(parent);
RotaleR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//情形一
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//情形二
{
RotaleL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotaleR(parent);
RotaleL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//此时还需要把_root变成黑色,不过不管什么时候根都是黑色,所以在外面给一下
return true;
}
void RotaleL(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 (parent == ppNode->_left)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotaleR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
5.红黑树的删除
红黑树删除其实挺难的。情况太多了,但是从大方向上来说,删除节点无非就是三种情况:叶子节点,一个孩子的节点,两个孩子的节点,被删的是节点是红色,黑色,这些情况组合在一起删除,其实当我们真正组合分析下来,还是挺简单的。
删除节点的三种情况
1.删除叶子节点(非NIL节点)
- 如果是红色,直接删除即可,不影响黑高值
- 如果是黑色,导致黑高失衡,需要进行平衡调整
在红黑树的删除中,删除红色是最没影响的。
删除黑色叶子节点,其实一条路径黑色节点就少了一个,导致违背性质4,需要调整
同样这个情况也是红黑树删除中最麻烦的,等会在分析。
2.删除只有一个叶子节点的节点
- 此时删除节点只能是黑色,其子节点为红色,否则就无法满足红黑树的性质
- 将红色子节点的值拷贝到父节点上,将删除节点转成删除红色叶子节点(如情况1.1)
那为什么删除节点只能是黑色,其子节点为红色呢?反过来不行吗?
3.删除两个子节点的的节点
- 使用前序或者后继节点作为替代节点,转换为1或2的情况。
经过这样的分析是不是视野清晰起来了。
删除节点步骤
- 没找到删除节点直接返回
- 如果删除的是唯一根节点,_root置空并返回
-
删除有两个子节点的节点
- 使用前序或者后继节点作为替换的删除节点
- 将del指向替换节点,转换出4或5的情况处理
-
删除只有一个节点的节点时,删除节点只能是黑色,其子节点为红色,否则无法满足红黑树的性质
- 将红色子节点的值拷贝到父节点
- 将删除节点转换为删除红色叶子节点,即5.2
-
删除叶子节点
- 对要删除的黑色叶子节点进行调整(情况最复杂)
- 删除红黑两种叶子节点(红色直接删除,黑色但调整好了也直接删除)
我们先把整个思路写好,然后一点一点分析调整的情况。
//红黑树删除
bool Erase(const pair<T, V>& kv)
{
if (_root == nullptr)
return false;
Node* del = _root;
while (del)
{
if (del->_kv.first < kv.first)
{
del = del->_right;
}
else if (del->_kv.first > kv.first)
{
del = del->_left;
}
else
{
break;
}
}
//没找到
if (del == nullptr)
return false;
//del是唯一的根节点
if (del ==_root && del->_left == nullptr && del->_right == nullptr)
{
delete _root;
_root = nullptr;
return true;
}
//del有两个孩子
if (del->_left != nullptr && del->_right != nullptr)
{
//找后序替代删除
Node* MinRight = del->_right;
while (MinRight->_left)
{
MinRight = MinRight->_left;
}
del->_kv = MinRight->_kv;
del = MinRight;//删除节点指向替换节点
}
//del只有一个孩子
if ((del->_left != nullptr && del->_right == nullptr) || (del->_right != nullptr && del->_left == nullptr))
{
//只有一个孩子,父亲一定为黑,孩子一定为红
//1.将红色节点的值赋值给父亲
//2.将删除节点转换成删除红色叶子节点
Node* child = del->_left == nullptr ? del->_right : del->_left;
del->_kv = child->_kv;
del = child;//删除节点指向替代的红色节点
}
//上面有两个孩子/一个孩子最终都会转换成叶子节点
//叶子节点是黑色,直接删除违背性质4,还需要调整
if (del->_col == BLACK)
{
//调整
AdjustRBTreeBalance(del);
}
//叶子节点是红色或是黑色但调整好了,就可以直接删除了
//并且我们这是三叉,不用找父亲
Node* parent = del->_parent;
if (del == parent->_left)
{
parent->_left = nullptr;
}
else
{
parent->_right = nullptr;
}
delete del;
return true;
}
删除黑色叶子节点调整平衡情况分析
删除黑色叶子节点需要调整的情况有三种
- 根节点,直接返回删除
-
兄弟节点为黑色
- 兄弟有红色子节点
- 兄弟无红色字节的
- 兄弟为红色
删除的是黑色叶子节点,我们着重关注它的兄弟节点。
第一种情况没什么好说的。下面就第二种第三种情况详细分析。
2.兄弟节点为黑色
1.兄弟有红色子节点
这里细分成三种情况。
1.1兄弟有红色左子节点
1.2兄弟有两个红色子节点
1.3兄弟有红色右子节点
注意这里D是黑色右叶子节点,D当然还有可能是黑色左孩子节点,那旋转和变色就反过来了,这里就不再演示,写代码一定注意分情况。
我们可以总结一下
2.兄弟无红色子节点
兄弟无红色子节点,这里依照父亲节点颜色要分成两种情况。
2.1父亲是红色节点
2.2父亲是黑色节点
这里还像上面一样,父变黑,兄变红可以解决问题吗?
当然如果上图就是我们整颗树,这种方法肯定解决问题了。
那是以p为根的子树呢?
这样简单变色,然后删除D,这条路径相对其他路径来说,就少了一个黑色节点,违背了性质4。
所以父亲节点是黑色的具体做法
1.将兄弟节点染红
2.把父节点当作新的删除节点,递归调用前面的方法,进行相应处理,直至遇到红色父亲节点并将其染黑,兄弟染红或者遇到根节点结束
3.兄弟是红色节点
兄弟是红色节点,那父亲一定是黑色的,否则违背性质3,并且这个兄弟一定有两个黑色字节的,否则违背性质4 。
自此关于删除黑色叶子节点调整的所有情况都说完了,其实按照大方向然后再细分一些小的方向也还可以。
下面总结一下。
黑色节点调整平衡方法步骤
- 是根节点:直接返回删除即可
-
兄弟黑色
-
兄弟有红子:黑不够,侄来凑
- 根据LL,RR,RL,LR类型旋转+变色
-
兄弟无红子:兄无够,父红头
- 父节点是红色:父变黑 兄变红
- 父节点是黑色:兄变红 父作为新删除(调整)节点向上递归调整
-
兄弟有红子:黑不够,侄来凑
-
兄弟红色
兄弟红,旋中黑;随父侄,黑变红- 兄弟是左子树:右旋+兄变黑+兄右变红
- 兄弟是左子树:左旋+兄边黑+兄左变红
删除的完整代码
//这里是为了能够返回旋转类型而随便定义的,没有任何实际意义
//如果不想写GetRotaleType函数,可以直接在AdjustRBTreeBalance判断都是一样的结果
#define LL 1
#define RR 2
#define LR 3
#define RL 4
int GetRotaleType(Node* Brother)
{
Node* parent = Brother->_parent;
if (Brother == parent->_left)//Brother是左子树
{
//Brother,只有一个孩子并且和它同侧,或者有两个孩子都单旋
if (Brother->_left != nullptr && Brother->_left->_col == RED)
{
return RR;
}
//rother,只有一个孩子并且和它异侧,双旋
if(Brother->_right != nullptr && Brother->_right->_col == RED)
{
return LR;
}
}
else//Brother是右子树
{
//同上
if (Brother->_right != nullptr && Brother->_right->_col == RED)
{
return LL;
}
if(Brother->_left != nullptr && Brother->_left->_col == RED)
{
return RL;
}
}
//无红色子节点不旋转
return 0;
}
void *AdjustRBTreeBalance*(Node* del)
{
//1.是根节点
//2.兄弟是黑色节点 ------ 2.1兄弟有红色子节点 2.2兄弟无红色子节点
//3.兄弟是红色节点
//1.是根节点,刚开始我们就把del是根节点情况考虑过了
//这里del还是根的情况,是因为下面我们有递归,递归到根要结束
//注意我们这里的del是形参,形参的改变并不影响实参,所以最后删除不会是删除根,而造成删除出现野指针的情况
if (del == _root)
return;
//2.兄弟是黑色节点
//兄弟要分左右两种情况旋转
Node* parent = del->_parent;
Node* Brother = parent->_left == del ? parent->_right : parent->_left;
if (Brother->_col == BLACK)
{
int type = GetRotaleType(Brother);
switch(type)//兄不够,侄来凑
{
// 2.1兄弟有红色子节点 ---- 通过旋转变色达到平衡
case LL: //变色原则:恢复未删除前各个位置颜色 爷孙变色,兄变父色
Brother->_col = parent->_col;//兄弟旋转后取代父亲节点颜色
Brother->_right->_col = parent->_col = BLACK;//父亲和侄节点变黑
RotaleL(parent);
break;
case RR:
Brother->_col = parent->_col;
Brother->_left->_col = parent->_col = BLACK;
RotaleR(parent);
break;
case LR:
Brother->_right->_col = parent->_col;//侄节点变成父节点颜色
parent->_col = BLACK;//父节点变黑
RotaleL(Brother);
RotaleR(parent);
break;
case RL:
Brother->_left->_col = parent->_col;
parent->_col = BLACK;
RotaleR(Brother);
RotaleL(parent);
break;
default://兄无后,父红头
//2.2兄弟无红色子节点 ---- 2.2.1父节点是红色 2.2.2父节点是黑色
if (parent->_col == RED)//2.2.1父节点是红色 ---交换父兄颜色
{
parent->_col = BLACK;
Brother->_col = RED;
}
else//父节点是黑色,需要向上递归调整---虽然这个最麻烦,但是我们以前把情况都写出来了,直接递归即可
{
//del被删,以parent为根节点违背性质4,因此兄先变红先把以parent为根先平衡
//然后在以parent为被删节点,向上递归调用,注意不是真的要删parent,从始至终删的都是del
Brother->_col = RED;
AdjustRBTreeBalance(parent);
}
}
}
else//3.兄弟是红色节点 兄弟红,旋黑中,随父侄,黑变红
{
//1.兄弟是左子树:右旋---右侄变红
//兄弟是红色节点,它父亲必定是黑色,同时它的孩子必定有两个黑节点,否则违背性质4
if (Brother == parent->_left)
{
Brother->_col = BLACK;//兄弟变色
Brother->_right->_col = RED;//随着父亲的侄子,颜色变红
//虽然Brother有两个孩子,但是单旋就可以
RotaleR(parent);
}
else //2.兄弟是右子树:左旋--左侄变红
{
Brother->_col = BLACK;
Brother->_left->_col = RED;
RotaleL(parent);
}
}
}
//红黑树删除
bool Erase(const pair<T, V>& kv)
{
if (_root == nullptr)
return false;
Node* del = _root;
while (del)
{
if (del->_kv.first < kv.first)
{
del = del->_right;
}
else if (del->_kv.first > kv.first)
{
del = del->_left;
}
else
{
break;
}
}
//没找到
if (del == nullptr)
return false;
//del是唯一的根节点
if (del ==_root && del->_left == nullptr && del->_right == nullptr)
{
delete _root;
_root = nullptr;
return true;
}
//del有两个孩子
if (del->_left != nullptr && del->_right != nullptr)
{
//找后序替代删除
Node* MinRight = del->_right;
while (MinRight->_left)
{
MinRight = MinRight->_left;
}
del->_kv = MinRight->_kv;
del = MinRight;
}
//del只有一个孩子
if ((del->_left != nullptr && del->_right == nullptr) || (del->_right != nullptr && del->_left == nullptr))
{
//只有一个孩子,父亲一定为黑,孩子一定为红
//1.将红色节点的值赋值给父亲
//2.将删除节点转换成删除红色叶子节点
Node* child = del->_left == nullptr ? del->_right : del->_left;
del->_kv = child->_kv;
del = child;
}
//上面有两个孩子/一个孩子最终都会转换成叶子节点
//叶子节点是黑色,直接删除违背性质4,还需要调整
if (del->_col == BLACK)
{
AdjustRBTreeBalance(del);
}
//叶子节点是红色或是黑色但调整好了,就可以直接删除了
//并且我们这是三叉,不用找父亲
Node* parent = del->_parent;
if (del == parent->_left)
{
parent->_left = nullptr;
}
else
{
parent->_right = nullptr;
}
delete del;
return true;
}
6.判断是否是红黑树
给你一颗红黑树你会怎么判断它是否是红黑树呢。
如果用最长路径不超过最短路径的2倍可不可以?
答案是不可以。如果确实是最长路径不超过最短路径2倍,但是其它路径颜色不符合红黑树,这颗树还是红黑树吗?显而易见不是的。
所有我们应该用红黑树的性质来判断。
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的
- 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
我们主要用第2,3,4的性质
先给一个框架
bool IsRBTree(Node* root)
{
if (_root == nullptr)
return true;
//第2条性质
if (_root->_col != BLACK)
return false;
//接下来就是第3,4条性质
}
现在有一个问题第3条性质你要怎么样用?
首先肯定得用递归把整颗树都查完这是肯定的。
然后呢,如果碰见红色节点,你是拿它与它的父亲做比较,还是它的孩子做比较呢?
应该选择与它的父亲做比较,看是不是连续的红色节点。这是因为一个节点它孩子情况有很多,你需要判断有没有孩子,左孩子还是右孩子,这样写代码太繁琐,而选择与它父亲做比较,因为它只有一个父亲。
bool Check(const Node* root)
{
if (root == nullptr)
return true;
if (root->_col == RED && root->_parent->_col == RED)
return false;
return Check(root->_left) && Check(root->_right);
}
bool IsRBTree()
{
if (_root == nullptr)
return true;
if (_root->_col != BLACK)
return false;
//不能拿IsRBTree当递归使用,自己重新写一个
Check(_root);
}
性质4:每条路径都有相同的黑色节点,该怎么检验呢?
既然我们刚才已经写了递归检验整棵树,那我们依旧还是用这个递归,改造一下。文章来源:https://www.toymoban.com/news/detail-788384.html
就拿下图来说,每个节点都给一个值,来记录根节点到该节点的黑色节点的数量。 当递归走到空就能探查到每条路径黑色节点的数量。
这里给两个思路
1.把每层黑色节点数量都存下来,最后在比较
2.给一个参考值,参考值是红黑树中某条路径的黑色节点的数量,递归每条路径走完都与这个值比较,不相等就报错文章来源地址https://www.toymoban.com/news/detail-788384.html
bool Check(const Node* root,int blacknum,int ref)
{
if (root == nullptr)
{
if (blacknum != ref)
{
cout << "违反第四条规定" << ";" << "每条路径都有相同的黑色节点" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
//打印错误信息,方便查找
cout << "违反第3条规定" << ":" << root->_kv.first << "不能有相连的红色节点" << endl;
return false;
}
if (root->_col == BLACK)
++blacknum;
return Check(root->_left,blacknum,ref) && Check(root->_right,blacknum,ref);
}
bool IsRBTree()
{
if (_root == nullptr)
return true;
if (_root->_col != BLACK)
return false;
//参考值
int ref = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
++ref;
left = left->_left;
}
return Check(_root,0,ref);
}
到了这里,关于【C++】红黑树插入删除的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!