Red-Black Trees
A Red-Black Tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
1. Properties (The Invariants)
To be a valid Red-Black Tree, it must satisfy these five properties:
- Node Color: Every node is either red or black.
- Root Property: The root is always black.
- Leaf Property: Every leaf (NIL) is black.
- Red Property: If a node is red, then both its children are black. (No two red nodes can be adjacent).
- Depth Property: For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
2. Why use them?
Standard Binary Search Trees (BST) can become skewed (like a linked list) in the worst case, degrading operations to $O(n)$. Red-Black trees guarantee that the height of the tree is approximately $\log n$, ensuring that operations like search, insert, and delete always take $O(\log n)$ time.
3. Operations & Complexity
| Operation | Time Complexity |
|---|---|
| Search | $O(\log n)$ |
| Insert | $O(\log n)$ |
| Delete | $O(\log n)$ |
| Space | $O(n)$ |
4. Balancing (Rotations & Recoloring)
When you insert or delete a node, the properties might be violated. To restore them, the tree performs two types of operations:
- Recoloring: Changing a node's color from red to black or vice versa.
- Rotations: Changing the structure of the tree (Left Rotation or Right Rotation) to reduce height.
5. Red-Black vs. AVL Trees
Both are self-balancing BSTs, but they have different trade-offs.
- AVL Trees: More strictly balanced. Faster lookups, but slower insertion/deletion due to more frequent rotations.
- Red-Black Trees: Less strictly balanced. Faster insertion/deletion, but slightly slower lookups.
Use Cases:
- Red-Black: Used in most language standard libraries (e.g., Java's
TreeMap, C++std::map). - AVL: Used in databases where lookups are much more frequent than updates.
programming/binary-search-trees programming/avl-trees programming/algorithms