Major Trees in Algorithms

• AVL Tree emphasizes “height balance” for fast lookups.
• Red-Black Tree trades off strict balance for insertion efficiency, used in many libraries (e.g., TreeMap, HashMap).
• Huffman Tree focuses on “optimal coding,” commonly used in compression algorithms (ZIP, JPEG, MP3, etc.).

---

🌳 1. AVL Tree (Balanced Binary Search Tree)

1.1 Definition

An AVL Tree (Adelson-Velsky and Landis Tree) is one of the earliest self-balancing binary search trees (BSTs). It satisfies the balance condition at every node:

For any node, the height difference between the left and right subtree (balance factor) ≤ 1.

| height(left) - height(right) | ≤ 1

If insertion or deletion breaks the balance, rotations are used to restore it.

---

1.2 Structure Example

An AVL tree satisfies both BST properties:

Left subtree < Root < Right subtree

and maintains “near-perfect balance”:

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

---

1.3 Balance Adjustment (Rotations)

AVL trees rely on rotations. There are four types:

Type	Meaning	Diagram
LL	Inserted node in left subtree's left	Right rotation
RR	Inserted node in right subtree's right	Left rotation
LR	Inserted node in left subtree's right	Left-Right rotation
RL	Inserted node in right subtree's left	Right-Left rotation

Example: LL case (Right Rotation)

Before rotation:

      5
     /
    3
   /
  2

After right rotation:

     3
    / \
   2   5

---

1.4 Time Complexity

Operation	Complexity
Search	O(log n)
Insert	O(log n) + rotations
Delete	O(log n) + rotations

---

1.5 Pros, Cons & Use Cases

Pros:

• Strictly balanced → high and stable lookup speed.

Cons:

• Frequent rotations for insert/delete → higher maintenance cost.

Use cases:

• Systems where reads dominate writes (indexes, caches, search trees).

---

🔴 2. Red-Black Tree

2.1 Definition

A Red-Black Tree is a roughly balanced BST. Insertions and deletions maintain balance using coloring + local rotations. It is not perfectly balanced but guarantees the longest path ≤ 2 × shortest path.

---

2.2 Properties (5 Rules)

1. Each node is either red or black.
2. The root is black.
3. All leaves (NIL nodes) are black.
4. If a node is red, both its children are black (no consecutive red nodes).
5. Every path from a node to its leaves contains the same number of black nodes.

---

2.3 Example

A valid red-black tree:

        10(B)
       /     \
   5(R)       15(R)
  /  \        /   \
2(B) 7(B)   12(B) 18(B)

---

2.4 Balancing on Insert/Delete

Red-black balancing is more complex than AVL because of color constraints. Key techniques:

• Recoloring
• Left rotation
• Right rotation

Common insertion cases:

Case	Description	Action
Uncle is red	Recolor parent and uncle black, grandparent red	–
Uncle is black, inner child insertion	Rotate to convert to “outer”	Double rotation
Uncle is black, outer child insertion	Single rotation + recolor	–

---

2.5 Time Complexity

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

Maximum height ≈ 2 * log2(n+1), providing stable performance.

---

2.6 Pros, Cons & Use Cases

Pros:

• Balanced with fewer rotations.
• Faster insert/delete than AVL.
• Suitable for frequently modified structures.

Cons:

• Lookup slightly slower than AVL (not perfectly balanced).

Applications:

• Java TreeMap and TreeSet
• Java 8 HashMap uses red-black trees for collision chains
• Linux CFS scheduler, epoll
• C++ STL std::map / std::set

---

🟢 3. Huffman Tree

3.1 Definition

A Huffman Tree is a weighted path tree (optimal binary tree) used for optimal coding. Primarily applied in data compression.

---

3.2 Core Idea

Goal:

Assign shorter codes to high-frequency characters and longer codes to low-frequency characters, minimizing average code length.

---

3.3 Construction Process

Example characters with frequencies:

Char	Weight
A	5
B	9
C	12
D	13
E	16
F	45

Steps:

1. Treat all characters as individual nodes.
2. Repeatedly merge the two nodes with the smallest frequencies, creating a new node with weight = sum of the two.
3. Repeat until a single root node remains → Huffman Tree.

---

3.4 Example Codes

Assign 0 for left and 1 for right traversal:

Char	Code
F	0
C	100
D	101
A	1100
B	1101
E	111

The average code length is minimized → optimal compression.

---

3.5 Applications

Pros:

• Minimizes average code length → efficient compression.

Applications:

• File compression (ZIP, GZIP, JPEG, MP3)
• Transmission coding (Huffman encoding in communications)

---

⚖️ 4. Comparison

Feature	AVL Tree	Red-Black Tree	Huffman Tree
Type	Balanced BST	Approximately balanced BST	Optimal binary tree (not BST)
Balance	Strict	Approximate	Not required
Adjustment	Rotations	Rotations + recoloring	Merge smallest nodes
Search	High O(log n)	Slightly lower O(log n)	Not used
Insert/Delete	Slower (more rotations)	Faster (fewer rotations)	Built once
Use Case	Indexes, search trees	TreeMap, HashMap, etc.	Compression, encoding
Design Goal	Fast lookup	Balanced insert/delete	Minimum code length

---

🧠 5. Summary

• AVL Tree: emphasizes height balance → fast lookup, slower insertion.
• Red-Black Tree: moderate balance → overall performance optimized, widely used in libraries.
• Huffman Tree: optimal coding → unrelated to search.

They represent three optimization strategies in data structures:

Balance → Stability → Optimal coding.