Red Black Tree

Red-black tree is a Binary search tree that has each node is colored either red or black.
Properties of red black tree:
1. This is the same as for binary search trees: all the keys
     to left of a node are smaller, and a to the right of a node are
     larger than the node key
2.The number of black nodes on every path from the root
     to each leaf is the same.  This is called as the black height of the tree.
3. No two consecutive nodes are red.

Red Black Tree

 Red Black tree ensure that the longest path from the root to a leaf is at most twice as long as the shortest path.  Since insertion and searching  in a binary search tree have time proportional to the length of
the path from the root to the leaf, this is sure that O(log(n)) times for these
operations, even if the  red black tree is not perfectly balanced.