Red Black BST

Red Black BST's are self balancing BSTs that contain "red" and "black" nodes

Rules of a Red Black Tree

• Every node is either red or black
• The root node is black
• No red nodes have red children
• Every path from root to a null child has the same number of black nodes
• Null children are black nodes