Struktura zestawu roboczego Iacono

Struktura danych zbioru roboczego Iacono
Wynaleziony	2001
Wynalezione przez	Johna Iacono
Złożoność asymptotyczna w notacji dużego O
Przestrzeń	O ( n )
Szukaj	O (log w(x) )
Wstawić	O (log n )
Usuwać	O (log n )

W informatyce struktura zestawu roboczego Iacono jest słownikiem opartym na porównaniach . Obsługuje operacje wstawiania, usuwania i uzyskiwania dostępu w celu utrzymania dynamicznego $zestawu$ . Zestaw roboczy elementu $to$$dostępu$ elementów, do których uzyskano dostęp w strukturze od czasu ostatniego lub wstawienia, jeśli nigdy nie uzyskano dostępu). Wstawianie i usuwanie w strukturze zestawu roboczego trwa ${\ Displaystyle O (\ log n)}$${\ Displaystyle O (\ log w (x))$ podczas uzyskiwania dostępu do elementu zajmuje $)$ . Tutaj $x$ zestawu roboczego $x}$ .

Struktura

$.$ wyszukiwania w strukturze zestawu roboczego Po znalezieniu $i$ usuwany z ${\ displaystyle T_ {4}}$ wstawiany do ${\ displaystyle T_ {1}}$ . ${i + 1}}$ koniec przeprowadzane jest przesunięcie od 1 do 4, w którym element jest usuwany z wstawiany do $T_$ dla ${\ Displaystyle 1 \ równoważnik i <4}$ .

Aby przechowywać dynamiczny zestaw $,$ ta struktura składa się z szeregu czerwono-czarnych drzew lub innych samobalansujących drzew wyszukiwania binarnego ${\ displaystyle T_ {1 }, T_ {2}, \ ldots, T_ {k}}$ i seria deques (kolejki dwustronne) ${\ displaystyle Q_ {1}, Q_ {2}, \ ldots Q_{k}}$ , gdzie ${\ Displaystyle k = \ lceil \ log \ log n \ rceil}$ . Dla każdego $Displaystyle T_ {i}}$$i \ równoważnik k}$ drzewo ${\$ i deque mają tę samą zawartość, a wskaźniki są utrzymywane między odpowiadającymi im elementami. Dla każdego rozmiaru ${\ displaystyle i <k}$${\ Displaystyle T_ {i}}$ i ${\ Displaystyle Q_ {i}}$ jest ${\ Displaystyle 2 ^ {2 ^ {i}}}$ . Drzewo ${\ Displaystyle T_ {k}}$$deque$ składają się z pozostałych elementów, tj. ich rozmiar wynosi $\ displaystyle n -\suma _{i=1}^{k-1}2^{2^{i}}}$ . Dlatego liczba elementów we wszystkich drzewach i liczba elementów we wszystkich dekach sumują się do ${\ displaystyle n}$ . Każdy element, który został wstawiony do struktury danych jest przechowywany dokładnie w jednym z drzew i odpowiadającej mu deque.

Zestaw roboczy Niezmienny

