Data Structures (Advanced)

1. Balanced Search Trees

1.1 Red-Black Trees

A red-black tree is a self-balancing BST satisfying five invariants:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL sentinel) is black.
4. If a node is red, both its children are black (no two consecutive reds on any path).
5. For every node, all simple paths from the node to descendant leaves contain the same number of black nodes. This number is the black-height of the node.

Theorem 1.1. A red-black tree with $n$ internal nodes has height $h \leq 2 \log_2(n + 1)$.

Proof. By invariant 4, on any path from root to leaf, at most half the nodes (rounded up) can be red. So the length of any root-to-leaf path is at most twice the black-height $bh$ of the root. We now bound $bh$ in terms of $n$.

Consider the subtree rooted at any node $x$. If this subtree has height $h_x$Then it contains at least $2^{bh(x)} - 1$ internal nodes (…/1-number-and-algebra/3_proof-and-logic by induction on $h_x$: if $x$ is a leaf, it has $0 = 2^0 - 1$ internal nodes; otherwise, each child has black-height at least $bh(x) - 1$ if it is red, or $bh(x)$ if it is black, so each child has at least $2^{bh(x)-1} - 1$ internal nodes, giving at least $2(2^{bh(x)-1} - 1) + 1 = 2^{bh(x)} - 1$ for $x$).

Therefore $n \geq 2^{bh(\mathrm{root})} - 1$Giving $bh(\mathrm{root}) \leq \log_2(n+1)$. Since $h \leq 2 \cdot bh(\mathrm{root})$We have $h \leq 2\log_2(n+1)$. $\blacksquare$

Corollary. Search, insert, and delete in a red-black tree take $O(\log n)$ time.

1.1.1 Insertion

Insertion follows the standard BST insert, then colours the new node red. This may violate invariant 4 (two consecutive reds). Fix-up uses at most three rotations and recolouring.

Cases after insertion (let $z$ be the newly inserted red node, $p$ its parent, $u$ its uncle, and $g$ its grandparent):

Theorem 1.2. Insertion into a red-black tree with $n$ nodes takes $O(\log n)$ time and performs at most 2 rotations.

Proof. The BST insert takes $O(\log n)$ time. The fix-up loop ascends the tree. Each iteration either terminates (cases 2 and 3 perform one or two rotations and terminate) or moves the problem two levels up (case 1 recolours and continues with $g$). Since the tree height is $O(\log n)$The loop runs $O(\log n)$ times, but only cases 2 and 3 involve rotations, and at most one of these is reached. $\blacksquare$

7(B)

    7(B)
   /
  3(R)

    7(B)
   /    \
  3(R)  18(R)

      7(B)
    /      \
   3(B)    18(B)
          /
        10(R)

      7(B)
    /      \
   3(B)    18(B)
          /    \
        10(R)  22(R)

        7(B)
      /      \
    3(B)     18(R)
            /     \
         10(B)   22(B)
         /
       8(R)

        7(B)
      /      \
    3(B)     18(R)
            /     \
         10(B)   22(B)
         /   \
       8(R)  11(R)

          7(B)
       /        \
     3(B)      18(B)
    /   \      /    \
  2(R)  6(R) 10(R)  22(B)
          /   \       \
        8(B) 11(B)   26(R)

1.1.2 Deletion

Deletion is more complex than insertion. The key difficulty arises when removing a black node, which changes the black-height of paths.

Algorithm outline:

1. Perform standard BST deletion. If the removed node $y$ is black, let $x$ be the node that replaces $y$ in its position. The “extra black” is pushed onto $x$.
2. If $x$ is red-black (red with an extra black), colour it black.
3. Otherwise, fix the “double-black” violation at $x$ using the fix-up procedure.

Fix-up cases (let $w$ be the sibling of $x$):

Theorem 1.3. Deletion from a red-black tree with $n$ nodes takes $O(\log n)$ time and performs at most 3 rotations.

