Red-Black trees - Erasing a node with two non-leaf children
- by SalamiArmi
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 betweek sides, or do I stick to the same side for every future deletion?