Search code examples
algorithmtreebinary-treered-black-tree

Is Red-Black tree balanced

I am studying red-black trees and I am reading the Cormen's "Introduction to Algorithms" book. Now I am trying to create red-black tree with numbers 1-10 by using the pseudo-code described in the book - RB-INSERT-FIXUP(T, z). Here is the screenshot enter image description here

Everything was fine until I inserted number "6" into the tree. According to pseudo-code I get the following result

enter image description here

As you can see all red-black tree requirements met, but I am confused because I know that red-black tree should be balanced on each step.

I can manually perform "left-rotate" procedure with "2" and "4" and change the colours. In that case I will get the following result, which is balanced appropriately

enter image description here

So my question is:

Is that all right to have unbalanced tree?, or I missed something during insertion nodes?

Solution

  • This is fine. Red-black trees are balanced, but not necessarily perfectly. To be precise, properties of red-black tree guarantee that the longest path to the leaf (implicit, not shown in your picture) is at most twice as long as the shortest. Shortest one has length 2 (2 -> 1 -> leaf), longest one has length 4 (2 -> 4 -> 5 -> 6 -> leaf), so the invariant does hold.