Red-Black Trees

Key Properties

• Maintains a balanced height
• Each node is colored red or black
• All leaves (NIL nodes) are black