Proof. BST deletion is $O(\log n)$. The fix-up loop either terminates (cases 1, 3, and 4 involve rotations and terminate or move to case 4 which terminates) or moves the problem one level up (case 2). At most $O(\log n)$ iterations, but at most 3 rotations total (case 1 does one, then case 3 does one, then case 4 does one). $\blacksquare$

          7(B)
       /        \
     3(B)      18(B)
    /   \      /    \
  2(R)  6(R) 10(R)  22(B)
          /   \       \
        8(B) 11(B)   26(R)

          7(B)
       /        \
     3(B)      22(B)
    /   \      /
  2(R)  6(R) 10(R)
          /   \
        8(B) 11(B)
              \
             26(R)

          7(B)
       /        \
     3(B)      22(B)
    /   \      /
  2(R)  6(R) 10(R)
          /   \
        8(B) 11(B)

:::caution Common Pitfall The most common error in red-black tree deletion is forgetting to handle the case where the node to be deleted has two children. In this case, one must find the successor (or predecessor), copy its key/value to the node being deleted, and then delete the successor node from its original position. The successor always has at most one child, simplifying the actual removal. :::

1.2 B-Trees and B+ Trees

1.2.1 B-Trees

A B-tree of minimum degree $t$ (where $t \geq 2$) is a rooted tree satisfying:

1. Every node other than the root has at least $t - 1$ keys. The root has at least 1 key.
2. Every node has at most $2t - 1$ keys.
3. Every internal node with $k$ keys has exactly $k + 1$ children.
4. All leaves appear at the same depth.

Theorem 1.4. A B-tree of height $h$ with minimum degree $t \geq 2$ has at least $2t^{h-1}$ leaves (for $h \geq 1$) and stores at least $n \geq 2t^{h-1} - 1$ keys.

Proof. The root has at least 2 children (since it has at least 1 key). Every internal node at depth $\geq 1$ has at least $t$ children. Therefore the number of nodes at depth $d$ is at least $2t^{d-1}$ for $d \geq 1$. The number of leaves (at depth $h$) is at least $2t^{h-1}$. Each leaf has at least $t - 1$ keys, so $n \geq 2t^{h-1}(t-1) \geq 2t^{h-1} - 1$ (for $t \geq 2$). $\blacksquare$

Corollary. The height of a B-tree storing $n$ keys is $h \leq \log_t \frac{n+1}{2} = O(\log_t n)$.

For example, with $t = 1001$ and $n = 10^9$, $h \leq \log_{1001}(5 \times 10^8) \approx 2.8$So at most 3 disk accesses.

1.2.2 B-Tree Operations

Search. Starting at the root, scan the keys in the current node for the target. If found, return. Otherwise, determine which child pointer to follow and recurse. Takes $O(\log_t n)$ node accesses.

Insertion. Insert the key into the appropriate leaf. If the leaf overflows (has $2t$ keys), split it: promote the median key to the parent, and create two new nodes each with $t - 1$ keys. If the parent overflows, split it recursively. If the root splits, create a new root with one key and two children.

Split cost. Splitting a node costs $O(t)$ time (copying keys and children) but occurs infrequently. The amortised cost of insertion is $O(\log_t n + t)$.

      [6]
     /    \
  [5]    [10, 20]

        [6, 20]
       /   |    \
    [5]  [10,12] [30]

        [6, 20]
       /   |    \
    [5,7] [10,12,17] [30]

Deletion. Deletion from a B-tree is more complex. The key cases are:

1. Key in a leaf with excess keys ($> t - 1$): remove.
2. Key in a leaf with minimum keys ($t - 1$): try to borrow from an immediate sibling (if the sibling has $> t - 1$ keys, rotate through the parent). If no sibling can lend, merge with a sibling (this reduces the parent’s key count by 1, which may cascade upward).
3. Key in an internal node: replace with the predecessor (or successor), then delete the predecessor from its leaf position (which reduces to cases 1 or 2).

Theorem 1.5. Deletion from a B-tree takes $O(t \log_t n)$ time in the worst case.

        [6, 20]
       /   |    \
    [5,7] [10,12,17] [30]

        [6, 20]
       /   |    \
    [5,7] [10,17] [30]

        [6, 17]
       /   |    \
    [5,7] [10] [20, 30]

1.2.3 B+ Trees

A B+ tree is a variant of the B-tree where:

1. All data records (key-value pairs) are stored in leaf nodes only.
2. Internal nodes store only keys for routing.
3. Leaf nodes are linked together in a linked list (in sorted order).

