Red Black Trees

Rules:

• Each Node is red or black
• The root node is always black
• Red nodes cannot have red children
• Every path from a node to the descendant leaf node has the same number of black nodes