Red Black Tree

Wikipedia explanation

Basic Rules

• Every node is either red or black
• The root node is black
• The black height to every nil is the same
• Red parents can not have red children