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:

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

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