הצגת המקור של הדף "איחוד קבוצות זרות"

[[קובץ:Dsu disjoint sets init.svg|ממוזער|360px|לאחר הפעלת '''יצירה''' 8 פעמים, ייווצרו 8 יחידונים.]]
[[קובץ:Dsu disjoint sets final.svg|ממוזער|360px|אחרי כמה הפעלות של '''איחוד''', חלק מהקבוצות התאגדו יחדיו.]]

ב[[מדעי המחשב]], '''איחוד קבוצות זרות''' (באנגלית: '''Disjoint-Set Data Structure'''), הוא [[מבנה נתונים]] אשר מבצע מעקב אחרי [[קבוצה (מתמטיקה)|קבוצה]] של עצמים [[חלוקה (תורת הקבוצות)|המחולקים]] למספר של [[תת-קבוצה|תתי-קבוצות]] [[קבוצות זרות|זרות]] ולא חופפות.

'''אלגוריתם איחוד-חיפוש '''(באנגלית: '''Union-Find Algorithm'''), הוא [[אלגוריתם]] המבצע את שתי [[אופרטור|הפעולות]] השימושיות הבאות על מבנה נתונים זה:
* '''חיפוש''''' (Find)'': קביעה איזו קבוצה מכילה עצם ספציפי. פעולה זו יכולה גם לעזור בקביעה האם שני עצמים שייכים לאותה הקבוצה.
* '''איחוד''''' (Union)'': [[איחוד (מתמטיקה)|איחוד]] שתי קבוצות לכדי קבוצה אחת.
פעולה הכרחית נוספת היא '''יצירה''' (''MakeSet''), פעולה היוצרת קבוצה חדשה המכילה עצם אחד בלבד ([[יחידון|סינגלטון]]).

על מנת להגדיר פעולות אלו בצורה מדויקת יותר, נדרשת דרך לייצוג הקבוצות במבנה הנתונים. גישה שכיחה אחת היא בחירת עצם אחד מכל קבוצה להוות '''נציג''', אשר תפקידו לייצג את הקבוצה כולה. הפעלת '''חיפוש''' על עצם <math>x</math>, תחזיר את '''הנציג''' של הקבוצה אליה <math>x</math> שייך. באופן דומה, פעולת '''איחוד''' תקבל שני '''נציגים''' כ[[שגרה (תכנות)|ארגומנטים]]. בהמשך הדיון נעבוד תחת ההנחה שלא ניתן למחוק או להסיר עצמים ממבנה הנתונים.

== מימוש בעזרת רשימות מקושרות ==
גישה פשוטה ל[[מימוש]] מבנה הנתונים היא בעזרת שימוש ב[[רשימה מקושרת]]. כל קבוצה תיוצג באמצעות רשימה שתכיל את כל העצמים השייכים לקבוצה. ה'''נציג''' ייקבע כעצם שבראש הרשימה.

פעולת '''יצירה''' תיצור רשימה בעלת איבר אחד. פעולת '''איחוד''' תבצע [[שרשור (מחרוזות)|שרשור]] של שתי רשימות. אולם, בגישה ישירה זו, המימוש של פעולת '''חיפוש '''הוא יקר מבחינת [[סיבוכיות זמן]]. בעוד שתי הפעולות הראשונות עובדות בסיבוכיות של זמן קבוע, אותה מסמנים בעזרת ה[[סימון אסימפטוטי|סימון האסימפטוטי]] <math>O(1)</math>, פעולה זו תדרוש סיבוכיות ליניארית בגודל הרשימה, <math>O(n)</math>. זאת מכיוון שבפעולת חיפוש אנו נאלצים לסרוק רשימה החל מהעצם הנתון ועד לנציג (ראש הרשימה), אותו אנו מתבקשים להחזיר כ[[פלט]].

