Union-Find (Disjoint Set Union) تتابع تقسيم العناصر إلى مجموعات منفصلة وتدعم عمليتين قريبتين من O(1): find (في أي مجموعة توجد x؟) وunion (دمج مجموعتين). إنها تتفوق في استعلامات الاتصال.
الفكرة الأساسية
كل مجموعة عبارة عن شجرة بعقدة تمثيلية جذر. مع و، تعمل العمليات في وقت قريب من الثابت (Ackermann معكوس، α(n)).
