Red-Black tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black.
Red-Black Tree Properties
Root Property: The root is black.
Red Property: If a red node has children then, the children are always black.
Black Height Property: For each node, any simple path from this node to any of its descendant leaves has the same black-depth.
