---

Red–Black Trees — Detailed Explanation

A Red-Black Tree (RBT) is a type of self-balancing Binary Search Tree that ensures efficient operations (search/insert/delete in O(log n)) by maintaining color-based balancing rules.

It is widely used in programming libraries (e.g., C++ STL map/set, Java TreeMap, Linux kernel) because it provides good balancing with fewer rotations compared to AVL Trees.

---

1. Why Red-Black Tree?

A normal BST can become skewed → poor performance (O(n)).
AVL Trees are strictly balanced but require many rotations.

Red-Black Trees offer faster insertion and deletion with fewer rotations, giving a good compromise between strict balancing and performance.

---

2. Properties of Red-Black Tree

Every Red-Black Tree satisfies five important properties:

Property 1 — Every node is either red or black.

Property 2 — Root is always black.

Property 3 — All NULL (leaf) nodes are black.

(Red-Black Trees treat NULL children as black leaves.)

Property 4 — No two red nodes can be adjacent.

A red node cannot have a red parent.

Property 5 — Every path from a node to its descendant NULL leaves has the same number of black nodes.

This is called the Black Height.

---

Effect of These Rules

• Prevents long chains of red nodes → tree doesn’t become skewed.
• Guarantees tree height is O(log n).

---

3. Basic Concepts

3.1 Black Height

Black height of node X = number of black nodes on any path from X to a leaf (excluding X).

All paths must have same black height.

---

3.2 Rotations

Rotations maintain the BST structure and reduce imbalance:

• Left Rotation
• Right Rotation

They work exactly like AVL rotations but are used less often.

---

3.3 Recoloring

Red ↔ Black color changes used to fix violations after insert/delete.

---

4. Violations in Red-Black Trees

A violation occurs when:

1. A red node has a red parent → “red-red conflict”
2. Black height imbalance

Two actions to fix:

• Recoloring
• Rotations

---

5. Insertion in Red-Black Tree

Default: New node is always inserted RED
(Because inserting as black may violate black-height property.)

Steps of Insertion

1. Insert like a BST.
2. Color new node RED.
3. Fix violations using:
   • Case 1 – Recoloring
   • Case 2 – Rotation (LL, RR)
   • Case 3 – Rotation + Recoloring (LR, RL)

---

Insertion Fix-Up Cases

Case 1 — Parent is Red, Uncle is Red

• Recolor parent and uncle to BLACK
• Recolor grandparent to RED
• Move pointer to grandparent and continue fixing

      G(B)            G(R)
     /   \    →      /   \
  P(R)  U(R)      P(B)  U(B)

---

Case 2 — Parent is Red, Uncle is Black → “Structural Violation”

Rotation required.

Case 2A — Left-Left (LL)

     G                   P
    /         →         / \
   P                   N   G
  /
 N

• Right rotate on G
• Swap colors of P and G

---

Case 2B — Right-Right (RR)

 G                      P
  \        →           / \
   P                  G   N
    \
     N

• Left rotate on G
• Swap colors of P and G

---

Case 3 — Parent is Red, Uncle is Black → “Triangle Case”

Rotation + Recoloring

Case 3A — LR Case

• Left rotate on parent
• Then Right rotate on grandparent
• Recolor appropriately

Case 3B — RL Case

• Right rotate on parent
• Then Left rotate on grandparent
• Recolor appropriately

---

6. Deletion in Red-Black Tree

Deletion is more complex than insertion.

Steps:

1. Delete node like in a BST.
2. If a BLACK node is removed → black-height property may break.
3. Fix using:
   • Recoloring
   • Rotations

Deletion fix-up deals with:

• Double Black
• Sibling being red/black
• Sibling’s children colors

---

7. Runtime Complexity

Operation	Time Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Space	O(n)

---

8. Advantages of Red-Black Trees

✔ Fewer rotations than AVL Trees
✔ Insertion & deletion faster in practice
✔ Height always O(log n)
✔ Used widely in real-world libraries
✔ Good performance for large dynamic data

---

9. Disadvantages

✘ Less strictly balanced than AVL Trees
✘ Searching slightly slower than AVL Trees
✘ Implementation is more complex

---

10. Red-Black Tree vs AVL Tree (Summary)

Feature	AVL Tree	Red-Black Tree
Balancing	Strict	Relaxed
Search	Faster	Slightly slower
Insert/Delete	Slower	Faster
Rotations	More	Fewer
Use Cases	Databases, indexing	Language libraries, OS kernels

---

11. Applications of Red-Black Trees

• C++ STL map, set
• Java TreeMap, TreeSet
• Linux kernel scheduler
• File systems
• Network routing tables
• Associative arrays
• Dictionaries
• Priority search trees

---