RBT Insertion Algorithm

1. Check if tree is empty.
2. If tree is empty, then insert node as root and change color to black.
3. If tree is not empty, insert node as a red leaf node and perform the appropriate repair operations.

Example of insertting a new node into an RBT.

Insertion Efficiency

Worst case O(log(n)).

For more information on Red Black Trees, you can visit https://pages.cs.wisc.edu/~cs400/readings/Red-Black-Trees/.