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

$ 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 units49h total

Open in Course

Path Compression

Flattening during find

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

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])
    return self.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.