Geometria drzew wyszukiwania binarnego

W informatyce jedno podejście do problemu optymalności dynamicznej w algorytmach online dla drzew wyszukiwania binarnego polega na przeformułowaniu problemu w sposób geometryczny, w zakresie powiększania zestawu punktów na płaszczyźnie o jak najmniejszą liczbę dodatkowych punktów, aby uniknąć prostokątów z tylko dwoma punkty na ich granicy.

Sekwencje dostępu i stosunek konkurencji

Zgodnie z typowym sformułowaniem problem drzewa wyszukiwania binarnego online obejmuje drzewa wyszukiwania zdefiniowane na podstawie ustalonego zestawu kluczy $..., n \}}$ . Sekwencja dostępu $_$ sekwencja ... gdzie $_$

Każdy konkretny algorytm utrzymywania drzew wyszukiwania binarnego (taki jak algorytm drzewa splay lub struktura zbioru roboczego Iacono ) ma koszt dla każdej sekwencji dostępu, która modeluje czas potrzebny na użycie struktury do wyszukania każdego z kluczy w kolejność dostępu po kolei. Koszt wyszukiwania jest modelowany przy założeniu, że algorytm drzewa wyszukiwania ma pojedynczy wskaźnik do drzewa wyszukiwania binarnego, który na początku każdego wyszukiwania wskazuje na korzeń drzewa. Algorytm może wówczas wykonać dowolną sekwencję następujących operacji:

Przesuń wskaźnik do jego lewego dziecka.
Przenieś wskaźnik do jego prawego dziecka.
Przenieś wskaźnik do jego rodzica.
Wykonaj pojedynczy obrót drzewa na wskaźniku i jego rodzicu.

Wyszukiwanie jest wymagane, aby w pewnym momencie tej sekwencji operacji przesunąć wskaźnik do węzła zawierającego klucz, a kosztem wyszukiwania jest liczba operacji wykonywanych w sekwencji. Całkowity koszt kosztu _A ( X ) dla algorytmu A w sekwencji dostępu X jest sumą kosztów wyszukiwania każdego kolejnego klucza w sekwencji.

Jak to jest standardem w analizie konkurencji , współczynnik konkurencyjności algorytmu A jest definiowany jako maksymalny, we wszystkich sekwencjach dostępu, stosunku kosztu A do najlepszego kosztu, jaki mógłby osiągnąć dowolny algorytm:

{\ Displaystyle \ rho _ {A} = \ sup _ {X} {\ Frac {\ operatorname {koszt} _ {A} (X)} {\ operatorname {koszt} _ {\ operatorname {opt}} (X) }}.}

Przypuszczenie dynamicznej optymalności stwierdza, że drzewa splay mają stały współczynnik konkurencyjności, ale pozostaje to nieudowodnione. Geometryczny widok drzew wyszukiwania binarnego zapewnia inny sposób zrozumienia problemu, który doprowadził do rozwoju alternatywnych algorytmów, które mogą również (przypuszczalnie) mieć stały współczynnik konkurencyjności.

Tłumaczenie na zbiór punktów geometrycznych

W geometrycznym ujęciu problemu drzewa wyszukiwania binarnego online sekwencja dostępu ${\ Displaystyle x_ {1}, ..., x_ {m}} (sekwencja wyszukiwań$ ${\ Displaystyle { 1,2, ..., n}}$ z zestawem kluczy ) jest odwzorowywane na zbiór punktów ${\ Displaystyle {(x_ {i}, i)}}$ , gdzie oś X reprezentuje kluczową przestrzeń i oś Y reprezentuje czas; do którego dodawany jest zestaw dotkniętych węzłów. Przez dotknięte węzły rozumiemy następujące. Rozważ algorytm dostępu BST z pojedynczym wskaźnikiem do węzła w drzewie. Na początku dostępu do danego klucza $jest$ inicjowany do korzenia drzewa. Ilekroć wskaźnik przesunie się do węzła lub zostanie do niego zainicjowany, mówimy, że węzeł został dotknięty. Reprezentujemy algorytm BST dla danej sekwencji wejściowej, rysując punkt dla każdego dotkniętego elementu.

Załóżmy na przykład następujący BST na 4 węzłach: Zestaw kluczy to {1, 2, 3, 4}.

Mapowanie tylko sekwencji dostępu 3, 1, 4, 2.

Geometryczny widok algorytmu drzewa wyszukiwania binarnego.

Niech 3, 1, 4, 2 będą sekwencją dostępu.

W pierwszym dostępie dotykany jest tylko węzeł 3.
W drugim dostępie dotykane są węzły 3 i 1.
W trzecim dostępie - 3 i 4 są dotykane.
W czwartym dostępie dotknij 3, następnie 1, a następnie 2.

Dotknięcia są reprezentowane geometrycznie: jeśli element x zostanie dotknięty w operacjach dla i -tego dostępu, wówczas wykreślany jest punkt ( x , i ).

