5

I've been implementing my own version of a red-black tree, mostly basing my algorithms from Wikipedia (http://en.wikipedia.org/wiki/Red-black_tree). Its fairly concise for the most part, but there's one part that I would like clarification on.

When erasing a node from the tree that has 2 non-leaf (non-NULL) children, it says to move either side's children into the deletable node, and remove that child.

I'm a little confused as to which side to remove from, based on that. Do I pick the side randomly, do I alternate between sides, or do I stick to the same side for every future deletion?

4

1 回答 1

5

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

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

于 2010-04-03T09:00:16.123 回答