Red-Black Trees

Red-Black Trees are a type of Binary Search Tree that are self-balancing!

Properties

• Every node must be red or black
• The root of the tree is always black
• All NIL leaf nodes are black
• No two consecutive red nodes
• Every path from root node to leaf must have the same number of Black Nodes

Red-Black Tree Wikipedia