Union-Find (Disjoint Set Union) عناصر کی تقسیم کو غیر متقاطع مجموعوں میں ٹریک کرتا ہے اور دو تقریباً O(1) آپریشنز کو سپورٹ کرتا ہے: find (x کس مجموعے میں ہے؟) اور union (دو مجموعوں کو ملائیں)۔ یہ connectivity کے سوالات میں بہترین ہے۔
ہر مجموعہ ایک نمائندہ جڑ کے ساتھ ایک درخت ہے۔ اور کے ساتھ، آپریشنز تقریباً مستقل وقت میں چلتے ہیں (inverse 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
Path compression اور union by rank کے بغیر، درخت O(n) chains میں خراب ہو جاتے ہیں۔ یہ مجموعوں کے splitting کو موثر انداز میں سپورٹ نہیں کرتا۔
Union-find بہت بڑے پیمانے پر "کیا یہ دونوں چیزیں جڑی ہوئی ہیں؟" کا جواب تقریباً کوئی لاگت کے ساتھ دیتا ہے۔
یہ Kruskal's MST اور بہت سے graph اور clustering algorithms کے اندر انجن ہے۔
اس کی دونوں بہتریاں ایک یادگار سبق ہیں کہ چھوٹی ساختی تدابیر تقریباً مستقل وقت کی کارکردگی کیسے حاصل کرتی ہیں۔