Union-Find (Disjoint Set Union) sporer en partition af elementer i disjunkte mængder og understøtter to næsten-O(1) operationer: find (hvilken mængde tilhører x?) og union (flet to mængder). Det er fremragende til konnektivitets-forespørgsmål.
Hver mængde er et træ med en repræsentativ rod. Med og køres operationerne i næsten konstant tid (invers Ackermann, α(n)).
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # compress
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller under larger
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
Uden path compression og union by rank degenereres træer til O(n) kæder. Det understøtter ikke effektiv opdeling af mængder.
Union-find besvarer "er disse to ting forbundne?" i enormt omfang med næsten ingen omkostninger.
Det er motoren bag Kruskals MST og mange graf- og klusteringsalgoritmer.
Dets to optimeringer er en mindeværdig lektion i, hvordan små strukturelle tricks giver næsten konstant-tid ydeevne.