Visualizer CodeViz · Algorithms, visualized

Part I · Union–Find · week 1

Quick-union

Reinterpret the same array as parent pointers. Union changes exactly one entry, but the trees can grow tall, and then find has to walk them.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

unionO(tree height)
findO(tree height)
worst caseO(n) — a path
spaceO(n)

Reference: Sedgewick & Wayne, §1.5.

Quick-union in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class QuickUnionUF:
    # id[i] is the PARENT of i; a root is its own parent. The array is now
    # a forest of trees, one per component, and find walks to a root.

    def __init__(self, n):
        self.id = list(range(n))

    def find(self, p):
        while p != self.id[p]:            # chase parent pointers
            p = self.id[p]
        return p                          # the root names the component

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        i, j = self.find(p), self.find(q)
        if i == j:
            return
        self.id[i] = j                    # ONE entry changes

Why it works

The reinterpretation

Same array, different meaning: id[i] is now i's parent, not its component name. A component is a tree, and the tree's root is its name. That single change of interpretation turns the expensive part of quick-find (relabelling) into one assignment.

Where the cost went

It moved into find. The loop while p != self.id[p] runs once per level, so everything costs the height of the tree. Nothing in this code controls that height — union(p, q) always hangs p's root under q's root, however lopsided that makes things.

Run the worst case: a path preset: 0-1 1-2 2-3 … builds a single chain of n nodes, and find on its deep end walks all of it. Quick-union is not better than quick-find; it is differently bad.

The fix, in one line

The whole problem is which root goes under which. Weighted quick-union answers it (hang the smaller tree) and gets a guaranteed height of at most lg n. Read the two find loops side by side: identical code, tree height decides everything.

What to try in the animation

n sites, then a list of p-q pairs to connect. The default is tinyUF.txt from the course.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Quick-union in the player →

The rest of Union–Find