[[מעקף]] (''Workaround'') אפשרי לבעיה זו, הוא תוספת של [[מצביע]] לראש הרשימה מכל איבר (''Node'') ברשימה. בעזרת המצביע, נוכל פשוט לגשת ל'''נציג''' באופן מיידי, וכך פעולת '''חיפוש''' תיעשה בזמן קבוע. לעומת זאת, פעולת '''איחוד''' תידרש כעת לדאוג לתחזוקת המצביעים של איברי הרשימה המאוחדת. שהרי, לאחר שרשור שתי רשימות, חלק מהאיברים מחזיקים מצביעים לראש הרשימה הישנה, שאינו רלוונטי יותר כנציג. כתוצאה מכך, פעולת האיחוד תעבוד עתה בסיבוכיות ליניארית. המסקנה היא שהבעיה לא נפתרה, אלא הצגנו [[שקלול תמורות]] (''Tradeoff'') בין סיבוכיות פעולות האיחוד והחיפוש.

ייעול נוסף של המימוש כולל ביצוע מעקב אחר האורך של כל רשימה. אם נדאג תמיד לשרשר את הרשימה הקצרה אל הארוכה בזמן פעולת '''איחוד''', נוכל לשפר את סיבוכיות הזמן של ביצוע הפעולה.

=== ניתוח אסימפטוטי ===
נרצה לנתח באופן אסימפטוטי את סיבוכיות הפעולות על מבנה נתונים הממומש כמתואר לעיל (בעזרת רשימות מקושרות ועם שימוש במצביעים והשוואת אורכים). נראה כי סיבוכיות הזמן של ביצוע <math>m</math> פעולות על פני מבנה נתונים בעל <math>n</math> עצמים נתונה על ידי <math>O(m + n \log(n))</math> זמן.

נניח כי כל איבר ברשימה מקושרת שומר שני [[שדה (אחסון נתונים)|שדות]]: שם הרשימה אליה הוא שייך ([[מצביע]] לראש הרשימה) ואת אורכה של הרשימה. בנוסף, נניח כי מספר האיברים הכולל בכל הרשימות הוא <math>n</math> (כלומר, מבנה הנתונים מחזיק בסך הכל <math>n</math> עצמים). כפי שראינו, הפעולה היחידה שאינה עובדת בזמן קבוע היא פעולת '''איחוד'''. כזכור, מימשנו פעולה זו בעזרת שרשור רשימות. ברצוננו לאפשר את תחזוקתם של מאפייני הרשימה (שם ואורך) בכל האיברים ברשימה המאוחדת.

נבחר איבר כלשהו <math>x</math> מרשימה כלשהי. נרצה לספור כמה פעמים נצטרך לעדכן את שדה שם-הרשימה של האיבר <math>x</math> במקרה הגרוע ביותר. שדה זה מתעדכן בכל פעם שהרשימה אליה שייך <math>x</math> משורשרת אל רשימה אחרת. אם רשימתו משורשרת אל רשימה אחרת אזי, על פי הגדרתנו לעיל, הרשימה השנייה היא בהכרח ארוכה יותר. בכל פעם שתרחיש זה מתרחש, הרשימה אליה משתייך <math>x</math> לכל הפחות מכפילה את גודלה פי שניים (כי הרשימה אליה שורשר הייתה לכל הפחות באורך של הרשימה המקורית שלו).

אם כן, השאלה שנותרה היא ''"כמה פעמים ניתן להכפיל מספר פי שניים לפני שהוא עובר את הגודל ''<math>n</math>?''"'', שהרי לאחר מכן הרשימה שמכילה את <math>x</math> תכיל <math>n</math> איברים, וכל הפעולות על מבנה הנתונים יעבדו בזמן קבוע. התשובה לשאלה נתונה על ידי [[לוגריתם]] בבסיס 2 על מספר האיברים, כלומר בדיוק <math>\log_2(n)</math>.

