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:

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 :)