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!)

1. RED-BLACK TREES (Most Important for Exams)

Properties (5 Rules):
1. Every node is Red or Black
2. Root is always Black
3. All leaves (NIL) are Black
4. Red node → both children Black (No two Reds adjacent)
5. 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

Better than binary heap for Decrease-Key in Dijkstra

4. FIBONACCI HEAPS (King of Amortized Performance)

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!)

One-Liner for Viva

Bonus: Real-World Usage (2025)

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!