Red Black Trees

Red black trees are a binary search tree where every node is either colored red or black. In order to be considered one, it must abide to the following rules:

• The root is black
• All nodes are either colored red or black
• Red nodes are not adjacent to one another
• Every path from a node to its null descendant have the same number of black nodes
• All null leaves are colored black

Insertion

There are two important factors when inserting a node into a red black tree: Recoloring and Rotating. The new node must be added as a leaf in its corresponding position and assigned the color red. Then, the tree is adjusted to follow the rules of a valid red black tree, depending on the cases that may appear.

• If the node's aunt is red, the parent and uncle are recolored to black while the grandfather is recolored to red.
• If the node's aunt is black, recoloring must take place as well as rotations

For a more in-depth read on this topic: Introduction to Red Black Trees