Red Black Trees

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

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 (note that this also implies that red nodes cannot have red parents)
4. Every path from root to a null node must have exactly the same number of black nodes

Note

null nodes are also sometimes called null leafs. these are not really nodes.. they are the "nodes" that null pointers point to...