Union-Find (Disjoint Set Union) seuraa elementtien jakautumista disjunkteiksi joukoiksi ja tukee kahta lähes O(1):n operaatiota: find (missä joukossa x on?) ja union (kahden joukon yhdistäminen). Se on erinomainen yhteyskytkentä-kyselyissä.
Jokainen joukko on puu, jolla on edustajajuurena oleva solmu. ja -optimisaatioilla operaatiot suorittautuvat lähes vakioajassa mielessä (käänteinen 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
Ilman polun pakkautumista ja union by rank -optimisaatiota puut degeneroituvat O(n)-ketjuiksi. Se ei tue tehokkaasti joukkojen jakamista.
Union-find vastaa kysymykseen "ovatko nämä kaksi asiaa yhteydessä toisiinsa?" massiivisessa mittakaavassa lähes ilman kustannusta.
Se on Kruskalin MST:n ja monien graafi- ja klusterointialgoritmin sydän.
Sen kaksi optimisaatiota ovat muistettava opetus siitä, kuinka pienet rakenteelliset temput tuottavat lähes vakioaikaisen suorituskyvyn.