红黑树 - 无dummys元素去除

Question

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

Answer 1

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

删除红色节点绝不是问题。请注意，从不从BST删除两个孩子的节点。如果您删除带有一个孩子的黑色节点，请将孩子涂黑并完成。只有黑叶（真正的，而不是假人）的删除是一个问题。 Matt Might's approach可以使无虚拟节点的工作。诀窍在于首先使用马特的“鼓泡”将叶子变成红色。然后简单地删除它。

Here是一个代码解决方案。