red-black-tree - 红黑树 - 没有假人的元素移除

Question

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

Answer 1

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

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

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