algorithm - 红黑树 - 删除具有两个非叶子节点的节点

Question

我一直在实现我自己的红黑树版本，主要基于维基百科 (http://en.wikipedia.org/wiki/Red-black_tree) 的算法。它的大部分内容相当简洁，但有一部分我想澄清一下。

当从具有 2 个非叶(非 NULL)子节点的树中删除一个节点时，它表示将任一侧的子节点移动到可删除节点中，然后删除该子节点。

基于此，我对从哪一侧移除有点困惑。我是随机选择一边，在两边之间交替，还是在以后每次删除时都坚持同一边？

Answer 1

如果您对输入数据没有先验知识，就无法知道哪一方作为新的中间节点或新的子节点更有利。

因此，您可以只应用最适合您的规则(最容易编写/计算——可能是“总是取左边的”)。采用随机方案通常只会引入更多不需要的计算。