🔴 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)
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:
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
-
Every node is red or black
-
Every path from root to NULL has same number of black nodes
-
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
-
Used in databases & file systems
Order of B-Tree (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:
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
