Red Black Trees

Red-Black Trees are binary search trees that are named after the way the nodes are coloured.

Each node in a red-black tree is coloured either red or black. The height of a red black tree is at most 2 * log(n+1).

A red black tree must maintain the following colouring rules:

1. every node must have a colour either red or black.
2. The root node must be black
3. If a node is red, its children must be black. null nodes are considered to be black.
4. Every path from root to null pointer must have exactly the same number of balck nodes.

Insertion

We will begin our look at Red-Black trees with the bottom up insertion algorithm. This insertion algorithm is similar to that of the insertion algorithm we looked at for AVL trees/Binary search trees. Insert the new node according to regular binary search tree insertion rules. New nodes are added as red nodes. "Fix" the tree starting at the parent of the newly inserted node so that none of the rules are violated.

General Insertion Algorithm

To insert into a red-black tree:

1) find the correct empty tree and insert new node as a red node. 2) working way up the tree back to parent fix the tree so that the red-black tree rules are maintained.

Fixing nodes:

1. If a node is red at the root, change it to black.
2. If the new node is red, and its parent is black you don't need to do anything.
3. If a new node is red and its parent is red, what you do depends on colour of sibling of the parent
   • if the sibling of the parent is black, a rotation needs to be performed
   • if the sibling of the parent is red, a color swap with grandparent must be performed