Menu
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?
512
Every path from the root to a leaf has the same amount of red links. A node never has two red links to his childs. Using a red-black tree, you can always draw the associated 2-3 tree.
Deleting a node outright would shorten at least one simple path from root to leaf. If the node we deleted was red, we will not have disturbed this property, however if we delete a black node we will destroy this property.
What is the time complexity of deletion in Red-Black Tree? It takes O(log N) time, where N is the number of nodes in the red-black tree.
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.
96
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