המסקנה עד כה, היא שבהינתן עצם כלשהו ניתן לבצע עדכון של שדה שם-הרשימה לכל היותר <math>\log_2(n)</math> פעמים במקרה הגרוע ביותר. לכן, עדכון מבנה נתונים בעל <math>n</math> עצמים הממומש בשיטה שתוארה לעיל, ידרוש <math>O(n \log(n))</math> זמן במקרה הגרוע ביותר. כל פעולת חיפוש יכולה להיעשות ב-<math>O(1)</math> זמן עבור מבנה הנתונים מכיוון שכל איבר ברשימה מחזיק שדה הקובע את שם הרשימה ואנו דואגים לעדכן ולתקף שדה זה, לכן פעולות חיפוש או יצירה יעבדו בזמן <math>O(m)</math>. בסך הכל נקבל <math>O(m + n \log(n))</math> כרצוי.

תוצאה מעניינת נוספת היא [[ניתוח לשיעורין|הסיבוכיות המשוערכת]] של מבנה הנתונים. עבור <math>n</math> פעולות על <math>n</math> עצמים, תתקבל סיבוכיות משוערכת של <math>O(\log n)</math> עבור ביצוע פעולה יחידה.

== מימוש בעזרת יער של קבוצות זרות ==
[[יער (תורת הגרפים)|יער]] של קבוצות זרות הוא מימוש של מבנה הנתונים בו כל קבוצה מיוצגת בעזרת [[עץ (תורת הגרפים)|עץ]].

במימוש הנאיבי, '''הנציג''' של כל קבוצה מוגדר להיות שורש העץ. '''חיפוש''' עוקב אחרי אבותיהם של איברים בעץ עד למציאת השורש. '''איחוד''' ממזג שני עצים בעזרת קביעת שורשו של עץ אחד כאביו של שורשו של העץ השני. במימוש זה, הגישה אינה טובה יותר מגישת הרשימות המקושרות, כיוון שהעצים שנוצרים אינם מאוזנים מבחינת הסתעפות הבנים. בהמשך נציג שני שיפורים אפשריים לשיטת היער.

להלן מימוש אפשרי בשיטה הנאיבית. נשים לב כי לצורך מניעת טיפול [[מקרה קצה|במקרי קצה]], הגדרנו את אביו של שורש להיות השורש עצמו.

{{קוד-ויקי}}
<div class="mw-content-ltr">
  '''function''' ''MakeSet''(x)
      x.parent := x

  '''function''' ''Find''(x)
      if x.parent == x
         return x
      else
         return ''Find''(x.parent)

  '''function''' ''Union''(x, y)
      xRoot := ''Find''(x)
      yRoot := ''Find''(y)
      xRoot.parent := yRoot
</div>

=== איחוד על פי דרגה ===
העיקרון המנחה של גישה זו הוא שמירה על '''עומק''' עץ מינימלי, בעזרת שרשור העץ הקטן יותר (מבחינת עומק) אל שורשו של העץ הגדול יותר בזמן פעולת '''איחוד'''. כתוצאה מכך, העץ המאוחד יהיה בעל עומק גדול יותר [[אם ורק אם]] עומקי העצים שאוחדו היו זהים. בהקשר של האלגוריתם, המונח '''דרגה''' בא לידי שימוש במקום המונח עומק, מכיוון שכפי שנראה בהמשך, לאחר שיפורים באלגוריתם, ערך זה כבר לא יהיה זהה לעומק העץ על פי הגדרתו.

עצים בעלי איבר יחיד יוגדרו להיות בעלי '''דרגה''' 0, ובכל פעם ששני עצים מדרגה <math>r</math> מאוחדים, דרגת העץ המאוחד תוגדר <math>r+1</math>. נשים לב כי עבור עצים מדרגה שונה, דרגת העץ המאוחד תהיה זהה לדרגתו של העץ הגדול מביניהם.

שימוש בטכניקה זו לבדה מניב זמן ריצה של <math>O(\log n)</math> לכל פעולת '''איחוד '''או '''חיפוש '''על פני מבנה נתונים בעל <math>n</math> עצמים. [[פסאודו קוד]] עבור מימוש הפעולות '''יצירה '''ו'''איחוד''' תחת טכניקה זו מוצג להלן.

