代码之家 › 专栏 › 技术社区 › Feek

红黑树~1个子删除

red-black-tree data-structures c c++

Feek · 技术社区 · 8 年前

红色父节点是否可能只有一个黑色子节点?我一直在网上玩红/黑树模拟器,但我没办法让这种情况发生。

问这个问题的原因是我相信我的代码中有一个不必要的IF。。。

if (temp_node->color == BLACK && node->color == RED)
{
    node->color = BLACK;
    global_violation = false;
}

感谢您的反馈!!

2 回复 | 直到 8 年前

Ahmed Akhtar 8 年前

不,这是不可能的。

请记住,在红/黑树中,从树根到树外的所有路径都必须经过相同数量的黑色节点(这是红/黑树不变量之一)。

如果您有一个红色节点 x 有一个黑人孩子 y ,它不能有另一个红色子节点(因为这打破了红色节点不能有红色子节点的红色/黑色不变量)。

这意味着 x(x) 到丢失的子节点将通过比路径少至少一个黑色节点 x(x) ,然后到 y ,然后从那里离开树,打破红/黑树不变量。

cheeseandtomato 2 年前

这要看情况。

目前(2021 10月)维基百科的图表上至少有一个黑色节点。

如果这是一种混乱,那么明确排除单节点情况作为新规则可能会有所帮助。

推荐文章

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前

Eddiex045 · 比较两个文本文件,匹配项转到一个新文件

2 年前

Liferafter · TypeError:缺少1个必需的位置参数(LinkedList)

2 年前

NOBUD · 最大堆插入函数实现C++

2 年前

Tuna ArÄ±yÃ¼rek · “结构对象*对象”和“对象*对象”之间的区别

2 年前

Mark Tyler · 具有O(1)随机移除和添加的数据结构,用于洗牌生成器顺序

6 年前

riasc · 嵌套贴图结构创建空贴图

6 年前

Foxhound013 · 将要发送到视图中的HighCharts的结构化数据

6 年前

Akshay Barpute · cpp中的以下链表程序有什么问题?

6 年前

Batwoman05 · C++中是否有具有类似函数的树集数据结构

6 年前