Advanced Data Structures

1. Introduction to Advanced Data Structures

Advanced data structures are designed to optimize specific operations beyond what basic structures like arrays and linked lists offer. They maintain special properties that guarantee efficient performance.

Why Self-Balancing Trees?

In a regular Binary Search Tree (BST), the height can become O(n) in the worst case (skewed tree), making operations O(n). Self-balancing trees maintain a height of O(log n), ensuring O(log n) operations.

*m = length of string, n = number of strings

2. AVL Trees

2.1 Properties of AVL Trees

• It is a Binary Search Tree (left < root < right)
• Balance Factor of every node is -1, 0, or +1
• Height is always O(log n)
• Rebalancing is done through rotations after insertion/deletion

2.2 AVL Tree Rotations

When an insertion or deletion causes imbalance, rotations restore balance:

2.3 Rotation Diagrams

    Before (BF=2):              After (BF=0):
         30                          20
        /                           /  \
       20         ─────►          10    30
      /
     10

    Steps:
    1. B becomes new root
    2. A becomes right child of B
    3. Right subtree of B becomes left subtree of A

    Before (BF=-2):             After (BF=0):
       10                            20
         \                          /  \
          20       ─────►         10    30
            \
             30

    Steps:
    1. B becomes new root
    2. A becomes left child of B
    3. Left subtree of B becomes right subtree of A

    Before:                Step 1 (Left):        Step 2 (Right):
       30                      30                     25
      /                       /                      /  \
     20        ─────►        25       ─────►       20    30
       \                    /
        25                 20

    Before:                Step 1 (Right):       Step 2 (Left):
     10                       10                     15
       \                        \                   /  \
        20     ─────►            15    ─────►     10    20
       /                           \
      15                            20

Insert 10:     Insert 20:     Insert 30:        After RR:
   10            10              10                20
                   \               \  BF=-2       /  \
                    20              20    →      10   30
                                      \
                                       30

Insert 40:        After RR at 30:     Insert 50:       After RR at 40:
    20                 20                 20                20
   /  \               /  \               /  \              /  \
  10   30    →      10    40            10   40    →     10   40
         \               /  \               /  \           /  \
          40           30    50           30   50        30   50

Insert 25:
      20
     /  \
   10    40
        /  \
       30   50
      /
     25
(Tree is balanced, no rotation needed)

2.4 Time Complexity Analysis

3. B-Trees

3.1 Properties of B-Tree of Order m

• Every node has at most m children
• Every non-leaf node (except root) has at least ⌈m/2⌉ children
• Root has at least 2 children if it's not a leaf
• A non-leaf node with k children contains k-1 keys
• All leaves appear at the same level (perfectly balanced)
• Keys within a node are sorted in ascending order

                    [30]
                   /    \
            [10, 20]    [40, 50]
           /   |   \    /   |   \
         [5] [15] [25] [35] [45] [55, 60]

Properties:
- Order m = 3
- Max children = 3, Max keys = 2
- Min children (non-root) = ⌈3/2⌉ = 2, Min keys = 1
- All leaves at same level

3.2 B-Tree Operations

Search Operation

Insertion Operation

Insert 1,3,7,10:        [1, 3, 7, 10]  (fits in one node)

Insert 11:              Split required (5 keys > max 4)
                              [7]
                             /   \
                     [1, 3]     [10, 11]

Insert 13, 14, 15:           [7]
                            /   \
                    [1, 3]     [10, 11, 13, 14, 15]

                    Split right child:
                              [7, 13]
                             /   |   \
                    [1, 3] [10,11] [14, 15]

Insert 18, 16:           [7, 13]
                        /   |   \
               [1, 3] [10,11] [14, 15, 16, 18]

Insert 19:     Split rightmost leaf:
                         [7, 13, 16]
                       /   |   |    \
              [1,3] [10,11] [14,15] [18, 19]

Insert 24:            [7, 13, 16]
                     /   |   |    \
            [1,3] [10,11] [14,15] [18, 19, 24]

Deletion Operation

3.3 Time Complexity

4. B+ Trees

4.1 Differences: B-Tree vs B+ Tree

                         [30 | 50]                    ← Internal node
                        /    |    \                    (only keys, no data)
                      /      |      \
              [10|20|30]  [40|50]  [60|70|80]        ← Leaf nodes
                 ↓           ↓          ↓              (keys + data)
              [data]      [data]     [data]
                 ↔           ↔          ↔            ← Linked list

Key features:
- Internal nodes: only keys for navigation
- Leaf nodes: keys + data pointers
- Leaves linked for range queries
- Keys 30 and 50 appear in both internal and leaf nodes

4.2 Advantages of B+ Trees

• Better for range queries: Leaf nodes are linked, allowing sequential traversal
• More keys per internal node: Internal nodes don't store data, so they can hold more keys
• Better cache performance: Internal nodes fit better in memory
• Uniform access time: All searches go to leaf level

4.3 Time Complexity

5. Red-Black Trees

5.1 Properties (Rules)

                    (13,B)                    B = Black, R = Red
                   /      \
               (8,R)      (17,R)
              /    \      /    \
          (1,B)  (11,B) (15,B) (25,B)
             \                  /
            (6,R)            (22,R)

Black Height from root = 2 (count black nodes to any leaf)
No two consecutive red nodes
Root is black