{{קוד-ויקי}}
<div class="mw-content-ltr">
  '''function''' ''MakeSet''(x)
      x.parent := x
      x.rank   := 0

  '''function''' ''Union''(x, y)
      xRoot := ''Find''(x)
      yRoot := ''Find''(y)
      if xRoot == yRoot
          return
 
      // x and y are not already in same set. Merge them.
      if xRoot.rank < yRoot.rank
          xRoot.parent := yRoot
      else if xRoot.rank > yRoot.rank
          yRoot.parent := xRoot
      else
          yRoot.parent := xRoot
          xRoot.rank := xRoot.rank + 1
</div>

=== דחיסת מסלולים ===
השיפור השני שנציג הוא ''דחיסת מסלולים''. נרצה לשטח את מבנה העץ בכל פעם שפעולת '''חיפוש''' מבוצעת עליו. הרעיון הבסיסי הוא שכל איבר בו אנו מבקרים בדרך אל השורש, יכול להתחבר ישירות אל השורש (כזכור, כל האיברים בעץ חולקים את אותו השורש שהוא גם ה'''נציג'''). בפועל, בעת חיפוש, נטפס באופן [[רקורסיה|רקורסיבי]] במעלה העץ ונערוך את מצביע האב של כל איבר במסלול כך שיצביע אל השורש. העץ המתקבל הוא שטוח יותר, תוצאה אשר ממריצה את זמני הריצה של פעולות עתידיות על מבנה הנתונים. פעולת '''חיפוש''' משופרת תמומש כדלהלן.

{{קוד-ויקי}}
<div class="mw-content-ltr">
  '''function''' ''Find''(x)
      if x.parent != x
         x.parent := ''Find''(x.parent)
      return x.parent
</div>

=== ניתוח אסימפטוטי משוערך ===
==== לוגריתם חוזר ====
הניתוח המוכר הראשוני של זמן לכל פעולה הוכח על ידי [[ג'ון הופקרופט|הופקרופט]] [[ג'פרי אולמן|ואולמן]] בשנת [[1973]] ונקבע בתור <math>O(\log ^* n)</math>, [[לוגריתם חוזר|הלוגריתם החוזר]].{{הערה|1={{cite journal |last1=Hopcroft |first1=J. E. |author1-link=ג'ון הופקרופט |last2=Ullman |first2=J. D. |author2-link=ג'פרי אולמן |year=1973 |title=Set Merging Algorithms |journal=SIAM Journal on Computing |volume=2 |issue=4 |pages=294–303 |doi=10.1137/0202024}}}} נוכיח כי עבור <math>m</math> פעולות של '''איחוד''' או '''חיפוש''', המופעלות על מבנה נתונים בעל <math>n</math> עצמים, מתקבל זמן ריצה של <math>O(m \log ^* n)</math>.

''[[למה (מתמטיקה)|למה]] 1:'' '''דרגת '''הצמתים לאורך מסלול '''חיפוש '''גדלה ממש.
:''הוכחה:'' נוכיח את הטענה בעזרת [[אינדוקציה]]. בתחילה, כל איבר נמצא בעץ נפרד (<math>n</math> עצים בעלי איבר יחיד). ברור כי הטענה מתקיימת באופן טריוויאלי. המקרה היחיד בו '''דרגה''' של צומת משתנה, היא כאשר מבצעים '''איחוד'''. כפי שהגדרנו לעיל, העץ בעל הדרגה הקטנה יותר, יחובר אל העץ בעל הדרגה הגדולה יותר. אם דרגות השורשים שנרצה לאחד שוות, אזי אם העצים הם מדרגה <math>r</math>, נקבל עץ בעל דרגה <math>r+1</math>, שהיא גדולה ממש. במהלך '''חיפוש''', כל הצמתים בהם אנו מבקרים בדרך אל השורש, מחוברים אליו ישירות. מכיוון שלשורש יש דרגה גדולה יותר מכל ילדיו, גם במקרה זה הטענה נשמרת.
''למה 2:'' לעץ בעל שורש עם '''דרגה''' <math>r</math> יש לפחות <math>2^r</math> איברים (כולל השורש).
:''הוכחה:'' בתחילה, כאשר כל איבר הוא השורש של העץ עצמו, הטענה מתקיימת באופן טריוויאלי, מכיוון שדרגת כל השורשים היא <math>0</math> ואכן ישנם בדיוק <math>1=2^0</math> צמתים בכל עץ (השורש עצמו בלבד). נניח כי לעץ בעל שורש עם דרגה <math>r</math> יש לפחות <math>2^r</math> צמתים בתת-העץ שלו. אז כאשר נבצע '''איחוד''' בין שני עצים מדרגה <math>r</math>, נקבל עץ בעל דרגה <math>r+1</math>, ובו לפחות <math>2^r+2^r=2^{r+1}</math> איברים. כאשר נבצע איחוד בין שני עצים מדרגות שונות, דרגת השורש לא תשתנה ומספר האיברים בעץ רק יגדל. בכל מקרה, הטענה נשמרת.

