Red black tree is a type of self-balancing tree in which the nodes are colored either red or black. It is subject to following conditions:
1) The root is black.
2) A red node can have only black children
3) The black depth of each external node is the same.