# 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