📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 2 – ADVANCED DATA STRUCTURES) university of allahabad

 

🔴 UNIT 2 – ADVANCED DATA STRUCTURES

---

1️⃣ AVL TREE (Adelson–Velsky and Landis Tree)

✅ Definition

An AVL Tree is a self-balancing Binary Search Tree (BST) where the height difference (balance factor) of left and right subtrees is at most 1.

---

✅ Balance Factor (BF)

$$BF = Height(left\ subtree) - Height(right\ subtree)$$

Allowed values:

• -1

• 0

• +1

---

✅ Rotations in AVL Tree

When balance factor becomes ±2, rotations are performed.

---

🔹 Types of Rotations

1. LL Rotation (Left-Left)

Occurs when:

• Insertion in left subtree of left child

✔ Single right rotation

---

2. RR Rotation (Right-Right)

Occurs when:

• Insertion in right subtree of right child

✔ Single left rotation

---

3. LR Rotation (Left-Right)

Occurs when:

• Left child has right-heavy subtree

✔ Left rotation + Right rotation

---

4. RL Rotation (Right-Left)

Occurs when:

• Right child has left-heavy subtree

✔ Right rotation + Left rotation

---

✅ Advantages

✔ Balanced tree
✔ Faster searching
✔ Time complexity: O(log n)

---

2️⃣ Red-Black Tree

✅ Definition

A Red-Black Tree is a self-balancing BST where each node is colored either red or black.

---

✅ Properties

1. Every node is red or black

2. Root is always black

3. Red node cannot have red child

4. Every path from root to NULL has same number of black nodes

5. Leaf nodes are black

---

✅ Advantages

✔ Less rotations than AVL
✔ Faster insertion and deletion
✔ Used in STL, Java TreeMap

---

🔹 Comparison: AVL vs Red-Black Tree

Feature	AVL Tree	Red-Black Tree
Balancing	Strict	Less strict
Speed	Faster search	Faster insert/delete
Rotations	More	Less
Use	Search-heavy	Insert-heavy

---

3️⃣ B-Trees

✅ Definition

A B-Tree is a self-balancing tree designed for disk storage systems.

---

✅ Properties

• All leaves at same level

• Multiple keys per node

• Used in databases & file systems

---

Order of B-Tree (m):

• Max children = m

• Min children = ⌈m/2⌉

---

Example:

B-Tree of order 3:

• Max keys = 2

• Min keys = 1

---

Advantages:

✔ Reduces disk access
✔ Balanced structure
✔ Efficient searching

---

4️⃣ Binomial Heap

✅ Definition

A Binomial Heap is a collection of binomial trees.

---

Properties:

• Each binomial tree follows min-heap property

• No two trees have same degree

---

Operations:

• Insert

• Merge

• Delete minimum

• Find minimum

---

Time Complexity:

Operation	Time
Insert	O(log n)
Merge	O(log n)
Delete min	O(log n)

---

5️⃣ Fibonacci Heap

✅ Definition

A Fibonacci Heap is an advanced heap structure used in graph algorithms.

---

Advantages:

✔ Faster decrease-key operation
✔ Used in Dijkstra & Prim algorithms

---

Time Complexity:

Operation	Time
Insert	O(1)
Decrease key	O(1)
Extract min	O(log n)

---

6️⃣ Comparison of Heaps

Feature	Binary Heap	Binomial Heap	Fibonacci Heap
Insert	O(log n)	O(log n)	O(1)
Delete Min	O(log n)	O(log n)	O(log n)
Merge	O(n)	O(log n)	O(1)
Complexity	Simple	Moderate	Complex

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 2)

✔ Explain AVL Tree with rotations
✔ Explain Red-Black Tree
✔ Difference between AVL & RB Tree
✔ Explain B-Tree
✔ Explain Fibonacci Heap
✔ Applications of heaps