Skip to main content

Balanced Trees and Union-Find Lab

Retrieval Prompts​

  1. State the BST property in terms of left subtree, node, and right subtree.
  2. State the five red-black invariants from memory.
  3. State the AVL balance-factor invariant.
  4. Give the union-find API and explain what find(x) == find(y) means semantically.
  5. State the amortized cost of find under union by rank plus path compression, and what function controls it.

Compare and Distinguish​

Separate these pairs clearly:

  • red-black tree versus AVL tree (which is strictly more balanced, which is faster to update)
  • AVL single rotation versus double rotation (which imbalance shapes trigger each)
  • skip list versus red-black tree (deterministic worst-case vs expected)
  • union by rank versus union by size (what each measures)
  • path compression versus path halving (compression flattens; halving only skips every other pointer)

Common Mistake Check​

For each statement, identify the error:

  1. "A BST with the BST property is always balanced."
  2. "Inserting a new node into a red-black tree and coloring it black preserves all invariants."
  3. "Union-find supports deletion of an edge by calling split(u, v)."
  4. "A skip list guarantees O(log n) worst-case per operation."
  5. "Path compression reduces the stored rank of the root."

Mini Application​

Do all four tasks for each scenario:

  1. state which structure you would use and why
  2. sketch its invariant or defining randomization
  3. estimate the time per operation and cite the bound source
  4. explain one failure mode and how to detect it

Scenarios:

  1. a task scheduler that stores jobs in priority order and needs O(log n) insert, O(log n) min-extract, and O(n) iteration in sorted order
  2. a graph problem that receives 1,000,000 edges in arbitrary order and must answer connected?(u, v) queries on the fly
  3. an in-memory ordered map for a 10,000-request-per-second service where deterministic worst-case matters
  4. a concurrent ordered set for a NoSQL database where simplicity of locking matters more than tightest bound

Evidence Check​

This page is complete only if, for each structure above, you can:

  • write the invariant or key property in one sentence
  • sketch a small worked example by hand (insert 4 elements, trace 1 find or query)
  • state the cost per operation and the reason for the cost
  • name at least one production system that uses it