Red Back Tree

• Every node is either Red or Black
• root is Black
• No two consecutive Red
• number of Black nodes from every node to all of it's descendant leaves should be same