Advantages over B-trees:

• Range queries are efficient: find the start of the range, then follow leaf pointers.
• Internal nodes have higher fan-out (they store only keys, not values), reducing tree height.
• All leaves are at the same depth, ensuring uniform access time.

Theorem 1.6. A B+ tree of order $d$ (maximum $d$ keys per internal node) with $n$ records has height $h \leq \lceil \log_d(n) \rceil + 1$.

1.2.4 B+ Tree vs B-Tree Comparison

:::caution Common Pitfall Students often confuse the minimum degree $t$ of a B-tree with its order. A B-tree of order $m$ has maximum $m$ children per internal node, which means $t = \lceil m/2 \rceil$. A B-tree of minimum degree $t$ has maximum $2t - 1$ keys per node. Always verify which convention the question or textbook uses. :::

1.3 Tries and Prefix Trees

A trie (from “retrieval”) is a tree data structure for storing strings. Each node represents a prefix, and edges are labelled with characters.

Definition. A trie for a set of strings over alphabet $\Sigma$ is a rooted tree where:

1. Each edge is labelled with a character from $\Sigma$.
2. Each node represents the string formed by the concatenation of edge labels from the root to that node.
3. A node is marked as a “terminal” node if the string it represents is in the stored set.

Operations:

Space. A trie storing $n$ strings of total length $N$ uses $O(N)$ nodes. Each node has up to $|\Sigma|$ children pointers.

Theorem 1.7. A trie storing $n$ distinct strings over alphabet $\Sigma$ has at most $n \cdot L_{\max}$ nodes, where $L_{\max}$ is the maximum string length.

1.3.1 Compressed Tries (Radix Trees)

A compressed trie (or radix tree or Patricia trie) eliminates chains of single-child nodes by compressing the edge labels. Each edge stores a substring rather than a single character.

Space savings. If the strings share long common prefixes, compression significantly reduces the number of nodes.

(root)
├── a
│   ├── p
│   │   ├── p [terminal: "app"]
│   │   │   ├── l
│   │   │   │   └── e [terminal: "apple"]
│   │   │   └── l
│   │   │       └── i
│   │   │           └── c
│   │   │               └── a
│   │   │                   └── t
│   │   │                       └── i
│   │   │                           └── o
│   │   │                               └── n [terminal: "application"]
│   │   └── t [terminal: "apt"]
│   └── ...
├── b
│   ├── a
│   │   ├── t [terminal: "bat"]
│   │   └── r [terminal: "bar"]
│   └── ...

(root)
├── "app" [terminal]
│   ├── "le" [terminal: "apple"]
│   └── "lication" [terminal: "application"]
├── "apt" [terminal]
├── "bat" [terminal]
└── "bar" [terminal]

1.3.2 Ternary Search Trees

A ternary search tree (TST) is a hybrid between a trie and a BST. Each node stores a single character and has three children: left (smaller character), middle (equal character, continue), and right (larger character).

Properties:

• Space: $O(N)$ where $N$ is the total length of all strings.
• Search: $O(L + \log |\Sigma|)$ per string (BST search at each character position).
• More space-efficient than a standard trie for sparse datasets.

1.4 Splay Trees

A splay tree is a self-adjusting BST with no explicit balance information. After every access (search, insert, or delete), the accessed node is moved to the root using a sequence of rotations called splaying.

Splay operations:

1. Zig (node is child of root): single rotation.
2. Zig-zig (node and parent are both left or both right children): rotate parent first, then node.
3. Zig-zag (node is left child of right child or vice versa): rotate node, then rotate node again.

Theorem 1.8 (Static Optimality). The total time for a sequence of accesses in a splay tree is $O\left(\sum_{i} \left(1 + \log \frac{W}{w_i}\right)\right)$ where $W = \sum_i w_i$ is the total access count and $w_i$ is the number of accesses of the $i$-th element.

This means splay trees are asymptotically as fast as a static optimal binary search tree for any access sequence.

Theorem 1.9 (Static Finger). The total access time is $O\left(n \log n + n \log \min_{j} |\mathrm{key_i} - \mathrm{key_j}|\right)$ where $j$ is a fixed “finger” position.

