Red Black Trees Overview

Red Black Trees are a niche type of Binary Search Tree's that uses rotation and color change operations to auto balance a tree containing red and black nodes.

Visual Example

Red Property

In order to keep a tree balanced we must maintain the red node property. Every new node inserted is a red node and red nodes can not have red children.

Black Property

The black property also must be maintained to keep the tree balanced. The root node must always be black and the amount of black nodes to the first null nodes at the bottom must be equal. Additionally all null nodes should be considered black.

Steps

1. Insert new node as a red node. If it is the first node recall black because its the root.
2. If a red or black property is detected utilize the insertion chart below to determine the case and rotate, recolor, and color swap accordingly.
3. Now if you wanted to delete a node in a tree you should replace that node with its in order sucessor.
4. If you detect a violation use the deletion chart below to determine the case and operate accordingly.

Insertion Visualization

Deletion Visualization

Learn More

See a more in depth explanation at Wikipedia.