# 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:
1.  **Node Color:** Every node is either red or black.
2.  **Root Property:** The root is always black.
3.  **Leaf Property:** Every leaf (NIL) is black.
4.  **Red Property:** If a node is red, then both its children are black. (No two red nodes can be adjacent).
5.  **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:
1.  **Recoloring:** Changing a node's color from red to black or vice versa.
2.  **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]]