9.2. Diszjunkt-halmaz erdők

Egy másik ábrázolásnál egy-egy diszjunkt halmazt egy-egy fával ábrázolunk.

9.2. ábra - Diszjunkt-halmaz erdő ábrázolás

Diszjunkt-halmaz erdő ábrázolás


A halmaz képviselője a fa gyökerében lévő elem. A HALMAZT-KÉSZÍT művelet ekkor egy gyökérből álló fát hoz létre. A HALMAZT-KERES művelet az apa-mutatókat járja be, s jut el a gyökérig, azaz a fa magasságával arányos bonyolultságú. Az EGYESÍT művelet az egyik fát a másik gyökere alá fűzi be. Ez bizonyos esetekben igen rossz fákat eredeményez, ezért különböző módszerekkel javíthatunk a hatékonyságon. Ennek keretében minden elemhez hozzárendelünk egy számértéket: a rangot, ami nagyjából az elemhez tartozó fa magasságát jelzi. Ez a rang kezdetben 0. Az egyesítésnél a rangok alapján dönt a program arról, hogy a magasabb fa alá szúrja be az alacsonyabbat, illetve ha két fa egyforma magas, akkor mindegy, hogy melyiket szúrjuk be, de ekkor a megváltozott rangot be kell állítani. A keresés eljárása pedig a reprezentáns megtalálása mellett mellékhatásként összekuszálja a fát olyan értelemben, hogy a gyökértől eltekintve a keresett elemtől a gyökérig vezető úton minden elemet a gyökér alá fűz be. Ezzel pedig lényegesen csökkentheti a fa magasságát. Ezen heurisztikákat követve n elem ű diszjunkt-halmazon m művelet bonyolultsága O(mln n), ahol ln a lánchatványozás (222...) inverze.

Procedure HALMAZT-KÉSZÍT(x) 
Input: x elem 
Eredmény: Létrehoz egy fát, melynek egyetlen csúcsa a megadott elem 
1 x.apa = x 
2 x.rang = 0 

Procedure EGYESÍT(x,y) 
Input: két elem 
Eredmény: a két elemet tartalmazó diszjunkt halmazokat összekapcsolja 
1 ÖSSZEKAPCSOL((HALMAZT-KERES(x),HALMAZT-KERES(y)) 

Procedure ÖSSZEKAPCSOL(x,y) 
Input: két gyökér 
Eredmény: a kisebb fát a nagyobb gyökere alá fűzi 
1 if x.rang ≥ y.rang then 
2    y.apa = x 
3 else 
4    x.apa = y
5 endif 
6 if x.rang == y.rang then 
7    y.rang = y.rang + 1
8 endif 

Function HALMAZT-KERES(x) 
Input: x elem 
Output: Az x reprezentánsa 
1 if x.apa != x then 
2    x.apa = HALMAZT-KERES(x.apa) 
3 endif
4 return x.apa