Skip to main content

Advanced Data Structures: Worked Examples

Derive the next state before reading the answer. Fixtures are original teaching examples; the practice and assessment pages use separate attempts and feedback.

Example 1: ordering is global, metadata is local work​

Root 10 with left child 5 and 5's right child 12 violates a subtree bound even though immediate-child comparisons pass. Carry lower/upper bounds through the whole validation traversal. For AVL insertion [3,1,2], rotate left at 1 then right at 3. Root 2 has height 2 and size 3, with leaf heights/sizes

  1. Recomputing only the new root can leave stale data on the old root. Transfer: replace key 1's value; neither height nor size should grow.

Example 2: smaller-list union has a doubling proof​

Merging arbitrary lists can relabel components of sizes 1,2,...,n-1, giving quadratic total work. When always relabeling the smaller list, an element's component at least doubles each time it moves. At most floor(log2 n) moves per element gives O(n log n) total relabeling. This argument is about list merges, not a derivation of the stronger forest/compression alpha bound.

Example 3: the partition is not the graph​

Edges 0-1 and 1-2 connect three vertices. DSU can represent them with both 1 and 2 pointing to 0 even though 0-2 is not an input edge. Removing graph edge 1-2 cannot be modeled by blindly cutting a parent pointer. Kruskal must keep original chosen edge IDs separately from DSU routing pointers. Transfer: with two copies of 1-2, deleting one still leaves connectivity.

Example 4: carrying a heap meld and transferring ownership​

Sizes 13 (1101 binary) and 3 (0011) have roots 0,2,3 and 0,1. Degree-zero roots link into degree one; the degree-one collision carries again, and collisions continue through degrees two and three, leaving degree four. There are 16 nodes. The implementation must allocate any skipped root slots when importing a higher-degree donor. After destructive meld, the donor is empty and may be reused without changing the receiver.

Example 5: append spikes and potential​

First nine append costs in the declared copy/write model are [1,2,3,1,5,1,1,1,9]. Copies total 15, writes 9, cumulative cost 24. For Phi=2*size-capacity, non-resize appends have charge 3. A resize from full c to 2c has actual c+1 and potential change 2-c, also charge 3. The first allocation costs 1 and raises potential by 1, charge 2. Transfer: allowing deletion requires a new potential or hysteresis analysis.

Example 6: queue accounting depends on the primitive​

Three enqueues cost three pushes. The first dequeue transfers all three elements using three input pops and three output pushes, then pops one output: cost 7. The next two dequeues cost 1 each. Total is 12. With Phi=2*len(In), enqueues have amortized charge 3 and dequeues 1. With Phi=len(In), the first dequeue's charge is 4, not constant independently of the number transferred. An aggregate bound may still be provable, but that coefficient does not give the claimed per-operation potential proof under this model.

Example 7: Fenwick cells are aligned intervals​

For array [1,2,3,4], one-based bit cells are [1,3,3,10] (excluding unused slot 0). Cell 4 covers [0,4); cell 3 covers [2,3). Add 2 at external index 1: update cells 2 and 4, giving [1,5,3,12]. Prefix(3) reads cells 3 and 2 for 8; sum [1,3) subtracts prefix(1)=1, giving 7. Prefix-minimum values cannot be subtracted to get arbitrary range minima.

Example 8: deferred assignment and addition do not commute​

On [1,2,3,4], assign the whole range to 5 then add 3. The composed tag is (1,3) after (0,5), yielding (0,8), so a length-2 subrange sums to 16. Reversing the updates produces (0,5) and sum 10. Identity (1,0) and assign-zero (0,0) must stay distinct. In the mixed fixture, add 2 on [1,4) then assign -1 on [2,4) gives [1,4,-1,-1], total 3.

Example 9: a branch must read the requested old root​

Version 0 is [1,2,3,4]. Fork it to set index 0 to 9: version 1 is [9,2,3,4], sum 18. Fork version 0 again to set index 3 to -1: version 2 is [1,2,3,-1], sum 5. Version 0 still sums to 10. If the second update incorrectly starts at the latest root, it produces sum 13. If updates mutate shared nodes, older sums change. Test both failure modes.

Example 10: a positive filter answer needs exact confirmation​

At n=1000 and target false-positive probability 0.01, the classical approximation suggests m≈9585.1 bits. Round up to 9586, choose k=7, and allocate 1199 payload bytes. The report measures a separate fixed sample, not a guarantee.

With m=k=1, inserting A makes every key query positive. If the exact store contains only A, querying B must still return absent after confirmation. Deleting A from the exact store need not clear the filter; leaving a stale positive only causes extra work. A newly published exact key missing from the filter, however, can make a negative shortcut wrong. Publication order is a correctness issue.