5.2 Insertion in Red-Black Tree

New nodes are always inserted as RED (to maintain black height). Then fix violations:

5.3 Comparison: AVL vs Red-Black Trees

5.4 Time Complexity

6. Tries (Prefix Trees)

6.1 Properties of Tries

• Root node is empty
• Each edge represents a character
• Path from root to a node represents a prefix
• End-of-word nodes are marked specially
• Common prefixes are shared

                        (root)
                       /      \
                     c          d
                     |          |
                     a          o
                    / \         |
                   t*  r        g*
                      /|\
                     d* e*
                         |
                         *

    * = End of word marker

    Searching "car":
    root → c → a → r (found, marked as word end)

    Searching "cab":
    root → c → a → b (not found, no 'b' edge)

6.2 Trie Operations

structure TrieNode:
    children[ALPHABET_SIZE]  // Array of child pointers
    isEndOfWord              // Boolean flag

function INSERT(root, word):
    node = root
    for each character c in word:
        index = c - 'a'
        if node.children[index] is NULL:
            node.children[index] = new TrieNode()
        node = node.children[index]
    node.isEndOfWord = true

function SEARCH(root, word):
    node = root
    for each character c in word:
        index = c - 'a'
        if node.children[index] is NULL:
            return false
        node = node.children[index]
    return node.isEndOfWord

function STARTS_WITH(root, prefix):
    node = root
    for each character c in prefix:
        index = c - 'a'
        if node.children[index] is NULL:
            return false
        node = node.children[index]
    return true

6.3 Time & Space Complexity

6.4 Applications of Tries

• Autocomplete: Finding all words with given prefix
• Spell Checker: Checking if word exists in dictionary
• IP Routing: Longest prefix matching
• Phone Directory: Contact search

7. Graphs

7.1 Types of Graphs

    A --- B
    |     |
    C --- D
                        

    A → B
    ↓   ↓
    C → D
                        

7.2 Graph Representations

Adjacency Matrix

Graph:                    Adjacency Matrix:
    0 --- 1                     0   1   2   3
    |   / |               0  [  0   1   1   0  ]
    |  /  |               1  [  1   0   1   1  ]
    2 --- 3               2  [  1   1   0   1  ]
                          3  [  0   1   1   0  ]

Space: O(V²)
Check edge: O(1)
Find all neighbors: O(V)

Adjacency List

Graph:                    Adjacency List:
    0 --- 1               0: [1, 2]
    |   / |               1: [0, 2, 3]
    |  /  |               2: [0, 1, 3]
    2 --- 3               3: [1, 2]

Space: O(V + E)
Check edge: O(degree of vertex)
Find all neighbors: O(degree of vertex)

7.3 Comparison of Representations

8. Breadth First Search (BFS)

8.1 BFS Algorithm

function BFS(graph, start):
    visited = set()
    queue = empty queue

    visited.add(start)
    queue.enqueue(start)

    while queue is not empty:
        vertex = queue.dequeue()
        print(vertex)  // Process vertex

        for each neighbor of vertex in graph:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

Graph:
        0
       / \
      1   2
     / \   \
    3   4   5

BFS from 0:
Step 1: Visit 0, Queue: [1, 2]
Step 2: Visit 1, Queue: [2, 3, 4]
Step 3: Visit 2, Queue: [3, 4, 5]
Step 4: Visit 3, Queue: [4, 5]
Step 5: Visit 4, Queue: [5]
Step 6: Visit 5, Queue: []

BFS Order: 0 → 1 → 2 → 3 → 4 → 5
(Level by level traversal)

8.2 BFS Properties & Applications

Applications:

• Shortest path in unweighted graph
• Finding connected components
• Level order traversal in trees
• Finding all nodes within k distance
• Web crawlers
• Social network friend suggestions

9. Depth First Search (DFS)

9.1 DFS Algorithm

function DFS(graph, vertex, visited):
    visited.add(vertex)
    print(vertex)  // Process vertex

    for each neighbor of vertex in graph:
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

// Call: DFS(graph, start, empty set)

function DFS_Iterative(graph, start):
    visited = set()
    stack = empty stack

    stack.push(start)

    while stack is not empty:
        vertex = stack.pop()

        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  // Process vertex

            for each neighbor of vertex in graph:
                if neighbor not in visited:
                    stack.push(neighbor)

Graph:
        0
       / \
      1   2
     / \   \
    3   4   5

DFS from 0 (recursive, left-first):
Step 1: Visit 0, explore neighbor 1
Step 2: Visit 1, explore neighbor 3
Step 3: Visit 3 (no unvisited neighbors), backtrack
Step 4: Back to 1, explore neighbor 4
Step 5: Visit 4, backtrack to 1, then to 0
Step 6: Explore neighbor 2
Step 7: Visit 2, explore neighbor 5
Step 8: Visit 5, done

DFS Order: 0 → 1 → 3 → 4 → 2 → 5
(Go deep, then backtrack)

9.2 DFS Properties & Applications

Applications:

• Detecting cycles in graph
• Topological sorting
• Finding strongly connected components
• Solving puzzles (mazes)
• Path finding
• Checking if graph is bipartite

9.3 BFS vs DFS Comparison

10. Practice Questions

Key Points Summary