1
$\begingroup$

I've been reading about fixing up after an insertion into a red black tree. (http://web.cse.ohio-state.edu/~lai/2331/0.Red-Black%20Trees.pdf)

The most surprising part is not that there are 6 things that we need to do after inserting into a red black tree. i.e. if both parent, uncle red, then parent, uncle black, grandparents red, replace inserted value with grandparent. The most surprising part is that wouldn't this blatantly mess up the BST ordering such that a node x is always greater than the left side and less than the right side?

In above link, page 10, the author just replaced grandparent with the newly inserted node x. Wouldn't this completely mess up the BST ordering? Can someone explain if BST ordering should be preserved in a red-black tree and why rotation/fix up after insertion will not have any affect on this ordering?

$\endgroup$
1
$\begingroup$

A correct implementation of red-black trees will maintain the BST ordering property. Whenever you add a node to the tree or delete a node from the tree you very carefully maintain this property. If you have to modify the structure of the tree then you do so in such a way that maintains the BST property.

I suggest you go carefully through the insertion and deletion pseudocode and verify that both operations maintain the BST property.

$\endgroup$
  • $\begingroup$ You deserve to be thumbbed up just for being alive $\endgroup$ – Olórin Oct 28 '14 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.