Red-Black tree is a binary search tree where
every node is colored with either red or black.
It is a type of self-balancing binary search tree,
meaning that the tree adjusts itself automatically
after insertion or deletion. To maintain balance, it
colors each node in the tree either red or black.
More information about Red-Black trees can be found
at
Introduction to RBT.

A typical Red-Black tree
looks like the following

- Follow the usual Binary Tree insert
- Mark the newly inserted node red
- If its parent is black, then you are done