Pădurea de mulțimi disjuncte

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 noiembrie 2019; verificarea necesită 1 editare .

Pădurea mulțimilor disjunctive este o structură de date arborescentă pentru seturile disjunctive . (uneori numit Sistem de set disjunc )

Setați reprezentări

Fiecare set este reprezentat ca un arbore înrădăcinat . Într-o pădure de set disjunc, fiecare nod conține un element set și indică numai către nodul său părinte. Rădăcina fiecărui arbore conține un reprezentant și este părintele însuși.

Operațiile pe pădurea mulțimilor disjunse se efectuează după cum urmează:

MAKE_SET - creează un arbore cu un singur nod.

FIND_SET - ne deplasăm de-a lungul legăturilor părinte la rădăcina arborelui.

UNION - setează indicatorul rădăcinii unui arbore la rădăcina altuia.

Euristică pentru eficiență

Asociere după rang. Ideea euristicii este că atunci când se efectuează operația UNION, înălțimea arborelui rezultat, dacă este posibil, nu crește. Pentru aceasta, se folosește rangul caracteristic pentru fiecare rădăcină, care este limita superioară a înălțimii nodului. Operația MAKE_SET creează o rădăcină cu rangul 0. Operația UNION, care în acest caz se numește unire cu rang, funcționează după cum urmează:

Dacă rangurile rădăcinilor sunt diferite, rădăcina cu rangul inferior indică rădăcina cu rangul superior. Rangurile rădăcinilor nu se schimbă.
Dacă rândurile rădăcinilor sunt egale, oricare dintre rădăcini indică către cealaltă. Rangul rădăcinii indicată de o altă rădăcină este mărit cu 1.

Comprimarea traseului. Euristica din timpul operațiunii FIND_SET face ca fiecare nod (care este întâlnit în timpul deplasării la rădăcină) să indice direct către rădăcină. Comprimarea căilor nu modifică rangurile nodurilor.

Pseudocod

Luați în considerare un exemplu de implementare a unei păduri de mulțimi disjunctive. În tabloul p vom stoca o legătură către nodul părinte, iar în tabloul r rangul vârfului.

operațiune MAKE_SET(x) p[x] = x r[x] = 0 operația FIND_SET(x) dacă x ≠ p[x] atunci p[x] = FIND_SET(p[x]) returnează p[x] operația UNION(x, y) dacă r[x] > r[y] atunci p[y] = x altfel p[x] = y dacă r[x] = r[y] atunci r[y] = r[y] + 1

Orele de deschidere

Când sunt aplicate separat, unirea rangului și compresia traseului conduc la o creștere a eficienței operațiunilor pe o pădure de mulțimi disjunse. Unirea după rang oferă timpul de rulare , unde este numărul total de operații și este numărul de elemente din sistem. Comprimarea căii în sine are ca rezultat timpul de rulare în cel mai rău caz , unde este numărul de operațiuni FIND_SET. Aplicarea ambelor euristici dă timpul de rulare în cel mai rău caz , unde este funcția Ackermann inversă . Această estimare este o limită inferioară a timpului de funcționare cu mulțimi disjunse, astfel încât pădurea mulțimilor disjunse este structura optimă pentru mulțimile disjunse. $O(m~\lg{n})$ $m$ $n$ $O(n + f~\log_{2 + f/n}{n})$ $f$ $O(m\ \alpha(n, m))$ $\alpha(n, m)$

Link -uri

Vizualizator de structură de date

Literatură

Thomas Kormen et al.Algoritmi : construcție și analiză = INTRODUCERE ÎN ALGORITMI. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 0-07-013151-1 .