PadhaikoAll subjects

Advanced Data Structures

Advanced Algorithms (ENCT 467)

Open in the Padhaiko app

2.1 Fibonacci heaps

A Fibonacci heap is a collection of min-heap-ordered rooted trees that supports mergeable-heap operations with better amortized bounds than binary or binomial heaps, making it the classic priority queue behind Dijkstra's algorithm and Prim's algorithm.

Definition

Structure and Potential of a Fibonacci Heap

A Fibonacci heap consists of a circular, doubly linked root list of min-heap-ordered trees, a pointer H.min to the root with minimum key, and the node count H.n. Each node stores:

Using for the number of trees in the root list and for the number of marked nodes, the potential function is:

Operations and Amortized Bounds

  1. INSERT(H, x) — amortized: Creates a singleton tree containing (x.mark = False), splices it into the root list, and updates H.min. Actual cost is and , so amortized cost is .
  2. UNION(H1, H2) — amortized: Concatenates the two circular root lists in time and picks the smaller min pointer ().
  3. EXTRACT-MIN(H) — amortized:
    • Promotes every child of H.min into the root list (clearing their mark bits) and removes H.min.
    • Consolidates the root list so that no two roots have the same degree: using an array A[0..D(n)], whenever two roots share degree , the larger-key root is linked as a child of the smaller-key root, increasing its degree to .
    • Because consolidation takes actual time and reduces to at most , the potential drop pays for processing the old roots, leaving amortized cost .
  4. DECREASE-KEY(H, x, k) — amortized:
    • Updates x.key = k. If the heap property with y = x.parent is violated, cut from , move to the root list, and clear x.mark.
    • Cascading cut on : if y is not a root and y.mark == False, set y.mark = True and stop. If y.mark == True, cut y from its parent, move y to the root list (y.mark = False), and continue upward until reaching an unmarked node or a root.
    • If cascading cuts occur, actual cost is , , and , giving:

so the terms cancel and the amortized cost is .

  1. DELETE(H, x) — amortized: Performs DECREASE-KEY(H, x, -\infty) () followed by EXTRACT-MIN(H) ().
Theorem

Maximum Degree Bound via Fibonacci Numbers

Every node of degree in an -node Fibonacci heap has subtree size at least , where is the -th Fibonacci number () and . Consequently, the maximum degree of any node satisfies:

Comparison of Binary, Binomial, and Fibonacci Heaps
OperationBinary Heap (Worst-Case)Binomial Heap (Worst-Case)Fibonacci Heap (Amortized)
MAKE-HEAP
INSERT
MINIMUM
EXTRACT-MIN
UNION
DECREASE-KEY
DELETE

2.2 Splay trees

A splay tree (Sleator & Tarjan, 1985) is a self-adjusting binary search tree that maintains no balance metadata (no height, color, or size fields) yet guarantees amortized time per dictionary operation (SEARCH, INSERT, DELETE, SPLIT, JOIN).

Definition

Splaying Rotations (Zig, Zig-Zig, Zig-Zag)

Whenever a node is accessed, SPLAY(x) repeatedly rotates upward until becomes the root of the tree, choosing one of three cases at each step based on 's parent and grandparent :

  1. Zig (single rotation): is the root. Rotate edge (left if is right child of , right if is left child).
  2. Zig-Zig (same-side double rotation): is not the root, and and are both left children (or both right children). First rotate , then rotate .
  3. Zig-Zag (opposite-side double rotation): is not the root, and is a left child while is a right child (or vice versa). First rotate , then rotate .

Amortized Analysis (Access Lemma)

Assign each node a positive weight (commonly ). Let be the subtree weight and define the rank , with potential .

Theorem

Splay Access Lemma and Optimality Properties

For a single splay step on moving to with root :

Telescoping over the entire SPLAY(x) to root gives amortized cost at most . Setting weights appropriately yields:

Example 1

