2

我正在寻找如何在不使用虚拟节点(即叶节点实际上是空指针)的情况下实现删除红黑树中的元素的指南。我在 google/wikipedia 和标准文献(sedgewick 和 cormen 等)上找到的所有实现都使用虚拟 NIL 节点,我想避免这种情况。

4

1 回答 1

2

对于插入,冈崎的双红消除开箱即用。像往常一样插入 BST 并继续消除双红色直到到达根部。

删除红色节点从来都不是问题。请注意,永远不会从 BST 中删除具有两个子节点的节点。如果您删除一个带有一个子节点的黑色节点,请将子节点涂成黑色,然后就完成了。只有删除黑叶(真实的,而不是假的)是一个问题。Matt Might 的方法可以在没有虚拟节点的情况下工作。诀窍是首先将叶子变成红色,使用马特的“冒泡”。然后只需将其删除。

是一个带有代码的解决方案。

于 2011-05-12T10:48:27.393 回答