למה 3: המספר המרבי של צמתים בעלי '''דרגה''' <math>r</math> הוא לכל היותר <math>\frac{n}{2^r}</math>.

:''הוכחה:'' כפי שהראינו בעזרת ''למה 2'', אנו יודעים כי בעץ עם שורש מדרגה <math>r</math> יש לפחות <math>2^r</math> צמתים. נקבל את המספר המרבי של צמתים מדרגה <math>r</math> כאשר כל איבר מדרגה <math>r</math> יהיה השורש של עץ עם בדיוק <math>2^r</math> צמתים (אחרת, ישנם צמתים שהיו יכולים להיות משויכים לעץ אחר ולהגדיל את דרגת השורש שלו). במקרה זה, מספר הצמתים מדרגה <math>r</math> הוא בדיוק <math>\frac{n}{2^r}</math>. אם כן, במקרה הכללי, מספר האיברים יכול להיות רק [[קטן או שווה]] לגודל זה.

מטעמי נוחות, נגדיר ''דלי'': דלי הוא [[קבוצה (מתמטיקה)|קבוצה]] של צמתים בעלי דרגות.

בהינתן קבוצת עצמים (צמתים), אנו יוצרים דליים וממיינים אליהם צמתים על פי דרגותיהם ועל פי החוקיות הבאה: צמתים בעלי דרגה 0 ישוייכו לדלי שיתוייג ב-0, צמתים בעלי דרגה 1 ישוייכו לדלי שיתוייג ב-1, צמתים בעלי דרגה 2 או 3 ישוייכו לדלי שיתוייג ב-2, ובאופן כללי, צמתים בעלי דרגה בין <math>B</math> לבין <math>2^B-1</math> ישוייכו לדלי שיתוייג ב-<math>B</math>.

נוכל לבצע שתי אבחנות לגבי הדליים:

:1. מספר הדליים המרבי הוא לכל היותר <math>\log ^* n</math> (הלוגריתם החוזר).

:''הוכחה:'' כאמור, בדלי מספר <math>B</math> ימוקמו הצמתים בעלי דרגות בתחום הסגור <math>[{B,2^B-1}]</math>. בדלי הבא, ימוקמו הצמתים בעלי הדרגות בתחום הסגור <math>[{2^B,2^{2^B}-1}]</math>. אם כן, במעבר מדלי אחד למשנהו, אנו מוסיפים 2 אחד נוסף לחזקה. מספר הדליים שיתקבלו, בהינתן שישנם <math>n</math> צמתים, יהיה אם כן לכל היותר <math>\log ^* n</math> על פי הגדרתו.

:2. מספר הצמתים בדלי <math>[{B,2^B-1}]</math> הוא לכל היותר <math>\frac{2n}{2^B}</math>.

