#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/path-compression

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/path-compression

Repovive

Path Compression - Union-Find | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Path Compression

Flattening during find

Path compression makes every node on the find path point directly to the root:

function find(x):
    if this.parent[x] != x:
        this.parent[x] = this.find(this.parent[x])
    return this.parent[x]

After calling find(x), every node from $x$ to the root now points directly to the root. Future finds on these nodes are $O(1)$ .

Example: chain $1 \to 2 \to 3 \to 4$ (4 is root). After find(1):

$1 \to 4$
$2 \to 4$
$3 \to 4$
$4 \to 4$ (root)

The tree flattens completely. You see the power of path compression. Even if trees get tall temporarily, find operations flatten them.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!