Theorem 1.10 (Working Set). The access time for element $i$ is $O(\log(t_i))$ where $t_i$ is the number of distinct elements accessed since the last access to element $i$.

  2
 /
1

    2
   /
  1

  2
   \
    3

  2
 / \
1   3

  3
 /
2

  3
 /
2
 \
  1

  2
 /
1

  2
 / \
1   3

    3
   /
  2
 /
1

      4
     /
    3
   /
  2
 /
1

        5
       /
      4
     /
    3
   /
  2
 /
1

  2
 / \
1   3
     \
      4
       \
        5

      3
     /
    2
   / \
  1   4
       \
        5

        4
       /
      3
     /
    2
   / \
  1   5

      4
     /
    3
   /
  2
 / \
1   5

        4
       /
      3
     /
    2
   /
  1
   \
    5 (was under 4, now let's ignore 5 for simplicity)

        4
       / \
      3   5
     /
    2
   /
  1

      3
     / \
    2   4
   /     \
  1       5

    2
   / \
  1   3
       \
        4
       / \
          5

    2
   / \
  1   3
       \
        4
         \
          5

  1
   \
    2
     \
      3
       \
        4
         \
          5

2. Advanced Priority Queues

2.1 Binomial Heaps

A binomial heap is a collection of binomial trees satisfying the heap property. It supports merge in $O(\log n)$ and insert, extract-min, and decrease-key in $O(\log n)$.

Binomial tree $B_k$. Defined recursively: $B_0$ is a single node. $B_k$ is formed by linking two $B_{k-1}$ trees, making one the leftmost child of the other’s root.

Properties of $B_k$:

Theorem 2.1. A binomial heap with $n$ nodes contains at most $\lfloor \log_2 n \rfloor + 1$ binomial trees.

Proof. The binary representation of $n$ determines which binomial trees are present. If $n = \sum_{i} 2^{b_i}$ (binary decomposition), then the heap contains exactly the trees $B_{b_1}, B_{b_2}, \ldots$. The number of terms is at most $\lfloor \log_2 n \rfloor + 1$. $\blacksquare$

Operations:

• Merge: Analogous to binary addition. Combine trees of the same degree by linking. $O(\log n)$.
• Insert: Create a single-node heap and merge. $O(\log n)$.
• Extract-min: Remove the root with minimum key, merge its children into a new heap, merge with the remaining heap. $O(\log n)$.
• Decrease-key: Bubble the decreased key up to the root. $O(\log n)$.

2.2 Fibonacci Heaps

A Fibonacci heap is a collection of min-heap-ordered trees supporting:

Key difference from binomial heaps: Fibonacci heaps allow trees to have any structure (not just binomial trees). Trees are only restructured during extract-min (consolidation). Decrease-key may cut a subtree from its parent and add it to the root list (“cascading cut”).

Lazy merging. Two heaps are merged by concatenating their root lists in $O(1)$ time.

Consolidation. During extract-min, all roots are combined by degree using an array. Trees of the same degree are linked.

Theorem 2.2. The amortised cost of extract-min is $O(D(n))$ where $D(n)$ is the maximum degree of any node in the Fibonacci heap.

Theorem 2.3. $D(n) = O(\log_\phi n)$ where $\phi = (1 + \sqrt{5})/2$ is the golden ratio.

Proof (outline). Define the potential $\Phi = t(H) + 2m(H)$ where $t(H)$ is the number of trees and $m(H)$ is the number of marked nodes. Show that each operation’s amortised cost is bounded. For decrease-key, the actual cost is $O(c)$ where $c$ is the number of cascading cuts. The change in potential is at most $c + 2 - 2m'(H) \cdot (\text{terms} cancel)$Giving $O(1)$ amortised. $\blacksquare$

:::caution Common Pitfall Fibonacci heaps have excellent amortised bounds but poor constant factors in practice due to the overhead of maintaining the root list, marking nodes, and consolidation. For this reason, binary heaps (or pairing heaps) are often preferred in practice despite worse theoretical amortised bounds for decrease-key. :::

2.3 Pairing Heaps

A pairing heap is a simplified alternative to Fibonacci heaps. It is a single min-heap-ordered multi-way tree.

Operations:

• Find-min: $O(1)$ (return root).
• Insert: $O(1)$ (add as leftmost child of root).
• Merge: $O(1)$ (make the larger root a child of the smaller root).
• Delete-min: Two-pass merging of all children: first pass pairs adjacent children, second pass merges the resulting trees left to right.
• Decrease-key: $O(1)$ (cut the node and merge with root).

Theorem 2.4. Insert, find-min, merge, and decrease-key take $O(1)$ amortised time. Delete-min takes $O(\log n)$ amortised time.

Proof sketch. The potential function is $\Phi = \log n$ per subtree (where $n$ is the subtree size). The key insight is that the two-pass merge of delete-min reduces the potential by at least $\log n$Absorbing the $O(n)$ work of merging. $\blacksquare$

Note. Whether pairing heaps achieve $O(\log n)$ amortised delete-min was an open problem for many years. It was resolved by Iacono and Ozturk (2018) who proved $O(\log n)$ for a variant called the “original pairing heap” and gave a $\Omega(\log \log n)$ lower bound for a simpler variant.

3. Advanced Graph Representations

3.1 Incidence Matrix

The incidence matrix $M$ of an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges is an $n \times m$ matrix where:

$M_{v,e} = \begin{cases} 1 & \text{if} vertex v \text{ is} incident to edge e \\ 0 & \text{otherwise} \end{cases}$

For directed graphs, $M_{v,e} = 1$ if $v$ is the tail of $e$, $M_{v,e} = -1$ if $v$ is the head of $e$And $0$ otherwise.

Properties:

• Space: $O(nm)$.
• The rank of $M$ over $\mathbb{R}$ is $n - c$ where $c$ is the number of connected components.
• The number of spanning trees of $G$ equals any cofactor of $MM^T$ (Kirchhoff’s matrix tree theorem).

3.2 Implicit Graphs

Many graphs are not stored explicitly but defined by a rule or function. Examples:

• State space graphs: Each vertex is a configuration; edges are valid transitions. Example: the 15-puzzle has $16!/2 \approx 10^{13}$ states.
• Geometric graphs: Vertices are points in $\mathbb{R}^d$; edges connect nearby points. Example: Delaunay triangulation.
• Social networks: Vertices are users; edges are friendships.

Implicit graph traversal requires a successor function that generates neighbours on-the-fly, rather than storing them.

3.3 Compressed Graph Representations

For massive graphs that do not fit in memory:

• CSR (Compressed Sparse Row): Two arrays: offsets (size $|V|+1$) and neighbours (size $2|E|$). offsets[i] to offsets[i+1]-1 gives the range of neighbours for vertex $i$. Space: $O(V + E)$Cache-friendly.
• WebGraph framework: Compresses web graphs using gap encoding, reference chains, and interval encoding. Achieves 2—3 bits per edge for typical web graphs.

4. Disjoint Set Union — Advanced Analysis

4.1 The Inverse Ackermann Function

The inverse Ackermann function $\alpha(n)$ is defined in terms of a rapidly growing function $A_k(j)$:

$A_k(j) = \begin{cases} 2j & \text{if} k = 0 \\ 0 & \text{if} j = 0 \text{ and} k \geq 1 \\ A_{k-1}(A_k(j-1)) & \text{if} j \geq 1 \text{ and} k \geq 1 \end{cases}$

$\alpha(n) = \min\{k : A_k(1) \geq n\}$

Key values: $\alpha(1) = 0$, $\alpha(2) = 1$, $\alpha(4) = 2$, $\alpha(16) = 3$, $\alpha(2^{65536}) = 4$.

For all practical purposes, $\alpha(n) \leq 4$.

4.2 Detailed Analysis of Union-Find

Theorem 4.1. A sequence of $m$ MakeSet, Union, and Find operations on $n$ elements, using union by rank with path compression, takes $O(m \alpha(n))$ time.

Proof (high-level outline).

Define the “level” of a node based on its rank. The key idea is to partition the nodes into groups and bound the total charges.

Let $A_k(j)$ be as defined above. Node $x$ has level $\ell$ if $\text{rank}(x) \in [A_\ell(\lfloor \log_2 n \rfloor), A_{\ell+1}(\lfloor \log_2 n \rfloor))$.

For a Find operation along a path $x_1, x_2, \ldots, x_k$Path compression makes all nodes point to the root. We charge the cost of the Find as follows:

• For each node $x_i$ that is not the root, if $x_i$‘s parent changes, charge $O(1)$ to $x_i$.
• We need to show each node is charged $O(\alpha(n))$ times total.

The …/1-number-and-algebra/3_proof-and-logic proceeds by showing that a node at level $\ell$ can be charged at most a constant number of times before it moves to a higher level or its parent’s level is too high for further charges. The total charges sum to $O(n \alpha(n) + m)$. $\blacksquare$

4.3 Union-Find with Partial Persistence

A persistent data structure preserves all previous versions. Partial persistence allows queries on any previous version but modifications only on the latest version.

Persistent Union-Find (Bender et al., 2002): Supports $m$ operations on $n$ elements with $O(\log \log n)$ amortised time per operation and $O(m \alpha(n))$ total space.

5. Interval Trees and Segment Trees

5.1 Interval Trees

An interval tree stores a set of intervals $[l_i, r_i]$ and supports:

• Insert an interval: $O(\log n)$.
• Delete an interval: $O(\log n)$.
• Query: find all intervals overlapping a given point $q$ (or interval). $O(\log n + k)$ where $k$ is the number of reported intervals.

Structure. An augmented BST where:

• In-order traversal of keys gives the intervals sorted by their left endpoint (or by midpoint).
• Each node stores a key $x_{\mathrm{mid}}$ (the median endpoint) and a max-endpoint for the subtree.

Query algorithm: Starting at the root, compare $q$ with $x_{\mathrm{mid}}$:

1. If $q < x_{\mathrm{mid}}$: report all intervals in the left subtree that overlap $q$ (check max-endpoint), then recurse into the left subtree. Also check if any interval stored at the current node overlaps $q$.
2. If $q \geq x_{\mathrm{mid}}$: similar for the right subtree.

Theorem 5.1. Query in an interval tree takes $O(\log n + k)$ time where $k$ is the number of reported intervals.

5.2 Segment Trees

A segment tree stores an array $A[1..n]$ and supports:

• Point update: set $A[i] = v$. $O(\log n)$.
• Range query: compute $\mathrm{combine}(A[l], A[l+1], \ldots, A[r])$ for any associative operation (sum, min, max, gcd). $O(\log n)$.

Structure. A binary tree where:

• The root represents the range $[1, n]$.
• Each internal node represents a sub-range, split in half between its children.
• Leaves represent individual elements.

Space. $O(n)$ (at most $4n$ nodes in the array representation).

Theorem 5.2. A segment tree on $n$ elements uses $O(n)$ space and supports point update and range query in $O(\log n)$ time each.

Proof. The segment tree is a complete binary tree of height $\lceil \log_2 n \rceil$. The number of nodes is at most $2 \cdot 2^{\lceil \log_2 n \rceil + 1} \leq 4n$. Each update or query visits at most $2 \log_2 n$ nodes (one per level, on each side). $\blacksquare$

              [0,7]: sum=31
             /                \
       [0,3]: sum=9       [4,7]: sum=22
       /         \         /         \
  [0,1]: sum=4  [2,3]:5  [4,5]:14  [6,7]:8
   /      \     /    \   /    \     /    \
[0]:3   [1]:1 [2]:4 [3]:1 [4]:5 [5]:9 [6]:2 [7]:6

5.3 Fenwick Trees (Binary Indexed Trees)

A Fenwick tree (BIT) is a space-efficient alternative to the segment tree for prefix sum queries and point updates.

Structure. An array BIT[1..n] where BIT[i] stores the sum of a specific range ending at index $i$. The range is determined by the lowest set bit of $i$: if $\mathrm{lsb}(i) = 2^k$Then BIT[i] stores the sum of $A[i - 2^k + 1..i]$.

Operations:

• Prefix sum $\sum_{j=1}^{i} A[j]$: Traverse BIT by removing lowest set bits. $O(\log n)$.
• Point update $A[i] += \delta$: Traverse BIT by adding lowest set bits. $O(\log n)$.
• Range sum $A[l..r]$: $\mathrm{prefix}(r) - \mathrm{prefix}(l-1)$. $O(\log n)$.

Advantages over segment trees: Simpler to implement, lower constant factor, $O(n)$ space (exactly $n+1$).

Limitations: Only supports prefix queries (not arbitrary range combinations unless the operation has an inverse, like sum or XOR).

Theorem 5.3. A Fenwick tree on $n$ elements supports prefix query and point update in $O(\log n)$ time and uses $O(n)$ space.

6. String Data Structures

6.1 Suffix Arrays

A suffix array $\mathrm{SA}$ of a string $S$ of length $n$ is a permutation of $\{0, 1, \ldots, n-1\}$ such that $S[\mathrm{SA}[0]..] < S[\mathrm{SA}[1]..] < \cdots < S[\mathrm{SA}[n-1]..]$ (lexicographic order of suffixes).

Construction: The most efficient algorithm (SA-IS) constructs the suffix array in $O(n)$ time. A simpler approach uses radix sort on prefixes of length $1, 2, 4, 8, \ldots$ in $O(n \log^2 n)$ time.

Theorem 6.1. The suffix array of a string of length $n$ can be constructed in $O(n)$ time (SA-IS algorithm) or $O(n \log n)$ time (using the doubling algorithm with radix sort).

6.2 Suffix Trees

A suffix tree for a string $S$ of length $n$ is a compressed trie of all $n$ suffixes of $S$ (plus a unique terminator \text{\}$).

Theorem 6.2 (Ukkonen). A suffix tree can be constructed in $O(n)$ time online.

Theorem 6.3. A suffix tree for a string of length $n$ has at most $2n$ nodes and at most $2n - 1$ edges.

Applications:

6.3 LCP Arrays

The LCP (Longest Common Prefix) array stores \mathrm{LCP[i] = the length of the longest common prefix of suffixes \mathrm{SA[i] and \mathrm{SA[i-1].

Theorem 6.4 (Kasai). The LCP array can be computed from the suffix array in $O(n)$ time.

Kasai’s algorithm. Uses the inverse suffix array \mathrm{SA^{-1}[\mathrm{SA[i]] = i and processes suffixes in text order. When computing \mathrm{LCP[\mathrm{SA^{-1}[j]]The result is at least \mathrm{LCP[\mathrm{SA^{-1}[j-1]] - 1.

7. Amortised Analysis — Detailed Framework

7.1 The Three Methods Compared

Equivalence. All three methods give the same amortised bounds when applied correctly. The accounting method is a special case of the potential method where $\Phi$ is the total credit.

7.2 Choosing a Potential Function

A good potential function satisfies:

1. $\Phi(D_0) = 0$ (initial potential is 0).
2. $\Phi(D_i) \geq 0$ for all $i$ (potential is never negative).
3. $\Phi$ increases before expensive operations and decreases during them.

Common potential functions:

7.3 Limitations of Amortised Analysis

:::caution Common Pitfall Amortised bounds do not guarantee worst-case performance for individual operations. In real-time systems, an $O(n)$ operation (even if amortised $O(1)$) may violate timing constraints. For real-time applications, use data structures with worst-case bounds (e.g., balanced BSTs instead of splay trees, or dynamic arrays with geometric resizing only when safe). :::

Theorem 7.1. There exist sequences of operations where any data structure supporting dynamic array operations must pay $\Omega(\log n)$ per operation in the worst case (cell-probe model lower bound).

8. Balanced BST Variants

8.1 Treaps (Tree + Heap)

A treap is a BST where each node has a key (BST property) and a priority (min-heap or max-heap property). The priorities are assigned randomly at insertion time.

Property: Expected height is $O(\log n)$ (by the same argument as random BSTs).

Rotations. If the heap property is violated, perform rotations to restore it:

• If a node’s priority is less than its parent’s (min-heap treap), rotate the node up.
• This is equivalent to inserting the node and then rotating it up to its correct heap position.

Split and merge operations:

• Split$(T, k)$: Split treap $T$ into two treaps $L$ and $R$ where all keys in $L$ are $\leq k$ and all keys in $R$ are $> k$. $O(\log n)$.
• Merge$(L, R)$: Merge two treaps where all keys in $L$ are less than all keys in $R$. $O(\log n)$.

Theorem 8.1. Split and merge in a treap take $O(\log n)$ expected time.

Proof. Split traverses a root-to-leaf path, performing rotations. The expected depth of any node is $O(\log n)$So the expected path length is $O(\log n)$. Merge follows a single path from the root of one treap downward. $\blacksquare$

(5, 0.7)

  (3, 0.2)
    \
  (5, 0.7)

  (3, 0.2)
    \
  (5, 0.7)
      \
    (7, 0.9)

    (3, 0.2)
   /       \
(1, 0.5) (5, 0.7)
              \
            (7, 0.9)

    (3, 0.2)
   /       \
(1, 0.5) (4, 0.1)
            /   \
          (5, 0.7)
              \
            (7, 0.9)

        (4, 0.1)
       /       \
  (3, 0.2)   (5, 0.7)
   /               \
(1, 0.5)         (7, 0.9)

        (4, 0.1)
       /       \
  (1, 0.5)   (5, 0.7)
      \           \
   (3, 0.2)    (7, 0.9)

8.2 Weight-Balanced Trees

A weight-balanced tree (also known as BB[$\alpha$] tree or Adelson-Velsky-Landis tree) maintains the balance condition:

$\frac{1}{2 - \alpha} \leq \frac{|T_L|}{|T|} \leq \frac{1}{2}$

For some fixed $\alpha \in (1/4, 1 - \sqrt{2}/2)$Where $|T_L|$ is the size of the left subtree and $|T|$ is the total size.

Theorem 8.2. A weight-balanced tree with $n$ nodes has height $O(\log n)$.

Proof. At each level, the subtree size decreases by a factor of at least $\alpha$. After $h$ levels, the minimum size is $\alpha^h n \geq 1$Giving $h \leq \log_{1/\alpha} n = O(\log n)$. $\blacksquare$

8.3 scapegoat Trees

A scapegoat tree is a BST where no rebalancing is done during insertion (only during deletion if needed). When an insertion causes the height to exceed $\log_{3/2} n$The algorithm finds a “scapegoat” ancestor whose subtree is unbalanced and rebuilds it.

Height bound. A scapegoat tree with $n$ nodes has height at most $\log_{3/2} n$ (the “scapegoat bound”).

Theorem 8.3. Insertion into a scapegoat tree takes $O(\log n)$ amortised time.

Proof. The key insight is that the number of insertions between rebuilds is at least proportional to the size of the rebuilt subtree. Each rebuild of a subtree of size $s$ costs $O(s)$. Since each element is charged $O(1)$ per rebuild, and each element participates in at most $O(\log n)$ rebuilds, the amortised cost is $O(\log n)$. $\blacksquare$

9. Graph Decomposition Structures

9.1 Heavy-Light Decomposition

Heavy-light decomposition (HLD) partitions a tree into paths, enabling efficient path queries (sum, max, min) and updates on trees.

Definitions. For each node $u$The child $v$ with the largest subtree is the heavy child. All other children are light children.

Property. Every root-to-leaf path has at most $O(\log n)$ light edges.

Proof. When traversing a light edge from $u$ to its parent $p$The subtree size at least doubles: |\text{subtree(p)| \geq 2 \cdot |\text{subtree(u)|. Since the tree has $n$ nodes, there can be at most $\log_2 n$ light edges on any root-to-leaf path. $\blacksquare$

Algorithm:

1. Root the tree and identify heavy/light children.
2. Decompose into heavy paths (maximal chains of heavy edges).
3. Each heavy path is stored in a segment tree (or Fenwick tree) for efficient queries.
4. A path query between two nodes is decomposed into $O(\log n)$ heavy path segments.

Theorem 9.1. HLD supports path queries and updates on a tree in $O(\log^2 n)$ time.

Proof. A path between two nodes is decomposed into $O(\log n)$ heavy path segments (due to $O(\log n)$ light edges). Each segment query on the segment tree takes $O(\log n)$. Total: $O(\log^2 n)$. $\blacksquare$

      1
     /|\
    2  3  4
   /|     |
  5  6    7
  |
  8