Red Black Trees

What is a Red Black Tree?

A Red Black Tree is a type or sorting method of a Binary Search tree to keep the tree balanced and to keep the objects within the tree sorted. Red Black Trees follow a specific set of rules to accomplish this. If a Red Black Tree does not follow these rules, it means that the Tree is not balanced and therefore must be rotated or recolored as corrections for the imbalance.

The Rules of the Red Black Tree:

• Each Node must be either Red or Black
• The Root Node must be Black
• No Red nodes may have Red Child Nodes
• Every path from the Root Node to a Null Child must have the same number of Black Nodes

How does it stay self balancing?

The Red Black Tree stays self balancing by checking the rules after every insetion or deletion of a node. Insetion and deletion algorithm diagrams are shown below to help show what the Tree must do if it is out of balance.