What is a Red-Black Tree

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

Steps in the Insertion of a Node in a Red-Black Tree

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