Module 105
Here is your complete, exam-ready, beautifully organized notes for UNIT II – Advanced Data Structures (8 Lectures)
Perfect for university exams, interviews, and viva!
UNIT II – ADVANCED DATA STRUCTURES (Summary Table First – Must Remember!)
| Data Structure | Type | Insert | Delete | Search | Min/Extract-Min | Space | Used In / Best For |
|---|---|---|---|---|---|---|---|
| Red-Black Tree | Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | STL set/map (C++), Java TreeMap |
| B-Tree | Multi-way Tree | O(log n) | O(log n) | O(log n) | — | O(n) | Databases, File Systems (NTFS, ext4) |
| Binomial Heap | Heap (Forest) | O(log n) | O(log n) | — | O(log n) | O(n) | Dijkstra (better amortized) |
| Fibonacci Heap | Heap (Forest) | O(1) | O(log n) | — | O(1) amortized | O(n) | Fastest Dijkstra/Prim (theoretical) |
| Trie (Prefix Tree) | Tree (Radix) | O(m) | O(m) | O(m) | — | O(ALPHABET×keys) | Autocomplete, Dictionary, IP Routing |
| Skip List | Probabilistic | O(log n) expected | O(log n) exp | O(log n) exp | O(log n) | O(n) expected | LevelDB, Redis (ZSET), Concurrent maps |
1. RED-BLACK TREES (Most Important for Exams)
Properties (5 Rules):
- Every node is Red or Black
- Root is always Black
- All leaves (NIL) are Black
- Red node → both children Black (No two Reds adjacent)
- Every path from node to descendant leaves has same number of Black nodes
Operations: O(log n) guaranteed
Rotations + Recoloring to maintain balance
Use Case: std::map, std::set in C++, Java TreeMap/TreeSet
Insert Example (simple):
Insert 10, 20, 30 → Right-right case → Left Rotate + Recolor
2. B-TREES (Order m)
- Used in databases & file systems
- Each node can have up to m children, m-1 keys
- All leaves at same level
- Node: at least ⌈m/2⌉-1 keys (except root)
Operations: O(log n)
Node splitting & merging
Why B-Tree? → Minimizes disk reads (one node = one disk block)
3. BINOMIAL HEAPS
- Forest of binomial trees (B0, B1, ..., Bk)
- Each tree satisfies min-heap property
- At most one tree of each order
| Operation | Time Complexity |
|---|---|
| Insert | O(log n) |
| Find-Min | O(1) |
| Extract-Min | O(log n) |
| Decrease-Key | O(log n) |
| Merge (Union) | O(log n) |
Better than binary heap for Decrease-Key in Dijkstra
4. FIBONACCI HEAPS (King of Amortized Performance)
| Operation | Amortized Time | Worst Case |
|---|---|---|
| Insert | O(1) | O(1) |
| Find-Min | O(1) | O(1) |
| Extract-Min | O(log n) | O(log n) |
| Decrease-Key | O(1) | O(log n) |
| Delete | O(log n) | O(log n) |
| Union (Merge) | O(1) | O(1) |
Used in fastest theoretical Dijkstra & Prim
Structure: Circular doubly-linked list of trees + lazy merging
5. TRIE (Prefix Tree)
Best for string operations
Node contains:
- Array/Map of children (26 or dynamic)
- isEndOfWord flag
Operations:
- Insert: O(length)
- Search: O(length)
- StartsWith: O(prefix length)
Example:
Insert: "cat", "car", "cart", "dog"
Root
├── c
│ ├── a
│ │ ├── t → end
│ │ └── r → end
│ │ └── t → end
└── d
└── o
└── g → end
Applications:
- Autocomplete
- Spell checker
- IP routing (longest prefix match)
6. SKIP LISTS
“Probabilistic Alternative to Balanced BST”
- Multiple layers of linked lists
- Bottom layer = full list
- Each higher layer = “express lane” (50% nodes promoted randomly)
Expected Time: O(log n) for Insert/Search/Delete
Space: O(n)
Why used?
- Simple to implement
- Lock-free concurrent versions possible
- Used in Redis (Sorted Sets), LevelDB, Lucene
QUICK COMPARISON TABLE (Draw This in Exam!)
| Feature | RB Tree | B-Tree | F-Heap | Trie | Skip List |
|---|---|---|---|---|---|
| Guaranteed O(log n) | Yes | Yes | No | No | No (expected) |
| Worst-case Insert | O(log n) | O(log n) | O(log n) | O(m) | O(n) rare |
| Amortized O(1) ops | No | No | Yes | — | — |
| Disk-friendly | No | Yes | No | No | No |
| String operations | No | No | No | Yes | No |
| Concurrent-safe easy | Hard | Hard | Hard | Medium | Easy |
| Real-world usage | High | Very High | Rare | High | High |
One-Liner for Viva
| Structure | One-Liner Answer |
|---|---|
| Red-Black Tree | Self-balancing BST with O(log n) guaranteed operations |
| B-Tree | Multi-way tree for disk-based storage (DBs, filesystems) |
| Fibonacci Heap | Fastest amortized heap for Dijkstra/Prim |
| Trie | Prefix tree for fast string search/insert/delete |
| Skip List | Probabilistic layered list – simple alternative to balanced trees |
Bonus: Real-World Usage (2025)
| Data Structure | Where You See It Today |
|---|---|
| Red-Black Tree | C++ STL (map, set), Java (TreeMap), Linux kernel (scheduler) |
| B-Tree | MySQL (InnoDB), PostgreSQL, NTFS, ext4, MongoDB (WiredTiger) |
| Fibonacci Heap | Only in advanced algorithm courses & research |
| Trie | Redis (autocomplete), DNS, routers, compilers |
| Skip List | Redis (Sorted Sets), LevelDB/RocksDB, ConcurrentHashMap (Java) |
You now have complete Unit II notes – ready to score full marks in theory, practical, and viva!
Want handwritten-style PDF or colored diagram sheet? Just say!