Red-Black Trees

Red-Black trees are a self-balencing type of tree that gives each node a specific color: red or black

Requirments for balance

• Every node is either red or black
• The root node is always black
• Null child nodes are considered black
• A red node cannot have a red child node
• Every path from the root node to any of the bottom null nodes must have the same amount of black nodes

More information on how to fix a red-black tree violation