1
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ This subtree is impossible because every red node in a red-black tree must have two black children, which essentially makes it impossible to have two or more consecutive red nodes. Also, as is well-proven, the constraints of a red-black tree make it impossible for the path from the root to the farthest leaf to be more than twice as long as the path from the root to its nearest leaf. $\endgroup$ – Francesco Gramano Aug 14 '15 at 23:40
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.