Red-Black trees - Erasing a node with two non-leaf children

Question

Hi all,

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?

Answer 1

If you have no prior knowledge about your input data, you cannot know which side is more benefitial of being the new intermediate node or the new child.

You can therefore just apply the rule that fits you most (is easiest to write/compute -- probably "always take the left one"). Employing a random scheme typically just introduces more unneeded computation.