Les disjunktních množin

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. listopadu 2019; ověření vyžaduje 1 úpravu .

Les nesouvislých množin je stromová datová struktura pro disjunktní množiny . (někdy nazývaný Disjoint Set System )

Nastavit reprezentace

Každá sada je reprezentována jako kořenový strom . V doménové struktuře nesouvislé sady obsahuje každý uzel jeden prvek sady a ukazuje pouze na svůj nadřazený uzel. Kořen každého stromu obsahuje zástupce a je jeho rodičem.

Operace s doménovou strukturou nesouvislých množin se provádějí následovně:

MAKE_SET - vytvoří strom s jedním uzlem.

FIND_SET - přesouváme se po rodičovských vazbách do kořene stromu.

UNION - nastaví ukazatel kořene jednoho stromu na kořen druhého.

Heuristika pro efektivitu

Sdružení podle hodnosti. Myšlenka heuristiky spočívá v tom, že při provádění operace UNION se výška výsledného stromu, pokud je to možné, nezvyšuje. K tomu se používá charakteristická hodnost pro každý kořen, což je horní hranice výšky uzlu. Operace MAKE_SET vytvoří kořen s hodností 0. Operace UNION, která se v tomto případě nazývá sjednocení podle hodnosti, funguje následovně:

Pokud jsou úrovně kořenů různé, kořen s nižší úrovní ukazuje na kořen s vyšší úrovní. Kořenové pozice se nemění.
Pokud jsou řady kořenů stejné, jeden z kořenů ukazuje na druhý. Hodnost kořene, na který ukazuje jiný kořen, se zvýší o 1.

Komprese cesty. Heuristika během operace FIND_SET způsobí, že každý uzel (na který narazí při přesunu do kořenového adresáře) ukazuje přímo na kořenový adresář. Komprese cesty nemění pořadí uzlů.

Pseudokód

Zvažte příklad implementace lesa nesouvislých množin. Do pole p uložíme odkaz na nadřazený uzel a do pole r hodnost vrcholu.

operace MAKE_SET(x) p[x] = x r[x] = 0 operace FIND_SET(x) jestliže x ≠ p[x] pak p[x] = FIND_SET(p[x]) vrátit p[x] operace UNION(x, y) jestliže r[x] > r[y] pak p[y] = x jiný p[x] = y jestliže r[x] = r[y] pak r[y] = r[y] + 1

Otevírací doba

Při samostatné aplikaci vede sjednocení pořadí a komprese cesty ke zvýšení efektivity operací na doménové struktuře nesouvislých množin. Samotné sjednocení podle hodnosti udává dobu běhu , kde je celkový počet operací a počet prvků v systému. Samotná komprese cesty má za následek nejhorší případ běhu , kde je počet operací FIND_SET. Použití obou heuristik dává nejhorší případ běhu , kde je inverzní Ackermannova funkce . Tento odhad je spodní hranicí doby operace s disjunktními množinami, takže les disjunktních množin je optimální strukturou pro disjunktní množiny. $O(m~\lg{n})$ $m$ $n$ $O(n + f~\log_{2 + f/n}{n})$ $F$ $O(m\ \alpha(n, m))$ $\alpha(n, m)$

Odkazy

Vizualizér datové struktury

Literatura

Thomas Kormen aj. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .