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

红黑树~1个子删除

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

Feek · 技术社区 · 9 年前

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

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

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

感谢您的反馈!!

2 回复 | 直到 9 年前

Ahmed Akhtar 9 年前

不,这是不可能的。

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

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

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

cheeseandtomato 3 年前

这要看情况。

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

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

推荐文章

Community wiki · C中有哪些耗时的操作?

1 年前

Tintenfisch · 传递参数:array与C和C中的*&array和&array[0]之间的差异++

1 年前

daryldxn · Windows筛选平台计算通过TCP连接发送的字节和接收的字节

1 年前

Mike Balts · 它们将被打印多少次,为什么?我知道:“阿尔法”一次,“贝塔”两次,“欧米茄”两次但我不知道为什么

1 年前

Mohammed Eid · 数据类型“char”是否可以被视为数据类型“int”?

1 年前

Community wiki · 将所有处理器电源都投入到任务中

1 年前

Community wiki · 在C&数据结构中实现不同数据结构的聪明方法,应该更频繁地使用

1 年前

Community wiki · C++为C添加了什么?[已关闭]

1 年前

Abhinav Kumar · 如何将#define的数据类型设置为长双精度?

1 年前

Community wiki · 打印1到1000,不带循环或条件

1 年前