Bounds on the number of rotations in the insertion operation of a Red Black Tree

Question

I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree.

From what I've gathered, there are several special cases to take into consideration in the fixUp algorithm posterior to the standard BST insertion on the tree. But from all those cases, only one will put the grand-parent node as red, so only this case may require subsequent work (if the grand-grand parent exists and is a red node).

Consider this (extreme) case:

This tree would force an lot of rotations, as the black nodes will keep moving down and creating a red-red collision upper in the tree.

I can only imagine that such a tree cannot effectively be built, so that this is not a situation that could feasibly arise?

Thanks

Answer 1

First of all, as pointed out in the comments, your tree is not a valid Red-Black tree. Here is why:

1. By definition, every path from the root of the tree to its leaves contains the exact same number of black nodes.
2. By definition, every red node has a black parent.

So, suppose you have a path with $n$ black nodes. How much longer can another path in this tree be? This other path has exactly $n$ black nodes too, so it can be longer only by having more red nodes. How many more? Well, you can add $n$ red nodes (in the alternating manner) to it (totalling $2n$ nodes) but as soon as you try to add $n + 1$ red nodes you are out of luck: some red node will have a red parent. Finally, this means that for any path in the tree there is no path that is more than twice as long.

Now, suppose you are looking at a subtree of a Red-Black tree. Also suppose that the root of this subtree is black (a formality). Then this subtree is also a Red-Black tree:

1. The root of the subtree is black (we chose it that way)
2. Every red node has a black parent (because it is so in the original tree)
3. Every path from the root of the subtree contains the same number of black nodes

The last statement is true because when we look at a subtree, we actually look at all the paths from the original tree that go through the root of the subtree. So, we essentially subtract the same number of black nodes which are above the root of the subtree.

Since the subtree is also a Red-Black tree, we already know that:

for any path in the tree there is no path that is more than twice as long

Now look at your drawing, consider the subtree in the intermediate black node. It should be a Red-Black tree, yet it is not. There are at least two reasons:

1. There is a path (left-left) with one black node and there is a path (left-right-right-left) with two black nodes.
2. There is a path with $2$ nodes and there is a path with $5$ nodes and since $ 5 > 2 * 2$ which breaks the height property.

---

Another mistake you are making: you are inserting a red node as a right child of a red node. This is the third insertion case according to wikipedia which triggers color propagation first, not a rotation. A rotation might or might not take place further up the tree.