A red-black tree is a self-balancing binary search tree. Every node is
colored red or black, and a few simple rules keep the tree balanced so that
search, insert and delete all run in O(log n) time.
The rules
Every node is either red or black.
The root is black.
A red node never has a red child.
Every path from a node to its null descendants has the same number of black nodes.
