Advanced Data Structures: AVL Trees, B-Trees, Tries, Graph Algorithms & Applications

TAKEAWAYS:

• AVL trees maintain balance via rotations after insertions/deletions, ensuring $O(\log n)$ operations for dynamic datasets.
• B-trees optimize disk-based storage (e.g., databases) by reducing node accesses via multi-way branching.
• Tries excel at prefix-based searches (e.g., autocomplete) with $O(L)$ time per operation, where $L$ is key length.
• Graph algorithms (Dijkstra, Prim, Kruskal) solve shortest-path and minimum-spanning-tree problems critical for networks (e.g., NTC’s fiber-optic routes).
• Applications span databases (B-trees), search engines (tries), and logistics (graph routing).
• Trade-offs: Time/space complexity, memory locality, and hardware constraints (e.g., RAM vs. disk) dictate structure choice.

1. Self-Balancing Trees: AVL and B-Trees

1.1 AVL Trees: Balanced Binary Search Trees

Definition: An AVL tree is a self-balancing BST where the heights of the left and right subtrees of any node differ by at most 1 (balance factor $BF=\text{height(left)}-\text{height(right)}\in \{-1,0,1\}$). Rotations restore balance after insertions/deletions.

Key Operations:

1. Insertion:
   • Insert as in BST, then traverse upward to check balance factors.
   • Perform rotations if $BF$ violates the AVL property.
2. Rotations:
   • Left Rotation (LL): Right child becomes root; original root becomes left child.
   • Right Rotation (RR): Left child becomes root; original root becomes right child.
   • Left-Right (LR) and Right-Left (RL): Combination of rotations for complex imbalances.

Example: Insertion Trace Insert [14, 16, 22, 19, 15, 12, 21] into an empty AVL tree. Show balance factors and rotations after each step.

Step-by-Step Insertion:

Visual After Step 4 (LL Rotation):

Code Implementation (Python):

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def insert(root, key):
    # BST insertion + AVL balancing logic
    pass

Advantages/Disadvantages:

1.2 B-Trees: Disk-Optimized Trees

Definition: A B-tree is a multi-way search tree where:

• Each node has $m-1$ to $2m-1$ keys (degree $m\ge 2$).
• All leaves are at the same level.
• Keys are stored in sorted order, with children pointers between keys.

Why B-Trees?

• Minimize disk I/O: Fewer node accesses due to high branching factor (e.g., $m=100$ for SSDs).
• Used in: Databases (e.g., MySQL’s InnoDB), filesystems (e.g., NTFS), and NEPSE’s stock index storage.

Example: B-Tree Insertion ($m=3$) Insert [10, 20, 5, 6, 12, 30, 7, 17] into a B-tree.

Step-by-Step:

1. Insert 10: Root node [10].
2. Insert 20: Root becomes [10, 20].
3. Insert 5: Split [5, 10]; promote 10 to root.
4. Insert 6: Merge with left child; split if overflow.
5. Final structure (after all inserts):

Code Snippet (Insertion Logic):

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []
        self.children = []
        self.leaf = leaf

def insert_btree(root, key, m):
    # Handle splitting and promotion
    pass

Comparison: AVL vs. B-Tree

2. Tries: Prefix Trees for Strings

Definition: A trie (prefix tree) stores strings by shared prefixes in a tree structure:

• Root: Empty string.
• Edges: Characters.
• Terminal nodes: Mark end of a word.

Operations:

• Insert: Traverse/extend nodes for each character.
• Search: Traverse to the end of the string.
• Delete: Recursively remove nodes if no other strings use them.

Example: Autocomplete Trie Insert ["car", "card", "care", "cat"] into a trie.

Applications in Nepal:

• eSewa/Khalti: Prefix searches for merchant names (e.g., typing "N" auto-completes to "Ncell Merchant").
• Nepali Language Processing: Storing complex scripts (Devanagari) efficiently.