1

  1. In a Fibonacci heap, find the minimum possible number of nodes in a tree rooted at a node of degree . What is the maximum possible node degree in a Fibonacci heap containing nodes?
  2. A left-leaning chain of nodes has root , left child , left grandchild , and left great-grandchild . Trace SPLAY(10) step by step, naming each rotation case.

Fibonacci heap minimum subtree size for degree : By Theorem 2.1, a node of degree has at least nodes in its subtree (counting itself). For , we need :

So a degree- node requires at least nodes.

Maximum degree for nodes: Find the largest such that :

Since gives , the maximum possible degree is . (Equivalently, .)

Trace SPLAY(10) on the left chain :

  • First step (Zig-Zig at ): Both and are left children. First right-rotate so becomes the left child of with right child . Next right-rotate so becomes the left child of , with right child (whose right child is ).
  • Second step (Zig at ): Now is the root and is its left child. Right-rotate . Now is the root, its right child is , 's left child is , and 's right child is (depth reduced from to ).
Answer:
  1. Minimum subtree size for degree is nodes (); maximum degree in a -node Fibonacci heap is .
  2. SPLAY(10) performs a left-left Zig-Zig on followed by a left Zig on , leaving at the root with right spine .

2.3 Bloom filters

A Bloom filter (Burton Bloom, 1970) is a compact, probabilistic bit-array data structure for testing set membership (INSERT and QUERY) in time using far less memory than storing the keys themselves.

Definition

Bloom Filter Parameters and Operations

A Bloom filter consists of:

Operations:

False Positive Probability and Optimal Sizing

After inserting distinct elements ( independent bit-setting probes), the probability that a specific bit remains is:

For an uninserted query element , all probed bits are (a false positive) with probability:

Minimizing with respect to yields the optimal number of hash functions and required bit-array size:

Example 2

2

A Bloom filter has bits and is designed to store keys.

  1. Calculate the optimal number of hash functions (rounded to the nearest integer).
  2. Using that integer , compute the resulting false positive probability .

Optimal number of hash functions:

False positive probability for :

Answer:

The optimal integer number of hash functions is , yielding a false positive probability of () using only bits ( bytes) per key.


2.4 Segment trees

A segment tree is a static binary tree built over an array that supports both associative range queries (such as range sum, range minimum/maximum, range GCD, or XOR) and updates in time.

Definition

Segment Tree Node Invariant and Layout

Each node in a segment tree corresponds to a contiguous subarray interval :

Using 1-based heap indexing (left = 2*v, right = 2*v + 1), an array of size guarantees no out-of-bounds access for any .

Complexities and Lazy Propagation

