ساختارهای داده مجموعه‌های مجزا: Union-Find با Rank و Path Compression

نوع داده انتزاعی مجموعه‌مجزا

یک ساختار داده Disjoint-Set (مجموعه‌مجزا) (که Union-Find نیز نامیده می‌شود) یک مجموعه از مجموعه‌های بدون‌هم‌پوشانی را نگه می‌دارد، و سه عملیات را پشتیبانی می‌کند: MAKE-SET(x) یک مجموعه جدید شامل فقط x می‌سازد، UNION(x, y) مجموعه‌های شامل x و y را در یکی ادغام می‌کند، و FIND-SET(x) یک عنصر نماینده را برمی‌گرداند که مشخص می‌کند x در حال حاضر به کدام مجموعه تعلق دارد.

نمایش مجموعه‌ها به‌عنوان درخت‌ها

پیاده‌سازی استاندارد، به نام Disjoint-Set Forest (جنگل مجموعه‌مجزا)، هر مجموعه را به‌عنوان یک درخت نمایش می‌دهد، جایی که هر گره فقط به والدش اشاره می‌کند، و ریشه درخت به‌عنوان نماینده مجموعه عمل می‌کند.

MAKE-SET(x):
  x.p = x           // x والد خودش است، یک درخت تک‌گره تشکیل می‌دهد
  x.rank = 0

FIND-SET(x):
  اگر x ≠ x.p:
      FIND-SET(x.p) را برگردان
  x را برگردان

UNION(x, y):
  LINK(FIND-SET(x), FIND-SET(y))

LINK(x, y):
  x.p = y           // y را والد x می‌کند، دو درخت را ادغام می‌کند

این نسخه ساده به‌درستی کار می‌کند، اما یک ضعف جدی دارد: اتصال مکرر درخت‌ها به ترتیب بدشانس می‌تواند یک درخت تولید کند که به یک زنجیره طولانی تنزل یابد، که FIND-SET را در بدترین‌حالت زمان Θ(n) می‌کند — همان خطر ساختار نامتوازن که درخت‌های قرمز-سیاه که پیش‌تر در این مجموعه بحث شد را انگیزه داد.

بهینه‌سازی اول: Union by Rank

Union by Rank یک کران بالای تقریبی روی ارتفاع هر درخت، به نام Rank، ردیابی می‌کند، و همیشه درخت کوتاه‌تر را زیر ریشه درخت بلندتر در طول یک union متصل می‌کند، به‌جای انتخاب دلخواه یک جهت.

LINK(x, y):
  اگر x.rank > y.rank:
      y.p = x
  در غیر این صورت:
      x.p = y
      اگر x.rank == y.rank:
          y.rank = y.rank + 1

از آنجا که درخت کوتاه‌تر همیشه زیر بلندتر متصل می‌شود، ارتفاع درخت حاصل فقط زمانی افزایش می‌یابد که دو درخت در حال ادغام رتبه برابر داشته باشند، و حتی آنگاه، فقط یک سطح. این از نظر روحی مشابه با بینش تقسیم-متوازن که پیش‌تر در این مجموعه درباره درخت‌های B و درخت‌های قرمز-سیاه بحث شد است: ترتیب اتصال دقیق از ساختار زنجیره‌ای آسیب‌شناختی که در غیر این صورت ممکن بود جلوگیری می‌کند.

با استفاده فقط از union by rank، می‌توان اثبات کرد یک درخت با رتبه r حداقل 2^r گره دارد، که یعنی حداکثر رتبه ممکن برای n عنصر O(log n) است، که هر عملیات FIND-SET را به زمان O(log n) محدود می‌کند — از قبل بهبود چشمگیری نسبت به بدترین‌حالت O(n) بهینه‌نشده.

بهینه‌سازی دوم: Path Compression

Path Compression (فشرده‌سازی مسیر) در طول خود FIND-SET اعمال می‌شود: همان‌طور که الگوریتم در درخت بالا می‌رود تا ریشه را پیدا کند، هر گره بازدیدشده در طول مسیر را طوری می‌کند که مستقیماً به ریشه اشاره کند، و درخت را برای هر پرس‌وجوی آینده شامل آن گره‌ها صاف می‌کند.

FIND-SET(x):
  اگر x ≠ x.p:
      x.p = FIND-SET(x.p)     // به‌طور بازگشتی ریشه را پیدا کن،
                                // سپس x را مستقیماً به آن متصل کن
  x.p را برگردان

پیش از FIND-SET(d)، با زنجیره a-b-c-d:
a → b → c → d(ریشه)

پس از FIND-SET(d):
a → d(ریشه)
b → d(ریشه)
c → d(ریشه)
(هر گره روی مسیر اکنون مستقیماً به ریشه اشاره می‌کند)

این بهینه‌سازی