Red-black Trees

Red-black trees are a height-balanced binary search tree, much like 2-3 trees and AVL trees. Its distinguishing properties are as follows:

  1. Every node has a color, red or black (in numeric terms, a 0 or 1).
  2. The tree's root is always black.
  3. The null nodes are always black.
  4. If a node is red, then its parent and its chilren must be black.
  5. All newly inserted nodes are initially red.
  6. The height H{\H} of a red-black tree is bounded as follows:
    lg⁡n<=H<=2lg⁡n \lg n \lte \H \lte 2 \lg n

Insertion

To illustrate insertion, we use the following set of keys:

{ 10,20,30,50,40,60,70,80,4,8 } \set{10,20,30,50,40,60,70,80,4,8}

Start with the first key, 10. This creates the node:

Note that this node must have the color black, per Property 2. Next, we insert the key 20:

Then we insert the key 30:

Now we've run into trouble. Under Property 4, that 30 must be black. This situation is called a red-red conflict. For brevity, we'll call the node causing this conflict — here, 30 — the rascal. Red-red conflicts are resolved through recoloring and rotation. We examine each in turn.

Recoloring

The easiest approach is recoloring. To illustrate this approach, suppose we had the following tree:

Above, we have a red-red conflict resulting from the rascal n.{n.} n{\n} has the parent p,{\p,} the pibling u,{\u,} and the grandparent g.{\g.} In recoloring, we perform the following procedure:

  1. Starting from the rascal to the root:
    1. Change p{\p}'s color to black.
    2. Change u{\u}'s color to black.
    3. Change g{\g}'s color to red, unless g{\g} is the root.

The end result:

Rotation

Recoloring only addresses the situation where the rascal has a pibling. It does not address the situation where the rascal has no piblings. There are two such cases:

case 1
case 2

For both cases, we must rotate, similar to how rotations are done with AVL trees. In case 1, we perform a zig-zig rotation, and in case 2, we perform a zig-zag rotation. The end result for both:

In sum, we have the following requirements during the insertion process:

  1. If a red-red conflict occurs, do the following:
    1. If the rascal has a black pibling, perform a recoloring.
    2. Else:
      1. If the rascal is the left-child of its parent, perform a zig-zig rotation.
      2. If the rascal is the right-child of its parent, perform a zig-zag rotation.

Returning to our insertion process, we see that the rascal has no pibling and is the right-child of its parent. So, we perform a zig-zag rotation (equivalent to the RR-rotation we saw with AVL trees).

Now we add the next key, 50:

We have another red-red conflict. This time, the rascal has a pibling, and thati pibling is red. Accordingly, we perform a recoloring:

Now we insert the next key, 40. This node becomes the left-child of 50:

We get another red-red conflict. The parent is red, and the rascal 40 has no piblings. So, we perform a zig-zag rotation: