Red and black trees. Erasing a node with two non-leaf children.

Question

I implement my own version of the red-black tree, mainly basing my algorithms from Wikipedia ( http://en.wikipedia.org/wiki/Red-black_tree ). Its quite brief, for the most part, but there is one part that I would like to clarify.

When deleting a node from a tree in which there are 2 non-leaf (non-NULL) children, it is said that they move the children of each side to the deleted node and delete this child.

I am a little confused as to which side to remove, based on this. Do I randomly select a side, do I alternate between the sides, or do I stick to the same side for each subsequent deletion?

Answer 1

If you do not have any prior knowledge about your input, you cannot know which side is more beneficial to be a new intermediate node or a new child.

That way, you can just apply the rule that suits you best (the easiest way to write / compute - perhaps "always take the left one"). Using a random scheme usually introduces more unnecessary calculations.