What is a Red-Black Tree?

What is a Red-Black Tree?

Approach: Define a self-balancing binary search tree.

A self-balancing binary search tree where each node has a color (red or black). The colors and specific rules (e.g., the root is black, no two reds are adjacent) ensure the tree remains approximately balanced, guaranteeing O(log n) operations.

Follow-up: Compare it to an AVL tree.

Key concepts: balancing, rotations, height O(log n).