Red Black Tree

A binary tree that satisfies these properties:
1. Every node is either red or black.
2. Every leaf is black.
3. If a node is red, then both its children are black.
4. Every simple path from a node to a descendant leaf contains the same number of black trees.
By preserving these properties you create an approximately balanced tree that can be searched at O( lg n).

One of the primary problems of the Binary Search Tree data type in terms or search time is its worst case. If the items added to the BST are already sorted then they will always be added to the right most branch of the tree (or the left most, if inserted in reverse order). This will result in turning the BST in a simple Linked List, with the Node data type using up more memory than necessary to hold the null pointer to each empty branch.

This problem can be solved many ways, and one of which is to color the tree as a Red Black Tree. The Node data type, which would normally look like this:

struct node{
	int Num; // or some other variable
	node * left;
	node * right;
};

would instead be written as this

struct node{
	int Num;
	node * left;
	node * right;
	bool is_red;
};

Red Black Trees follow several rules:

1. Each leaf must have the same number of Black edges between it and the root as any other leaf (a leaf in this case is ANY node that has a null pointer).
2. A red colored node cannot have a red colored child.

When implementing a Red Black Tree it is not necessary to take into account the first rule, as the transformations required by the second rule will force everything to work out. Each of these transformations can be done two ways, the way it is shown, and the mirror. The letters a, b, c and d stand for single unique nodes and the numbers 1, 2, 3, and 4 stand for unique subtrees. The node and subtree designations are constant in each transformation diagram. A black edge is represented by either / or \, while red edges are #. A colored edge represents the color of the node directly below it.

Transformation Diagrams

Rotate Right

         /                      /
        c                      b
      #  \                   #   #
     b    4                 a     c
   #  \         -->        / \   / \
  a    3                  1  2  3   4
 /  \
1   2

Double Rotate Right

       /                      /
      c                       b
    #  \                    #   #
   a    4                  a     c
 /  #           -->       / \    / \
1    b                   1  2   3  4
    /  \ 
   2   3

Color Flip

       /                      #
     c                       b
   #   #                   /   \
  b     d                 b     d
 # \   / \      -->      # \   / \
a   1  2  3             a   1 2   3

Color Flip

      /                       #
     c                       c
   #   #                   /   \
  a     d                 a     d
 / #   / \     -->       / #   / \
1   b 2   3             1   b 2   3

The algorithm to implement this is large but simple. Whenever a new Red node is added, its parent is checked to see if it fits into the conditions of one of the four (eight with mirror images) transformations listed above. If so, then the transformation occurs, and the same check is performed on the uppermost node shown in the transformation. This process will cascade up the branch until the check does not find a case that fits one of the diagrams, which would mean the tree is correctly drawn.

As a side note, any AVL tree can be colored a Red Black Tree, although any Red Black Tree cannot necessarily be an AVL tree. Also, any Fibonacci tree can be colored as a Red Black Tree.