You have a Black-Red Tree of height h that has two childs:

  • Left child is a full binary tree of height h-1
  • Right child is a full binary tree of height h-3

Balance the tree so both childs of root are of the same height (you don't have to keep the other nodes balanced, just the root).

From Wikipedia I understood that:

When a subtree is rotated, the subtree side upon which it is rotated increases its height by one node while the other subtree decreases its height. This makes tree rotations useful for rebalancing a tree.

So the solution would be to right-rotate the root, and then the left and right childs' heights will become h-2.

However it doesn't work well: right-rotate

The left child node height did decrease by one, but the right child node increased by two!

  1. Why is it happening? Is wikipedia wrong?
  2. How can I do it otherwise?
  • $\begingroup$ Do you understand how B-trees work? $\endgroup$
    – Raphael
    Feb 25 '17 at 9:54
  • $\begingroup$ @Raphael Not really, I'm talking about red-black trees here. $\endgroup$
    – iTayb
    Feb 25 '17 at 10:18
  • $\begingroup$ @iTayb: What you're missing is that each of the white nodes in your diagram is actually the root of some subtree. Rotations rebalance the global height. If you're talking about RB-trees, then you don't have to worry about heights at all: as long as the colors are properly assigned, the tree is balanced. Rotations in RB-trees are only supposed to preserve the invariant. $\endgroup$
    – quicksort
    Feb 25 '17 at 11:49
  • $\begingroup$ @quicksort Sorry, i don't get what you mean. I'm also talking about the global height. I know that I don't need to care about rotations, but this specific question is about how to make the left and right childrens of the root to have the same height. I thought that rotations might come handy here, because I can't think of another way to do it. I might be wrong. $\endgroup$
    – iTayb
    Feb 25 '17 at 12:29
  • $\begingroup$ @iTayb Too bad, because RB-trees are basically a special case of B-trees, written in a convoluted way. See also here. Personally, I find B-trees easier to understand, and then RB-trees follow. $\endgroup$
    – Raphael
    Feb 25 '17 at 19:15

Your Answer

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

Browse other questions tagged or ask your own question.