Code Implementation:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert_trie(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end = True

Advantages:

• Fast prefix searches: $O(L)$ per operation ($L=\text{length of key}$).
• Space-efficient for shared prefixes: E.g., "care" and "card" share c-a-r.

3. Graph Algorithms: Shortest Paths and MSTs

3.1 Dijkstra’s Algorithm: Shortest Path

Problem: Find the shortest path from a source node to all other nodes in a weighted graph (non-negative edges).

Algorithm Steps:

1. Initialize distances: $d[\text{source}]=0$, others $=\infty$.
2. Use a priority queue to pick the node $u$ with the smallest $d[u]$.
3. Relax edges: For each neighbor $v$ of $u$, update $d[v]=\min (d[v],d[u]+\text{weight}(u,v))$.
4. Repeat until all nodes are processed.

Example: NTC’s Fiber-Optic Network Graph: Nodes = Kathmandu (K), Pokhara (P), Biratnagar (B), Dharan (D). Edges: K-P (50), K-B (30), P-D (20), B-D (10).

graph TD
    K["Kathmandu"] -->|"50"| P["Pokhara"]
    K -->|"30"| B["Biratnagar"]
    P -->|"20"| D["Dharan"]
    B -->|"10"| D

Trace (Source = K):

Shortest Paths:

• $K\to B\to D$: Total cost = 40.
• $K\to P\to D$: Total cost = 70.

Code (Python):

import heapq
def dijkstra(graph, source):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    heap = [(0, source)]
    while heap:
        current_dist, u = heapq.heappop(heap)
        for v, weight in graph[u].items():
            distance = current_dist + weight
            if distance < distances[v]:
                distances[v] = distance
                heapq.heappush(heap, (distance, v))
    return distances

3.2 Minimum Spanning Tree (MST): Prim’s and Kruskal’s

Problem: Find a subset of edges that connects all nodes with minimum total weight and no cycles.

Prim’s Algorithm:

• Start from an arbitrary node.
• Greedily add the cheapest edge connecting the current MST to a new node.

Kruskal’s Algorithm:

• Sort all edges by weight.
• Add edges one by one, skipping those that form cycles (use Union-Find).

Example: Pathao’s Bike-Sharing Routes Graph: Nodes = Thamel (T), Koteshwor (K), Lazimpat (L), Jawalakhel (J). Edges: T-K (4), T-L (2), K-J (3), L-J (1).

Prim’s Trace (Start at T):

1. Add T-L (cost=2).
2. Add L-J (cost=1, total=3).
3. Add T-K (cost=4, total=7).
4. Skip K-J (cycle).

MST Edges: T-L, L-J, T-K (Total cost = 7).

Kruskal’s Trace:

1. Sort edges: L-J (1), T-L (2), K-J (3), T-K (4).
2. Add L-J, T-L, T-K (skip K-J as it forms a cycle).

Comparison:

## In the Real World

1. eSewa/Khalti’s Merchant Search:

   • Trie: Stores merchant names (e.g., "Ncell Merchant", "F1 Plus") for instant autocomplete. Typing "N" narrows to names starting with "N" in $O(L)$ time.

2. NTC’s Fiber-Optic Network:

   • Dijkstra’s Algorithm: Computes the fastest route for data packets between cities (e.g., Kathmandu to Pokhara via Biratnagar if the direct link is congested).

3. Nepal Rastra Bank’s Loan Processing:

   • B-Trees: Indexes customer accounts by loan ID for $O(\log n)$ lookups, even with millions of records stored on disk.

4. Daraz’s Order Fulfillment:

   • Graph (MST): Optimizes warehouse-to-delivery routes for multiple orders (e.g., Prim’s algorithm to minimize total delivery distance).

5. NEPSE’s Stock Trading System:

   • AVL Trees: Maintains a balanced index of stock prices for $O(\log n)$ buy/sell operations, ensuring fairness during high-volume trades.

## Exam Tip

1. AVL/B-Tree Questions:

   • Must show: Balance factors, rotation types (LL/LR/RR/RL), and final tree structure after each operation.
   • Common Pitfall: Forgetting to update heights/balance factors after rotations. Always recalculate them!

2. Trie Questions:

   • Draw the trie step-by-step for insertions/searches. Label terminal nodes clearly.
   • Shortcut: For autocomplete, highlight the longest prefix match.

3. Graph Algorithms:

   • Dijkstra: Show the priority queue state after each extraction.
   • MST: List edges in order of addition and justify why others are skipped (cycles).
   • Real-World Tie-In: Relate to NTC/Pokhara University’s network or Daraz’s logistics (e.g., "Prim’s algorithm minimizes fuel costs for delivery vans").

4. Code Traces:

   • Exams often ask for pseudocode + trace table. Include:
     • Initialization step.
     • Loop invariants (e.g., "priority queue always contains unprocessed nodes").
     • Final output with justification.

5. Comparison Tables:

   • Always include time/space complexity and use cases (e.g., AVL for RAM, B-tree for disk).

Visual Summary: