Dolna granica z przeplotem

W teorii optymalnych drzew wyszukiwania binarnego dolna granica przeplotu jest dolną granicą liczby operacji wymaganych przez drzewo wyszukiwania binarnego (BST) do wykonania danej sekwencji dostępów.

Udowodniono kilka wariantów tej dolnej granicy. Ten artykuł jest oparty na odmianie pierwszej granicy Wilbera. Ta dolna granica jest używana w projektowaniu i analizie drzewa Tango . Co więcej, tę dolną granicę można przeformułować i udowodnić geometrycznie, Geometria drzew wyszukiwania binarnego .

Definicja

Granica jest oparta na ustalonym $idealnym$ BST zwanym drzewem dolnej granicy, nad kluczami $..., n \}}$ . Na przykład dla ${\ displaystyle n = 7}$ , ${\ displaystyle P}$ można przedstawić za pomocą następującej struktury nawiasów:

[([1] 2 [3]) 4 ([5] 6 [7])]

Dla każdego węzła w określ: $displaystyle y$$}$

• ${\ Displaystyle Left (y)}$ być zbiorem węzłów w lewym poddrzewie ${\ Displaystyle y}$ , w tym ${\ Displaystyle y}$ .
• ${\ Displaystyle Right (y)}$ być zbiorem węzłów w prawym poddrzewie ${\ displaystyle y}$ .

Rozważ następującą sekwencję dostępu: ${\ Displaystyle X = x_ {1}, x_ {2}, ..., x_ {m}$ . Dla stałego węzła ${$ dla każdego dostępu zdefiniuj etykietę w odniesieniu do ${\ displaystyle x_ {i}$$}$ jako ${\ displaystyle x_$ :

• „ L ” ${\ Displaystyle Left (y$ jeśli jest w $y$ .
• „ R ” - jeśli jest w $y$${\ Displaystyle Right ($ y
• Null - inaczej.

Etykieta $jest$ połączeniem etykiet ze wszystkich dostępów Na przykład, jeśli sekwencja dostępów to: ${\ Displaystyle 7,6,3}$ to etykieta korzenia ${\ Displaystyle (4)}$ to: „RRL”, etykieta 6 to: „RL”, a etykieta 2 to: „L”.

Dla każdego węzła $jako$ ilość przeplotu przez y liczbę naprzemiennych między L i R na etykiecie ${\ displaystyle y}$ . $\ displaystyle 6}$ powyższym przykładzie przeplatanie przez wszystkie $inne$$węzły$ wynosi ${$ i przeplatanie przez wszystkie inne .

Granica przeplotu jest $.$ drzewa Granica przeplotu powyższej sekwencji to ${\ displaystyle 2}$ .

Stwierdzenie dolnej granicy i jego dowód

Wiązanie z przeplotem podsumowuje następujące twierdzenie.

Twierdzenie — Niech będzie sekwencją $dostępu$ Oznacz przez ${\ Displaystyle IB (X)}$ granicę przeplotu ${\ displaystyle X}$ , a następnie ${\ Displaystyle {\ mathit {IB}} (X) / 2-n}$ jest dolną granicą ${\ Displaystyle OPT (X)}$ , koszt optymalnego BST offline, który obsługuje ${\ displaystyle X}$ .

Poniższy dowód opiera się na.

Dowód

Niech ${\ Displaystyle X = x_ {1}, x_ {2}, ..., x_ {m}}$ być sekwencją dostępu Oznacz przez stan dowolnego BST w czasie $,$${\ Displaystyle x_ {1}, x_ {2}, ..., x_ {i}$$po$ sekwencji . Naprawiamy również dolną granicę BST . ${\ displaystyle P}$ .

Dla węzła $aby$$,$ zdefiniuj punkt przejścia w czasie, $z$$węzłem$ o minimalnej głębokości $}$ BST $tak$$\ displaystyle z}$ że ścieżka od korzenia do ${$ węzeł z ( y ) i węzeł z prawej ( y ). Intuicyjnie, każdy algorytm BST na $)$ który uzyskuje dostęp do elementu z prawej ( y , a następnie elementu z lewej ( y ) (lub odwrotnie), musi dotykać punktu przejścia T ja ${\ displaystyle$ przynajmniej raz. W poniższym Lemacie pokażemy, że punkt przejścia jest dobrze zdefiniowany.

Lemat 1 $-$ Punkt przejścia $węzła$$.$ czasie i unikalny

Dowód

Zdefiniuj jako najniższego wspólnego przodka wszystkich węzłów w lewym ( y ) $\ displaystyle T_ {i}$${$ . Biorąc pod uwagę $Displaystyle$ dwa węzły , najniższy wspólny przodek i za $a}$ i ${\ Displaystyle b}$$,$ oznaczony przez ${\ Displaystyle lca (a, b)}$ , spełnia następujące nierówności. ${\ Displaystyle a \ równoważnik lca (a, b) \ równoważnik b}$ . W konsekwencji $i$ w Left (y) jest unikalnym węzłem o minimalnej głębokości w $displaystyle$$T_ {i}}$ . To samo rozumowanie można zastosować do ${\ displaystyle r}$ , najniższy wspólny przodek wszystkich węzłów w prawym (y) ${\ displaystyle T_ {i}}$ . Ponadto najniższy wspólny przodek dla wszystkich punktów w Left(y) i right(y) również znajduje się w jednym z tych zestawów. Dlatego unikalny węzeł minimalnej głębokości musi znajdować się wśród węzłów Left(y) i right(y) . Dokładniej, jest to albo ${\ displaystyle \ ell}$ lub ${\ displaystyle r}$ . Załóżmy, że jest to ${\ Displaystyle \ ell}$ . Następnie ${\ displaystyle \ ell}$ jest przodkiem ${\ displaystyle r}$ . $\ displaystyle$ konsekwencji jest $to$ punkt przejścia, ponieważ ścieżka od korzenia do zawiera $r}$ . Co więcej, $\ displaystyle T_ {i} }$ ścieżka w ${$ do węzła w poddrzewie musi odwiedzić T ${\ displaystyle \ ell}$ ponieważ jest przodkiem wszystkich takich węzłów, a dla każdej ścieżki do węzła w prawym regionie należy odwiedzić, $jest$ to najniższy wspólny przodek wszystkich węzłów w prawym (y) . Podsumowując, jest to unikalny punkt przejścia dla $displaystyle$$y}$ w $}$ .

Drugi lemat, który musimy udowodnić, mówi, że punkt przejścia jest stabilny. Nie zmieni się, dopóki nie zostanie dotknięty.

Lemat 2 - Biorąc pod uwagę węzeł ${\ displaystyle y}$ . Załóżmy $jest$ punktem przejścia w $y}$ momencie $displaystyle$ . Jeśli algorytm dostępu dla BST nie dotyka $\$$Displaystyle T_ {i}}$ { dla $}$ in [j, k punkt przejścia $pozostanie$${\ Displaystyle y}$ w T $\ Displaystyle T_ {i}}$ dla ${\ Displaystyle i \ w [j, k]}$ .

Dowód

Rozważ tę samą definicję dla i ${\ displaystyle$$r}$ jak w lemacie 1. Bez utraty ogólności załóżmy również, że jest przodkiem ${\ displaystyle \ ell}$ w $}$ BST w czasie , oznaczony przez $T_ {j}}$$displaystyle$ . W rezultacie ${\ displaystyle r}$ będzie punktem przejścia ${\ displaystyle y}$ . $Zgodnie$$z$ BST nie dotyka punktu przejścia, w naszym , czas W związku z tym nie dotyka żadnego węzła w Right(y) . W konsekwencji pozostaje najniższym wspólnym przodkiem dla dowolnych dwóch węzłów w $Right$ y) . Jednak algorytm dostępu może dotykać węzła w Left(y) . Dokładniej, może dotykać najniższego wspólnego przodka wszystkich węzłów w Left(y) $Displaystyle$ czasie , co będziemy oznaczać przez $\ ell _ {i}}$ . Mimo to pozostanie przodkiem $z$$displaystyle r}$ następujących powodów: Po pierwsze, zauważ, że każdy węzeł Left (y) znajdujący się poza drzewem ma korzenie w ${\ displaystyle r}$ w czasie jot $\ displaystyle j}$ nie może wejść do tego drzewa na raz $]}$$k$ , ponieważ nie jest dotykany w tym przedziale czasowym. Po drugie, istnieje co najmniej jeden węzeł $jot$${ \ Displaystyle i \ w [j, k]}$$poza$ ) drzewem w dowolnym momencie . Dzieje się tak, ponieważ początkowo znajdował się poza ${\ displaystyle \ ell}$${\ displaystyle r}$ 's i żadne węzły spoza drzewa nie mogą wejść do niego w tym przedziale czasowym. Teraz rozważmy $\ Displaystyle a_ {i} = lca (\ ell _ {i} ', r)}$ . ${\ Displaystyle a_ {i}}$ nie może być ${\ displaystyle r},$$ponieważ$ nie znajduje się w poddrzewie $}$ . Więc ${\ Displaystyle a_ {i}}$ musi być w $_ {i} '\ równoważnik a_ {i} \ równoważnik r}$ (y) , ponieważ . W konsekwencji $w$$być$ przodkiem konsekwencji przodkiem $}$$r$ czasie . Dlatego zawsze istnieje węzeł w $lewo$ (y) na ścieżce od korzenia do $jako$ taki pozostaje punktem przejścia.

$ma$ dowodu stwierdza, że ​​każdy węzeł punkt przejścia.

Lemat 3 - Biorąc $}}$ uwagę BST w czasie $ja {\$ każdy węzeł $displaystyle T_$ czasie $może$ być tylko przejściem dla co najwyżej jednego $węzła$ .

Dowód

Biorąc pod uwagę dwa różne węzły ${\ Displaystyle y_ {1}, y_ {2} \ w P}$ . Niech ${\ Displaystyle r_ {1}, \ ell _ {1}, r_ {2}, \ ell _ {2}}$ będzie najniższym wspólnym przodkiem ${\ Displaystyle Prawo (y_ {1}), lewo (y_ {1}), prawo (y_ {2}), lewo (y_ {2} )}$ odpowiednio. Z lematu 1 wiemy, że punkt przejścia dla $y_$$}$ \ ${ i$ jest dla ${\ Displaystyle i \ w \ {1,2 \}}$ . Teraz mamy dwa główne przypadki do rozważenia.

$w$ { \ displaystyle $}$ P. $\ displaystyle P}$ . W ${\ Displaystyle Lewy (y_ {1}), Lewy (y_ {2}), Prawy (y_ {1})}$ i ${\ Displaystyle Prawy (y_ {2})}$ są wszystkie rozłączne. Zatem ${\ Displaystyle r_ {1} \ neq r_ {2} \ neq \ ell _ {1} \ neq \ ell _ {2}}$ , a punkty przejścia są różne .

$displaystyle y_ {2}}$ : Załóżmy bez utraty ogólności, że jest przodkiem $\$ w $displaystyle P}$ .

$2 {$ 2.1: Załóżmy, że punkt przejścia nie znajduje się w drzewie zakorzenionym w ${\ displaystyle y_ {2}}$ w $displaystyle P}$ . Zatem ${2}}$ się od $konsekwencji$ aw od punktu przejścia $y_$ .

Przypadek 2.2: Punkt przejścia znajduje się w drzewie zakorzenionym w $y_ {2}}$$displaystyle$ w $displaystyle P}$ . Dokładniej, jest to jeden z najniższych wspólnych przodków ${\ Displaystyle Left (y_ {2})}$ i ${\ Displaystyle right (y_ {2} )}$ . Innymi słowy, jest to albo ${\ displaystyle \ ell _ {2}}$ lub ${\ displaystyle r_ {2}}$ .

Załóżmy , ${\$ jest najniższym wspólnym przodkiem poddrzewa zakorzenionego w $displaystyle y_ {1}}$ i nie zawiera $displaystyle y_ {2}}$ . Mamy i ${\ displaystyle \ ell _ {2}$$}$ głębiej niż $a_ {1}}, ponieważ jeden$ nich jest punktem przejścia. Załóżmy, że ${\ Displaystyle \ ell _ {2}}$ jest punktem przejścia. Wtedy $r_ {2}$ mniej głęboka niż $displaystyle$ . W tym przypadku ${\ Displaystyle \ ell _ {2}}$ jest punktem przejścia ${\ Displaystyle y_ {1}}$ i ${\ Displaystyle r_ {2}}$ jest punktem przejścia ${ \displaystyle y_{2}}$ . Podobne rozumowanie ma zastosowanie, $mniej$ głębokie ${\ Displaystyle \ ell _ {2}}$ . Podsumowując, punkt przejścia jest mniej głęboki od $r_$${2}}$$} \displaystyle y_{2}}$ \ displaystyle i $displaystyle r_$ ma głębszy jako punkt przejścia.

Podsumowując, punkty przejścia są różne we wszystkich przypadkach.

Teraz jesteśmy gotowi do udowodnienia twierdzenia. Przede wszystkim zauważ, że liczba dotkniętych punktów przejścia przez algorytm BST offline jest dolną granicą jego kosztu, liczymy mniej węzłów niż jest to wymagane dla całkowitego kosztu.

Wiemy z lematu 3, że w dowolnym momencie dowolny węzeł $\$ może być tylko przejściem dla co najwyżej jednego węzła w $i}}$${$$displaystyle$ . Zatem wystarczy policzyć liczbę dotknięć węzła przejściowego $}$ sumę wszystkich ${\ displaystyle y$ .

Dlatego dla stałego węzła ${\ Displaystyle y \ in P.}$ , $zostaną$ i ${\ displaystyle r}$ zdefiniowane jak w Lemacie 1. Punkt przejścia ${\ displaystyle y }$ jest jednym z tych dwóch węzłów. W rzeczywistości jest głębszy. Niech ${\ Displaystyle x_ {i_ {1}}, x_ {i_ {2}}, ..., x_ {i_ {p}}$ będzie maksymalnie uporządkowaną sekwencją dostępu do węzłów, które występują naprzemiennie między ${\ Displaystyle Left (y)}$ i ${\ Displaystyle Right (y)}$ . Wtedy ${\ displaystyle p}$ to ilość przeplotu w węźle ${\ displaystyle y}$ . Załóżmy, że parzyste dostępy indeksowane są w ${\ Displaystyle Left (y)}$ , a te nieparzyste są w ${\ Displaystyle Right (y)}$ tj. ${\ Displaystyle x_ {i_ {2j}} \ w lewo (y)}$ i ${\ Displaystyle x_ {i_ {2j-1}} \ w prawo (y)}$ . Z właściwości najniższego wspólnego przodka wiemy ${$ że dostęp do węzła w musi dotykać . $\ displaystyle Left (y)}$ . $\ Displaystyle$ dostęp do węzła musi dotykać $Right (y)}$ . Rozważmy każde ${\ Displaystyle j \ w [1, \ lfloor p / 2 \ rfloor]}$ . $dwóch$$i$ dostępów , _ $_ \ Displaystyle y}$ , a następnie ${\ Displaystyle \ ell}$ i ${\ Displaystyle R}$ musi się zmienić w międzyczasie. Jednak zgodnie z Lematem 2 taka zmiana wymaga dotknięcia punktu przejścia. ${\ Displaystyle [i_ {2j-1}, i_ {2j$ punktu przejścia co najmniej raz w przedziale $]$ . Podsumowując wszystkie ${\ Displaystyle j \ w [1, \ lfloor p / 2 \ rfloor]}$$najmniej$ najlepszy algorytm . $}$ Displaystyle Podsumowując, y $\ displaystyle y}$

      ${\ Displaystyle \ suma _ {y \ w P} p_ {y} / 2-1 \ geq IB (X) / 2-n }$

gdzie $}$ ilością przeplotu przez $\ displaystyle y$ . ${\ displaystyle IB (X)$ definicji suma $X$ się do } To kończy dowód.

Zobacz też

• Drzewo tanga
• Optymalne drzewo wyszukiwania binarnego
• Geometria drzew wyszukiwania binarnego