RedBlack Tree
Redblack tree

Invented by Rudolf Bayer in 1972

A node is either red or black

The root and leaves (NIL) are black

If a node is red, then its children are black

All path from a node to its NIL descendants contains the same number of black nodes.

Nodes require one storage bit to keep track of color

The longest path (root do farthest NIL) is no more than twice the length of the shortest path (root to nearest NIL).
 Shortest path: all black nodes
 Longest path: alternating red and black

Operations are O(log n) time complexity
 Search
 Insert (require rotation)
 Remove (require rotation)

Space complexity are O(n)