Is Red-Black tree balanced

5
votes

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?

2
algorithmtreebinary-treered-black-tree
I think rb tree can become unbalanced up to 2 log n in depth. you should check this. a perfectly balanced tree is roughly log n in depth. unbalanced-ness in rb tree is not bad enough to screw up it's big O for various operations. – thang

2 Answers

14
votes

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.

3
votes

They are not balanced, because they do not satisfy the balanced tree property:

A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

Some books call it "approximately balanced", because guaranteed the logarithmic time add/delete/search operations. (The balanced trees are the AVL trees.)