Balanced Trees and Union-Find Lab

Budget 7–9 focused hours for P1–P7. Keep a first attempt, invariant and counterexample before opening solutions.

P1: global BST validation

Explain why root 10, left child 5, and 5's right child 12 violates ordering. Design a validator that also catches pointer cycles and shared children. Specify unique-key replacement and how a two-child deletion must handle values.

P2: red-black reasoning

Trace insertions 10,5,15,1 with classic recoloring rules. State NIL conventions and derive a logarithmic height bound from equal black height and no red adjacency. Explain why the result is not a bound on enumerating all items.

P3: AVL and order statistics

Trace insertion 3,1,2, replacement at key 1 and deletion of key 3. Give heights/sizes and rank(2), select(1). Explain why deletion may require repairs at several ancestors and why updating height alone is insufficient.

P4: randomized levels

For n=1024 and promotion probability 1/2, compute expected level-5 nodes and a union-bound estimate for any height at least 20. Distinguish these statements from a per-operation worst-case or complete search-time tail guarantee.

P5: relabeling analysis

Derive quadratic total work for arbitrary linked-list merges and O(n log n) for smaller-list relabeling. Give the per-element doubling argument. Explain why neither is a proof of the forest/compression inverse-Ackermann theorem.

P6: partition trace

On six vertices union (0,1),(2,3),(1,3),(4,4),(0,2). Record whether each changes the partition, component count and component sizes. Explain why root labels and nonroot size slots need not match between implementations.

P7: deleting duplicate edges

Insert two copies of edge 0-1, then delete each in turn. Report connectivity after each event. Explain why ordinary DSU cannot process these deletions and how reverse-time processing would need edge multiplicities and the complete sequence.