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

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

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

So my question is:

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

回答1:

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.

回答2:

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.)