Zbiory punktowe spełnione arboralnie

Prostokąt rozpięty na dwóch punktach. Ten zbiór punktów nie jest spełniony arboralnie.

To jest przykład zestawu punktów spełnionego arboralnie.

Mówimy, że zbiór punktów jest spełniony arboralnie , jeśli zachodzi następująca właściwość: dla dowolnej pary punktów, które nie leżą na tej samej poziomej lub pionowej linii, istnieje trzeci punkt, który leży w prostokącie rozpiętym przez pierwsze dwa punkty (albo wewnątrz lub na granicy).

Twierdzenie

$displaystyle x_ {1}, x_ {2}, ..., x_ {m}}$ punkty $jest arboralnie spełniony$ gdy odpowiada poprawnemu BST dla .

Dowód

Najpierw udowodnij, że punkt ustalony dla dowolnego ważnego algorytmu BST jest spełniony arboralnie. Rozważ punkty ${\ Displaystyle (x, i)}$ i ${\ Displaystyle (y, j)}$ , gdzie $x$ jest dotykany w czasie $i$ i $y$ jest dotykany w czasie $j$ . $i <j$ symetrię, że i $displaystyle$ . Należy wykazać, że istnieje trzeci punkt w prostokącie z rogami as i $}$ $\ Displaystyle$ y . $_$ również oznacza $aib$ $t$ _ _ _ _ $_$ _ Jest kilka przypadków:

${LCA} _ {i} (x, y) \ neq x}$ do , to użyj punktu ${\ Displaystyle (\ operatorname {LCA} _ {i} (x, y), i)}$ , ponieważ $\ Displaystyle \ operatorname {LCA} _ {i} (x, y )}$ musiało zostać dotknięte, jeśli $x$ było.
${\ Displaystyle \ operatorname {LCA} _ {j} (x, y) \ neq y}$ do to punkt ${\ displaystyle (\ operatorname {LCA} _ {j} (x, y), j)} .$ można użyć
Jeśli żaden z powyższych dwóch przypadków nie zachodzi, to $x$ musi być przodkiem $y$ tuż przed czasem $i$ , a $y$ musi być przodkiem $x$ tuż przed czasem $j$ . $y, k)$ w pewnym momencie $,$ $musiało$ obrócone powyżej $,$ ( ) $($ może być użyte.

Następnie pokaż drugi kierunek: mając zbiór punktów spełniony arboralnie, można skonstruować prawidłowy BST odpowiadający temu zbiorowi punktów. Zorganizuj nasz BST w skarbiec, który jest uporządkowany w kolejności sterty według czasu następnego dotknięcia. Zauważ, że czas następnego kontaktu ma powiązania i dlatego nie jest jednoznacznie zdefiniowany, ale nie stanowi to problemu, o ile istnieje sposób na zerwanie powiązań. $osiągnąłem$ czas , dotknięte węzły tworzą połączone poddrzewo na górze, według właściwości porządkowania sterty. Teraz przypisz nowe czasy następnego kontaktu dla tego poddrzewa i przestaw je w nowy lokalny skarb. Jeśli para węzłów, $x$ i $y$ , leży okrakiem na granicy między dotkniętą i nietkniętą częścią skarbu, to jeśli $y$ ma zostać dotknięte wcześniej niż $x ,$ to ${\ Displaystyle (x, teraz) \ do (y, następny dotyk (y))}$ jest niezadowolonym prostokątem, ponieważ najbardziej wysunięty na lewo taki punkt byłby prawym dzieckiem $x$ , a nie $y$ .

Następstwo

Znalezienie najlepszego wykonania BST dla sekwencji wejściowej $jest$ równoważne znalezieniu minimalnego nadzbioru liczności punktów (który zawiera dane wejściowe w reprezentacji geometrycznej), który jest Wiadomo, że bardziej ogólny problem znalezienia minimalnej liczności spełnionej arboralnie nadzbioru ogólnego zbioru punktów wejściowych (nie ograniczonego do jednego punktu wejściowego na współrzędną $y$ ) jest NP-zupełny .

Chciwy algorytm

Poniższy algorytm zachłanny konstruuje zbiory arboralnie zadowalające:

Przeciągnij punkt ustawiony poziomą linią, zwiększając współrzędną $y$ .
$umieść$ czasie $ja$ minimalną liczbę punktów w $ustawić$ punkt w sposób $w$ minimalny zestaw punktów jest jednoznacznie zdefiniowany: dla każdego niezadowolonego prostokąta utworzonego z rogu dodaj drugi róg w $ja}$ $y$ .

Przypuszcza się, że algorytm jest optymalny w okresie addytywnym.

Inne wyniki

Geometria binarnych drzew wyszukiwania została wykorzystana do zapewnienia algorytmu, który jest dynamicznie optymalny, jeśli jakikolwiek algorytm drzewa wyszukiwania binarnego jest dynamicznie optymalny.

Zobacz też