Red-Black Tree

A self-balancing binary search tree that maintains the following properties:

• Every node is red or black
• A red node cannot have a red child
• Every node has a black height
• The root node is always black

Operations:

• Rotation
• Recoloring
• Insert
• Delete

More information: Red-Black Tree Wikipedia Page