# Red Black Tree Insertion

## About Red Black Trees

Red Black Trees (RBTs) are data structures that hold nodes in a binary search tree with additional constraints put on the structure. Those include:

- every node is either red or black
- red nodes cannot have red children
- the root node is always black
- the black height of a node (the number of black nodes passed while traversing down to a leaf) is constant along any path

These criteria produce some interesting properties of RBTs, namely that their height is always O( log n ) complexity, which is only the best case scenario for general BSTs.

## Insertion Algorithm

To insert a node into a Red Black Tree, simply follow these steps:

- Use the BST insert algorithm at first, inserting the new node as red.
- Then, repair any red node with red child violations.
- Finally, set the root node to black.

This should result in a valid RBT with no property violations! Happy coding :)