The intuition of red-black tree

Question

I wanted to understand how red-black tree works. I understood the algorithm, how to fix properties after insert and delete operations, but something isn't clear to me. Why red-black tree is more balanced than binary tree? I want to understand the intuition, why rotations and fixing tree properties makes red-black tree more balanced.

Thanks.

Answer 1

Suppose you create a plain binary tree by inserting the following items in order: 1, 2, 3, 4, 5, 6, 7, 8, 9. Each new item will always be the largest item in the tree, and so inserted as the right-most possible node. You "tree" would look like this:

1
 \
  2
   \
    3
     .
      .
       .
        9

The rotations performed in a red-black tree (or any type of balanced binary tree) ensure that neither the left nor right subtree of any node is significantly deeper than the other (typically, the difference in height is 0 or 1, but any constant factor would do.) This way, operations whose running time depends on the height h of the tree are always O(lg n), since the rotations maintain the property that h = O(lg n), whereas in the worst case shown above h = O(n).

For a red-black tree in particular, the node coloring is simply a bookkeeping trick that help in proving that the rotations always maintain h = O(lg n). Different types of balanced binary trees (AVL trees, 2-3 trees, etc) use different bookkeeping techniques for maintaining the same property.

Answer 2

Why red-black tree is more balanced than binary search tree?

Because a red-black tree guarantees O(logN) performance for insertion, deletion and look ups for any order of operations.

Why rotations and fixing tree properties makes red-black tree more balanced?

Apart from the general properties that any binary search tree must obey, a red-black tree also obeys the following properties:

1. No node has two red links connected to it.
2. Every path from root to null link has the same number of black links.
3. Red links lean left.

Now we want to prove the following proposition :

Proposition. Height of tree is ≤ 2 lg N in the worst case.

Proof. Since every path from the root to any null link has the same number of black links and two red links are never in-a-row, the maximum height will always be less than or equal to 2logN in the worst case.

Answer 3

Although quite late , but since I was recently studying RBT and was struggling with the intuition behind why some magical rotation and coloring balances the tree and was thinking the same question as the OP

why rotations and fixing tree properties makes red-black tree more balanced

After a few days of "research" , I had the eureka moment and decided to write it in details . I won't copy paste here as some formatting would be not right , so anyone who is interested , can check it from github . I tried to explain with a lot of images and simulation . Hope it helps someone someday who happens to trip in this thread searching the same question : )