在Sedgewick的左倾红黑树中(在他的论文或他的算法书中介绍),对标准BST的一个修改是在每次插入后将根节点涂成黑色,请参见< code>insert(Key,Value)中的< code>root.color = BLACK。
我明白这在语义上是必要的,因为根节点永远不应该是3节点/4节点的左子节点。然而,我不明白为什么这在实践中是必要的,因为似乎从来没有检查过根节点的颜色。有人能指出我这里缺少什么吗?
在检查代码之后,我得出了与您相同的结论,即根颜色从未实际使用过。
因此,我进行了一些测试,试图证实这一点,在这个过程中,我发现该论文中的代码实际上有许多小错误:从未定义的方法调用,从未声明的变量赋值,昂贵的方法调用的不必要重复,未使用的对象引用(=指针),等等。
当然,这些都不是一个非常严重的问题,因为它们都不需要付出太多努力来解决;但我认为,只有当代码完美或近乎完美时,你的问题才会真正有意义,而这根本不是。考虑到代码有几十个编译错误和几个不涉及红黑语义的明显非最佳位,我认为争论是否真的需要以语义预期的方式设置根节点颜色是没有意义的。
但就其价值而言,我的测试表明根颜色确实无关紧要;我编写了一个验证方法来验证适当的不变量(没有红色非根节点具有红色子节点,并且所有叶节点都具有相等的黑色深度),并且我发现无论我是否注释掉行以将根颜色设置为黑色,这些都保留了。(当然,这只是我测试的案例,但仍然足以让我对结论更有信心。具体来说,我的情况涉及按顺序、反向顺序或随机随机排列顺序添加键 1 到 1000,然后按顺序、反向顺序或随机随机顺序删除它们。我在每次插入或删除后验证了不变量。
这对于标准的红黑树似乎没有什么不同:惯例是根应该是黑色的。这只不过是一个惯例,因为理论上根节点可以是(左)红色而不违反任何(其他)红黑树属性。这种颜色变化也不影响左倾红黑树的附加属性。
参见红黑树-维基百科中的属性#2:
简而言之:将根节点涂成黑色是不必要的,但这是惯例。
我认为这是因为你需要重建树,使树是AVL。插入新节点时,根节点可能会更改为另一个节点,并且需要为根重新着色。