Red-Black Trees
A red-black tree (RB-tree) is a type of self-balancing BST. It is complex, but has a good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is the total number of elements in the tree.
  • In RB-trees, the leaf nodes are not relevant and do not contain data. A null child pointer can encode the fact that this child is a leaf.
  • Like BSTs, RB-trees allow efficient in-order traversals of elements.
  • The search time on a RB-tree results in O(log n) time.

Properties:

A RB-tree is a BST where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on BSTs, the following additional requirements apply to RB-trees:

  1. A node is either red or black.
  2. The root is black.
  3. All leaves are black.
  4. Both children of every red node are black.
  5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

The above constraints enforce a critical property of RB-trees:

  • The longest path from the root to any leaf is no more than twice as long as the shortest path from the root to any other leaf in that tree.
  • The result is that the tree is roughly balanced.
  • Insertion, deletion, and search require worst-case time proportional to the height of the tree, the theoretical upper bound on the height allows RB-trees to be efficient in the worst case.

To see why these properties guarantee this, it suffices to note that no path can have two red nodes in a row, due to property 4. The shortest possible path has all black nodes, and the longest possible path alternates between red and black nodes. Since all maximal paths have the same number of black nodes, by property 5, this shows that no path is more than twice as long as any other path.

Insertions and removals are quite complex in a RB-tree in order to keep the properties.

Insertion:

Insertion begins by adding the node as any BST insertion does and by coloring it red. It's a red inner node with two black leaves.

  • Property 3 (all leaves are black) always holds.
  • Property 4 (both children of every red node are black) is threatened only by adding a red node, repainting a black node red, or a rotation.
  • Property 5 (all paths have same number of black nodes) is threatened only by adding a black node, repainting a red node black (or vice versa), or a rotation.

In the following description, we have labels N (current node), P (N's parent), G (N's grandparent), and U (N's uncle).

  • Case 1: N is root. It's repainted black to satisfy property 2.
  • Case 2: P is black. Property 4 (children of red are black) is not violated. Property 5 holds since N has two black leaf children, but N is red.
  • Case 3: if both P and U are red, repaint them black and repaint G red. Recursively insert G.

  • Case 4: P is red, but U is black; N is the right child of P, and P is the left child of G. Perform left rotation on P. Then go to Case 5.

 

  • Case 5: right rotation. Repaint G and P.

 

For deletion on a RB-Tree, please see the Wikipedia link for details.

Let's try it out with the following sequence of values: 14, 17, 11, 7, 53, 4, 13, 12, and 8.