:''הוכחה:'' מספר הצמתים המרבי בדלי זה, על פי ''למה 3'': <math>\frac{n}{2^B}+\frac{n}{2^{B+1}}+\frac{n}{2^{B+2}}+\cdots +\frac{n}{2^{2^B-1}} \leq \frac{2n}{2^B}</math>. נעזרנו כאן בסכום של [[סדרה הנדסית]] בעלת מנה <math>\frac{1}{2}</math>. ניגש עתה להוכחת החסם על סיבוכיות זמן הריצה. כזכור, נוכיח כי עבור <math>m</math> פעולות של '''איחוד''' או '''חיפוש''', המופעלות על מבנה נתונים בעל <math>n</math> עצמים, מתקבל זמן ריצה של <math>O(m \log ^* n)</math>.לאחר <math>m</math> פעולות של '''איחוד''' או '''חיפוש''' ניוותר עם סדרת עצים <math>\{T_1,T_2,...\}</math>, אשר גודלם <math>\{n_1,n_2,...\}</math> בהתאמה, וכן בוצעו עליהם <math>\{m_1,m_2,...\}</math> פעולות בהתאמה. ובמילים אחרות, <math>m_i</math> פעולות איחוד/חיפוש בוצעו על צמתים של <math>T_i</math>.

כל צומת מתחיל כקבוצה בפני עצמה, המונה איבר יחיד, ולכן על מנת שהעץ <math>T_i</math> יהיה מגודל <math>n_i</math>, חייבים להפעיל לפחות <math>n_i-1</math> פעולות '''איחוד''' על העץ, ובפרט <math>m_i\geq n_i-1</math>.

נראה עתה כי לכל עץ <math>T_i</math>, עלות <math>m_i</math> הפעולות שבוצעו בו חסומה על ידי <math>O({({m_i+n_i})\log^* n})=O({m_i \log^* n})</math>.

:''הוכחה:'' עלות פעולת '''איחוד''' היא <math>O(1)</math> ולכן פעולות אלו עולות לכל היותר <math>O(m_i)</math>. עלות פעולת '''חיפוש''' היא ליניארית במספר הקשתות על המסלול אל השורש. נחלק קשתות אלו לשלושה סוגים:
:1. קשתות בין בן של שורש לבין שורש:

:קיימת לכל היותר קשת אחת כזו על כל מסלול חיפוש, מכאן שקשתות מסוג זה תורמות <math>O(m_i)</math>.

:2. קשתות בין צומת ואביו, הנמצאים בדליים שונים:

:על פי ''למה 1'', בעת עלייה במסלול חיפוש של צומת, אנו רק עולים בדרגה, לכן קשת מסוג '''2''' תתאים למעבר אל דלי עם דרגות גדולות יותר. המעבר ההפוך, אל דלי בעל דרגות קטנות יותר, אינו אפשרי. על פי ''אבחנה 1'' מספר הדליים הוא לכל היותר <math>\log ^* n</math>, על כן יהיו לכל היותר <math>\log ^* n</math> קשתות מסוג '''2'''. לכן על פני כל הפעולות על קשתות אלו, יתקבל זמן <math>O({m_i \log^* n})</math>.

:3. קשתות בין צומת ואביו, הנמצאים באותו דלי:

