Union-Find (Disjoint Set Union) تتابع تقسيم العناصر إلى مجموعات منفصلة وتدعم عمليتين قريبتين من O(1): find (في أي مجموعة توجد x؟) وunion (دمج مجموعتين). إنها تتفوق في استعلامات الاتصال.
كل مجموعة عبارة عن شجرة بعقدة تمثيلية جذر. مع و، تعمل العمليات في وقت قريب من الثابت (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
بدون ضغط المسار والاتحاد حسب الرتبة، تتدهور الأشجار إلى سلاسل O(n). لا تدعم تقسيم المجموعات بكفاءة.
Union-Find تجيب على "هل هذان الشيئان متصلان؟" بنطاق ضخم بدون تكاليف تقريباً.
هي محرك Kruskal's MST والعديد من خوارزميات الرسم البياني والتجميع.
تحسيناتها هي درس مذكور لكيفية أن الحيل الهيكلية الصغيرة تحقق أداءً قريباً من ثابت الوقت.