Segment Tree with Point Update and Range Sum QueryPython
class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)

    def _build(self, arr, v, l, r):
        if l == r:
            self.tree[v] = arr[l]
            return
        m = (l + r) // 2
        self._build(arr, 2 * v, l, m)
        self._build(arr, 2 * v + 1, m + 1, r)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def update(self, idx, val, v=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if l == r:
            self.tree[v] = val
            return
        m = (l + r) // 2
        if idx <= m:
            self.update(idx, val, 2 * v, l, m)
        else:
            self.update(idx, val, 2 * v + 1, m + 1, r)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def query(self, ql, qr, v=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if ql > r or qr < l:
            return 0
        if ql <= l and r <= qr:
            return self.tree[v]
        m = (l + r) // 2
        return self.query(ql, qr, 2 * v, l, m) + self.query(ql, qr, 2 * v + 1, m + 1, r)

2.5 Disjoint set union

A Disjoint Set Union (DSU) or Union-Find structure maintains a collection of pairwise disjoint dynamic sets over elements, identifying each set by a canonical representative.

Definition

Disjoint Set Operations

Representing each set as a rooted tree where parent[x] points toward the root (and parent[root] = root), naive UNION can create a degenerate chain of height , making FIND-SET take time. Two classic heuristics eliminate this:

  1. Union by Rank (or Union by Size): Maintain rank[root] (an upper bound on subtree height). When merging two roots and , attach the smaller-rank root under the larger-rank root; increment rank by only when rank[r_x] == rank[r_y]. Alone, this guarantees tree height , giving worst-case time per operation.
  2. Path Compression: During FIND-SET(x), after finding the root , redirect parent[u] = r for every node visited along the find path so subsequent lookups reach in time.
Theorem

Tarjan's Amortized Bound for DSU

With both union by rank (or size) and path compression, any sequence of MAKE-SET, UNION, and FIND-SET operations on elements runs in:

total time, where is the inverse Ackermann function ( for every up to , making each operation effectively constant time in practice).

Example 3

3

  1. Build a range-sum segment tree over the array (0-indexed). List the values at the root and its children and , compute query(1, 4), and find the updated values after update(2, 7).
  2. Starting from singleton sets (all rank ), trace UNION(1, 2), UNION(3, 4), UNION(2, 4) (attach second root under first on tie), UNION(5, 6), UNION(4, 6), and FIND-SET(6) with path compression.

Segment tree node values and query on :

  • Left half sums (split into and ).
  • Right half sums (split into and ).
  • Root stores .
  • Query decomposes into (), (), and (), returning .
  • After update(2, 7) (increase by ), nodes , , and ; now query(1, 4) returns .

DSU trace with union by rank and path compression:

  • UNION(1, 2): ranks equal () parent[2] = 1, rank[1] = 1.
  • UNION(3, 4): ranks equal () parent[4] = 3, rank[3] = 1.
  • UNION(2, 4): FIND(2) = 1 (rank ), FIND(4) = 3 (rank ). Tie parent[3] = 1, rank[1] = 2.
  • UNION(5, 6): ranks equal () parent[6] = 5, rank[5] = 1.
  • UNION(4, 6): FIND(4) walks (compresses parent[4] = 1); FIND(6) = 5 (rank ). Since rank[1] = 2 > rank[5] = 1, parent[5] = 1 (rank[1] stays ).
  • FIND-SET(6): walks , returning representative and compressing parent[6] = 1 directly.
Answer:
  1. Initial segment tree: root , left , right , query(1, 4) = 19. After update(2, 7): root , , and query(1, 4) = 25.
  2. After all unions and FIND-SET(6), the single tree has root (rank = 2) with direct children .

Exercises

Practice Exercises — Advanced Data Structures

Question 1

Define the potential function of a Fibonacci heap and prove why DECREASE-KEY achieves amortized time even when cascading cuts occur. Suppose a heap has root trees and marked nodes, and DECREASE-KEY performs an initial cut plus cascading cuts (causing the final unmarked ancestor, which is not a root, to become marked). Compute , , and .

Amortized proof for DECREASE-KEY with cascading cuts: Suppose DECREASE-KEY(H, x, k) performs initial cut of and cascading cuts of marked ancestors before stopping at an unmarked ancestor (or a root). Each cut takes actual work, so total actual cost is (in unit-cost steps).

  • Each of the cuts adds a new tree to the root list, so .
  • Each of the cascadingly cut ancestors was previously marked and becomes unmarked when promoted to a root, while at most unmarked ancestor becomes newly marked, so .
  • Therefore , and amortized cost .

Numerical potential change ():

  • Initial potential: .
  • After cuts: .
  • Two marked nodes lose their marks () and the final non-root ancestor becomes marked (): .
  • New potential: , so .
Answer:

gives , canceling the cascading-cut cost to leave amortized time. In the given state, , , and .

Question 2

Explain the three rotation cases (Zig, Zig-Zig, and Zig-Zag) in a splay tree and state why Zig-Zig rotates before rather than rotating up one edge at a time. Starting from a right-leaning chain (root ), trace SPLAY(5) and show the resulting tree shape.

Three rotation cases and why Zig-Zig order matters:

  • Zig: is the root; perform one single rotation on .
  • Zig-Zig: and are on the same side of their parents; rotate first, then .
  • Zig-Zag: and are on opposite sides; rotate first, then .

Rotating first in Zig-Zig compresses paths by halving the depth of nodes along the path; naive bottom-up single rotations merely shift the chain to the other side without shrinking depth, failing the amortized bound.

Trace SPLAY(5) on right chain :

  • Zig-Zig on : Left-rotate giving (with left child , right child ), then left-rotate giving (with left child , whose left child is ).
  • Zig-Zig on : Left-rotate giving root (left child , right child ), then left-rotate giving root with left child , 's left child , and 's right child (whose left child is ).
Answer:

Zig handles a root parent, Zig-Zig handles same-side grandparent paths ( then to halve depths), and Zig-Zag handles opposite-side paths. After SPLAY(5) on , is the root with left child , where has left child and right child (with left child ), reducing max depth from to .

Question 3

A web crawler needs a Bloom filter to track visited URLs with a target false positive rate of (). Compute the required bit-array size (in bits and KB) and the optimal number of hash functions . Also explain why standard Bloom filters do not support deletion and how Counting Bloom Filters solve this.

Compute bit-array size :

Compute optimal and explain deletion:

Standard Bloom filters cannot delete a key by resetting its bits to because another inserted key may share one or more of those bit positions, causing false negatives. A Counting Bloom Filter replaces each -bit cell with a small multi-bit counter (typically bits), incrementing on insert and decrementing on delete.

Answer:

The Bloom filter needs bits () and hash functions. Standard Bloom filters prohibit deletion because clearing shared bits creates false negatives; Counting Bloom Filters solve this by storing small integer counters instead of single bits.

Question 4

Explain how lazy propagation enables range updates in a segment tree. Given the -element array (0-indexed), suppose we execute a range-add update adding to all indices in followed by a range-sum query on . Trace which nodes receive lazy tags and compute the resulting sum.

Lazy propagation mechanism: When a range update covers a segment tree node's interval completely, we update tree[v] += (r - l + 1) * delta, store lazy[v] += delta, and return immediately without descending to descendants. Pending tags are pushed down to children only when a subsequent traversal needs to inspect a strict subinterval of , keeping both range updates and range queries at .

Trace range-add on over : The root splits into and :

  • In : is outside ; is completely inside , so tree[[2,3]] increases from to and receives lazy = +3.
  • In : is completely inside , so tree[[4,5]] increases from to and receives lazy = +3. On , is outside and leaf increases from to .
  • Querying visits the exact same three covering nodes , , and :
Answer:

Lazy propagation defers updates to descendants in lazy[v] until a child is visited. Adding on sets lazy tags on and (plus leaf ), yielding a range sum of .

Question 5

State the worst-case time complexity of Disjoint Set Union (DSU) with (a) naive linking, (b) union by rank only, and (c) union by rank combined with path compression for a sequence of operations on elements. Prove why union by rank alone bounds the height of any tree in the forest to at most .

Complexities for operations on elements:

  • (a) Naive linking: (degenerate chain of length ).
  • (b) Union by rank only: (each FIND-SET traverses at most the tree height ).
  • (c) Union by rank + path compression: amortized, where is the inverse Ackermann function.

Proof by induction that a root of rank has at least nodes:

  • Base case (): A singleton tree has node.
  • Inductive step: A tree's rank increases from to only when two trees of equal rank are merged. By the inductive hypothesis, each tree has at least nodes, so the merged tree has at least nodes. (Merging unequal ranks leaves the larger rank unchanged and strictly increases node count.)

Since the total number of nodes is , we have . Without path compression, rank equals tree height, so height .

Answer:

DSU takes naively, with union by rank alone, and amortized with union by rank plus path compression. By induction, any rank- tree contains at least nodes, bounding height by .

← Advanced Analysis TechniquesAdvanced Graph Algorithms →