:נניח כי אנו מסיירים על העץ מצומת <math>u</math> אל צומת <math>v</math>, המחוברים ביניהם בעזרת קשת מסוג '''3'''. על פי הגדרת קשת זו, הצמתים שייכים לאותו הדלי. נניח אם כן כי הצמתים הם בעלי דרגה המשויכת לדלי <math>[{B,2^B-1}]</math>. מכיוון שאנו מבצעים כיווץ מסלולים ומכיוון שלכל צומת יש דרגה גדולה ממש מלכל צאצאיו (על פי ''למה 1''), אזי בכל פעם שבה נעלה בקשת מסוג '''3''', דרגת האב ''החדש'' של <math>u</math> גדלה. למעשה, דרגת האב של <math>u</math> לא יכולה לקטון. מספר הפעמים שדרגת האב של <math>u</math> יכולה לגדול ועדיין הקשת בין <math>u</math> לבין אביו תוגדר כקשת מסוג '''3''', הוא כגודלו של הדלי. אם כן, נוכל לחצות את הקשת לכל היותר <math>2^B-1-B</math> פעמים (בדיוק כגודל הדלי). גודל זה חסום מלמעלה על ידי <math>2^B</math>. ומכאן נקבל כי מספר הקשתות מסוג '''3''' הוא <math>\sum_{[B, 2^B - 1]} \sum_{u} 2^B</math>. על פי ''אבחנה 1'' ו''אבחנה 2'', נוכל להסיק כי <math>\sum_{[B, 2^B - 1]} \sum_{u} 2^B \le\sum_{B} 2^B\frac{2n}{2^B}\le 2n\log^*n</math>. מכאן שקשתות מסוג זה תורמות <math>O({n_i \log^* n})=O({m_i \log^* n})</math> (מעבר זה נובע מכך ש-<math>m_i \geq n_i-1</math>).
ולסיכום, העלות של <math>m_i</math> פעולות על העץ <math>T_i</math> מורכבת מהעלות של <math>O(m_i)</math> בזכות קשתות מסוג '''1''', <math>O(m_i \log ^* n)</math> בזכות קשתות מסוג '''2''' וכן <math>O(m_i \log ^* n)</math> בזכות קשתות מסוג '''3'''. העלות הכוללת של כלל הפעולות על העץ נתונה על ידי <math>O(m_i \log ^* n)</math>.
נסכום מסקנה זו על פני כל העצים במבנה הנתונים, כאשר נזכור כי <math>m=\sum{m_i}</math>, ונקבל כי העלות הסופית היא <math>O(m \log ^* n)</math>, כנדרש.

==== חסם הדוק יותר ====
למעשה, שימוש בטכניקות שפורטו לעיל יניב [[ניתוח לשיעורין|סיבוכיות משוערכת]] של <math>O(\alpha(n))</math> בלבד לכל פעולה, כאשר <math>\alpha(n)</math> היא [[פונקציה הופכית|הפונקציה ההופכית]] לפונקציה <math>n = f(x) = A(x,x)</math>, כאשר <math>A</math> היא [[פונקציית אקרמן]], הידועה בתכונתה כפונקציה שגדלה מהר מאוד. בתור ההופכית לפונקציית אקרמן, <math>\alpha(n)</math> היא בפועל פחות מ-5 לכל ערך מעשי של <math>n</math>. לדוגמה, המספר <math>9876!</math>, כאשר <math>!</math> הוא אופרטור ה[[עצרת (מתמטיקה)|עצרת]], הוא בעל 35,164 ספרות ומתקבל <math>\alpha(9876!)=5</math>).