W elementach tej struktury elementy są uporządkowane według rozmiaru zestawu roboczego. Formalnie element leży po ${\ displaystyle y}$$w$ deque ${\ displaystyle Q_ {i}}$ wtedy i tylko wtedy, gdy $w(y)}$${\ Displaystyle w (x)$ . Co więcej, dla każdego elementy w deque ${\ Displaystyle 1 \ równoważnik i <k}$${\ displaystyle Q_ {i}}$ mają mniejsze zestawy robocze niż elementy w deque ${\ displaystyle Q_ {i + 1}}$ . Ta właściwość jest określana jako niezmiennik zestawu roboczego. Każda operacja w strukturze danych zachowuje niezmiennik zestawu roboczego.

Operacje

Podstawowa operacja w tej strukturze nazywa się przesunięciem $z$ do , $indeksami$ i $są$ drzew $.$ Przy przejściu od ${\ displaystyle h}$ do ${\ displaystyle j} rozważane są dwa przypadki$ : Jeśli ${\ displaystyle h <j}$ , to dla każdego ${\ displaystyle h \ leq i <j}$$i$ w porządku rosnącym, element jest usuwany z $+ 1}}$ \ . Odpowiedni element jest usuwany z ${\ displaystyle T_ {i}}$ i wstawiany do ${\ displaystyle T_ {i + 1}}$ . Czas wykonania tej operacji to ${\ Displaystyle O (\ suma _ {i = h} ^ {j} \ log | T_ {i} |) = O ( \sum _{i=h}^{j}\log 2^{2^{i}})=O(2^{j})}$ . Analogicznie, jeśli ${\ Displaystyle j <h}$ , to dla każdego ${\ Displaystyle j <i \ równoważnik h}$ , w kolejności malejącej, element jest usuwany z kolejki $Q_$ umieszczany w kolejce do ${i-1}}$ . Odpowiedni element jest usuwany z ${\ displaystyle T_ {i}}$ i wstawiany do ${\ displaystyle T_ {i-1}}$ . Czas wykonania tej operacji to ${\ Displaystyle O (\ suma _ {i = j} ^ {h} \ log | T_ {i} |) = O ( \sum _{i=j}^{h}\log 2^{2^{i}})=O(2^{h})}$ . Niezależnie od przypadku, po ${\ displaystyle T_ {j$ przesunięcia rozmiar zmniejsza się o jeden, podczas gdy rozmiar $}$ wzrasta o jeden. Ponieważ te elementy w deques są sortowane pod względem rozmiarów ich zestawów roboczych, operacja przesunięcia zachowuje niezmiennik zestawu roboczego.

Szukaj

Aby wyszukać element , wyszukaj $Displaystyle$$x}$ w $ldots T_ {k}}$ w kolejności rosnącej, aż do znalezienia drzewa zawierającego $T_ {j}}$$displaystyle$ . Jeśli nie zostanie znalezione żadne drzewo, wyszukiwanie zakończy się niepowodzeniem. Jeśli $znaleziony$ , zostanie usunięty z ${\ displaystyle T_ {j}},$ a następnie wstawiony do ${\ displaystyle T_ {1}}$ , czyli jest przenoszony na przód konstrukcji. Wyszukiwanie kończy się wykonaniem przesunięcia z do ${$$\ displaystyle j}$ , które przywraca rozmiar każdego drzewa i każdej deque do ich rozmiaru przed operacją wyszukiwania Czas trwania tego wyszukiwania to ${\ Displaystyle O (\ suma _ {i = 1} ^ {j} \ log 2 ^ {2 ^ {i}}) = O (2 ^ {j})}, jeśli wyszukiwanie zakończyło się sukcesem$ lub ${\ Displaystyle O (\ suma _ {i = j} ^ {k} \ log 2 ^ {2 ^ { i}})=O(2^{k})=O(\log n)}$ w przeciwnym razie. Dzięki właściwości zbioru roboczego każdy element w drzewach ${\ Displaystyle T_ {1}, T_ {2}, \ ldots, T_ {j-1}}$ należy do zestawu roboczego ${\ displaystyle x}$ . W szczególności każdy element w należy do zestawu roboczego $}$$}$ i stąd ${\ Displaystyle w (x)> | T_ {j-1} | = 2 ^ {2 ^ {j-1}}}$ . Zatem czas trwania pomyślnego wyszukiwania to ${\ Displaystyle O (2 ^ {j}) = O ( \log 2^{2^{j-1}})=O(\log w(x))}$ .

Wstawić

$Wstawienie$ elementu $poprzez$ struktury odbywa się $elementu$ struktury $.$ umieszczenie w Wstawianie jest zakończone przez wykonanie przesunięcia z ${\ displaystyle 1}$ do ${\ displaystyle k}$ . Aby uniknąć przepełnienia, jeśli ${\ Displaystyle | T_ {k} | = 2 ^ {2 ^ {k}}}$ przed przesunięciem, tj. jeśli ostatnie drzewo jest pełne, to $.$$zwiększane i$ tworzony jest ${\ displaystyle T_ {k}$ pusty i Czas trwania tej operacji jest zdominowany przez przejście z ${\ displaystyle 1}$ do ${\ displaystyle k}$ , którego czas wykonania to ${\ Displaystyle O (2 ^ {k}) = O (2 ^ {\ log \ log n}) = O (\ log n)}$ . Ponieważ element $, którego zestaw roboczy$$najmniejszy$ , jest umieszczany w , niezmiennik zestawu roboczego jest zachowywany po przesunięciu

Usuwać

$Usuwanie$ elementu odbywa się poprzez wyszukiwanie na $w$$drzewie$ rosnącym, aż do znalezienia drzewa, które zawiera (jeśli nie zostanie znaleziony, usunięcie nie powiodło się). Pozycja jest usuwana z $T$${\ Displaystyle T_ {j}}$ i $j}}$ . Wreszcie przejście z j ${\ displaystyle k}$ \ $Displaystyle j}$ utrzymuje rozmiar ${ \ Displaystyle 2 ^ {2$${j}}}$ . Czas trwania tej operacji to ${\ Displaystyle O (2 ^ {k}) = O (\ log n)}$ . Niezmiennik zestawu roboczego zostaje zachowany, ponieważ usunięcie elementu nie zmienia kolejności zestawu roboczego elementów.

Dyskusja

Drzewa splay to samodopasowujące się drzewa wyszukiwania wprowadzone $.$ , drzewa splay są w stanie wykonywać operacje wstawiania i usuwania w czasie bez przechowywanie wszelkich informacji o saldzie w węzłach. Co więcej, twierdzenie o zbiorach roboczych dla drzew splay stwierdza, że ​​koszt dostępu do elementu w drzewie splay wynosi ${\ Displaystyle O (\ log w (x))}$ amortyzowany . Struktura zestawu roboczego Iacono zapewnia taki sam czas działania wyszukiwania, wstawiania i usuwania w najgorszym przypadku. W związku z tym oferując alternatywę dla splay drzew.