Red-Black Tree (RBT)

A Red-Black Tree is a type of self-balancing binary search tree. It ensures that no path is more than twice as long as any other, guaranteeing O(log n) search, insertion, and deletion times.

Key Properties

• Every node is either red or black.
• The root is always black.
• No two consecutive red nodes appear on any path.
• All paths from a node to its descendant NIL nodes have the same black height.

Insertion Process

1. Insert a new node as in a regular BST and color it red.
2. If the parent is black, you’re done.
3. If the parent is red, perform a color flip or a rotation to restore balance.

Visualization Example

For more details, see the Wikipedia article on Red-Black Trees .