כך, הסיבוכיות המשוערכת לפעולה היא למעשה קבוע זעיר. [[רוברט טרג'אן]] היה הראשון להוכיח את [[חסם (מתמטיקה)|החסם]] על [[סיבוכיות זמן|סיבוכיות הזמן]] במונחים של פונקציית אקרמן בשנת [[1975]].{{הערה|1={{cite journal |last1=Tarjan |first1=Robert Endre |author1-link=רוברט טרג'אן |year=1975 |title=Efficiency of a Good But Not Linear Set Union Algorithm |journal=Journal of the ACM |volume=22 |issue=2 |pages=215–225 |url=http://portal.acm.org/citation.cfm?id=321884 |doi=10.1145/321879.321884 }}}} אמנם הלוגריתם החוזר הוא פונקציה הגדלה מאוד לאט, אך לא באותה מידת איטיות כפי של פונקציית אקרמן ההופכית.

פרדמן (''Fredman'') וסאקס (''Saks'') הראו בשנת [[1989]] כי <math>\Omega(\alpha(n))</math> עצמים בהכרח זוכים לגישה על ידי פעולה כלשהי על מבנה הנתונים בממוצע. תוצאה זו מראה כי החסם שנמצא הוא [[אופטימיזציה (מתמטיקה)|אופטימלי]] מבחינה [[סימון אסימפטוטי|אסימפטוטית]].{{הערה|1={{Citation |first=M. |last=Fredman |authorlink=Michael Fredman |first2=M. |last2=Saks |title=The cell probe complexity of dynamic data structures |journal=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing |pages=345–354 |date=May 1989 |quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires &Omega;(''m'' &alpha;(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets. }}}}

== יישומים ==
איחוד קבוצות זרות יכול להוות [[מערכת מודל|מודל]] של [[חלוקה (תורת הקבוצות)|חלוקה של קבוצה]], כדי, לדוגמה, לעקוב אחרי [[גרף קשיר|רכיבי קשירות]] ב[[גרף (תורת הגרפים)|גרף]] לא מכוון. מודל זה יכול לעזור לנו בקביעה האם זוג צמתים בגרף שייכים לאותו רכיב קשירות, או האם הוספת קשת בין זוג צמתים תגרום ליצירת [[מעגל (תורת הגרפים)|מעגל]]. אלגוריתם איחוד-חיפוש נמצא בשימוש נרחב במערכות בעלות ביצועים ברמה גבוהה המממשות איחוד-גרפים (''Unification''), תהליך החישוב של הגרף הכללי ביותר המכליל את הגרפים שניתנו כקלט.{{הערה|1={{cite journal |last1=Knight |first1=Kevin|year=1989 |title=Unification: A multidisciplinary survey |journal=ACM Computing Surveys|pages=93–124 |url=http://portal.acm.org/citation.cfm?id=62030|doi=10.1145/62029.62030 |volume=21}}}} שימוש נוסף לדוגמה למימוש אלגוריתמים בתורת הגרפים, הוא מימוש [[האלגוריתם של קרוסקל]] למציאת [[עץ פורש מינימלי]].

מימוש ביטויי שוויון בשפת [[Fortran]] עושה שימוש באלגוריתם איחוד-חיפוש.

יישומים נוספים כוללים שימושים בתחומי [[עיבוד תמונה]], אלגוריתמי [[היסק]] וכן במידול מערכות פיזיקליות, כגון [[חלחול (תהליך)|חלחול]].

== קישורים חיצוניים ==
* [https://web.archive.org/web/20071108172118/http://www.boost.org/libs/disjoint_sets/disjoint_sets.html מימוש בשפת C++] כחלק [[ספרייה (תכנות)|מספריות השירות]] של ''Boost'' עבור שפת [[C++]]
* [http://algs4.cs.princeton.edu/15uf/UF.java.html מימוש בשפת ג'אווה], מתוך המהדורה הרביעית של ''Algorithms'' מאת ''Robert Sedgewick and'' ''Kevin Wayne''
* [http://www.cs.unm.edu/~rlpm/499/uf.html יישומון עם תצוגה גרפית בשפת ג'אווה], מאת ''Rory L. P. McGuire''
* ''[http://citeseer.ist.psu.edu/anderson94waitfree.html Wait-free Parallel Algorithms for the Union–Find Problem]'', [[מאמר מדעי|מאמר]] מאת ''Richard J. Anderson and'' ''Heather Woll'', המתאר מימוש [[עיבוד מקבילי#תכנות מקבילי|מקבילי]] של מבנה הנתונים ללא חסימות
* [http://code.activestate.com/recipes/215912-union-find-data-structure/ מימוש] בשפת [[פייתון]].
* [https://web.archive.org/web/20161202120715/http://www.mathblog.dk/disjoint-set-data-structure/ הסברים עם דוגמאות ומימוש] בשפת [[C sharp|C#]]
* [http://cgi.di.uoa.gr/%7Eewcg06/invited/Seidel.pdf Understanding the Inverse Ackermann Function], Raimund Seidel

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{מבני נתונים}}

[[קטגוריה:מבני נתונים]]
[[קטגוריה:אלגוריתמי חיפוש|עץ חיפוש]]