Dowód, że losowo zbudowane drzewo wyszukiwania binarnego ma wysokość logarytmiczną

Jak udowodnić, że oczekiwana wysokość losowo zbudowanego drzewa wyszukiwania binarnego z węzłami wynosi ? Istnieje dowód we CLRS Wstęp do algorytmów (rozdział 12.4), ale ja go nie rozumiem. $n$ $O(\log n)$

— użytkownik1675999
źródło

Które pytanie? Jaki przykład Edytuj i podaj pełne dane.

— Ran G.

Unikaj używania skrótów (takich jak BST) i zakładaj, że większość z nas nie ma książki CLRS. Jeśli możesz skopiować to twierdzenie tutaj i wyjaśnić, czego nie rozumiesz, otrzymasz więcej odpowiedzi.

— Ran G.

To będzie zależeć od sposobu wyszukiwania binarne drzewo jest zbudowany. (Nawet jeśli wynik nie, dowód będzie). Przydałoby się więcej szczegółów.

— Peter Shor

Pomyślmy o tym intuicyjnie. W najlepszym przypadku drzewo jest idealnie zrównoważone; w najgorszym przypadku drzewo jest całkowicie niezrównoważone:

Binarne drzewo wyszukiwania o zrównoważonej wysokości Drzewo wyszukiwania binarnego najgorszego przypadku

Zaczynając od węzła głównego , to lewe drzewo ma dwukrotnie więcej węzłów na każdej kolejnej głębokości, tak że drzewo ma węzły i wysokość (czyli w tym przypadku 3). Przy odrobinie matematyki , co oznacza, że ma wysokość. W przypadku drzewa całkowicie niezrównoważonego wysokość drzewa wynosi po prostu . Mamy więc swoje granice. $p$ $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ $h$ $n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$ $O(\log n)$ $n-1\rightarrow O(n)$

Gdybyśmy budowali drzewo zrównoważone z uporządkowanej listy , wybralibyśmy środkowy element, który będzie naszym węzłem głównym. Jeśli zamiast tego losowo konstruujemy drzewo, każdy z węzłów zostanie równie prawdopodobnie wybrany, a wysokość naszego drzewa wynosi: Wiemy, że w drzewie wyszukiwania binarnego lewe poddrzewo musi zawierać tylko klucze mniejsze niż węzeł główny. Tak więc, jeśli losowo wybieramy element , lewe poddrzewo ma elementy , a prawe poddrzewa ma elementy , więc bardziej kompaktowo: $\{ 1,2,\dots,n\}$ $n$

h mi ja sol h t_{t r mi mi} = 1 + max (h mi ja sol h t_{l mi fa t s u b t r mi mi}, h mi ja sol h t_{r ja sol h t s u b t r mi mi})

$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$

i^{t h}

$i^{th}$

i - 1

$i-1$

n - i

$n-i$

h_{n} = 1 + max (h_{i - 1}, h_{n - i})

$h_n=1+\max (h_{i-1},h_{n-i})$ . Stąd sensowne jest, że jeśli każdy element jest równie prawdopodobne, że zostanie wybrany z równą prawdopodobieństwem, oczekiwana wartość jest tylko średnią wszystkich przypadków (a nie średnią ważoną). Stąd:

E [h_{n}] = \frac{1}{n} \sum_{i = 1}^{n} [1 + max (h_{i - 1}, h_{n - i})]

$\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

Jak zapewne zauważyłeś, nieznacznie odstąpiłem od tego, jak CLRS to udowadnia, ponieważ CLRS używa dwóch stosunkowo powszechnych technik dowodowych, które są niepokojące dla niewtajemniczonych. Pierwszym z nich jest użycie wykładników (lub logarytmów) tego, co chcemy znaleźć (w tym przypadku wysokości), co sprawia, że matematyka jest nieco bardziej przejrzysta; drugim jest użycie funkcji wskaźnika (które zamierzam tutaj zignorować). CLRS definiuje wysokość wykładniczą jako , więc analogiczna rekurencja to . $Y_n=2^{h_n}$ $Y_n=2\times\max (Y_{i-1},Y_{n-i})$

Zakładając niezależność (że każde losowanie elementu (spośród dostępnych elementów) jako podstawy poddrzewa jest niezależne od wszystkich poprzednich losowań), nadal mamy relację: dla którego zrobiłem dwa kroki: (1) przesunięcie zewnątrz, ponieważ jest stała, a jedną z właściwości sumowania jest to, że , oraz (2) przeniesienie 2 na zewnątrz, ponieważ jest to również stała, a jedną z właściwości oczekiwanych wartości jest . Teraz zastąpimy

mi [Y_{n}] = \sum_{ja = 1}^{n} \frac{1}{n} mi [2) \times max (Y_{ja - 1}, Y_{n - ja})] = \frac{2)}{n} \sum_{ja = 1}^{n} mi [max (Y_{ja - 1}, Y_{n - ja})]

$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$

\frac{1}{n}

$\frac{1}{n}$

\sum_{i} c i = c \sum_{i} i

$\sum_i ci=c\sum_i i$

E [a x] = a E [x]

$\operatorname{E}[ax]=a\operatorname{E}[x]$

max

$\max$ działają z czymś większym, ponieważ w przeciwnym razie uproszczenie jest trudne. Jeśli argumentujemy za nieujemnym , : , a następnie: tak, że ostatni krok wynika z obserwacji, że dla , i i przejście wszystkich droga do , i , więc każdy termin

X

$X$

Y

$Y$

E [max (X, Y)] \leq E [max (X, Y) + min (X, Y)] = E [X] + E [Y]

$\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$

mi [Y_{n}] \leq \frac{2)}{n} \sum_{ja = 1}^{n} (mi [Y_{ja - 1}] + mi [Y_{n - ja}]) = \frac{2)}{n} \sum_{ja = 0}^{n - 1} 2) mi [Y_{ja}]

$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$

i = 1

$i=1$

Y_{i - 1} = Y_{0}

$Y_{i-1}=Y_{0}$

Y_{n - i} = Y_{n - 1}

$Y_{n-i}=Y_{n-1}$

i = n

$i=n$

Y_{i - 1} = Y_{n - 1}

$Y_{i-1}=Y_{n-1}$

Y_{n - i} = Y_{0}

$Y_{n-i}=Y_{0}$

Y_{0}

$Y_0$ do pojawia się dwa razy, więc możemy zastąpić całe podsumowanie analogicznym. Dobra wiadomość jest taka, że mamy wznowienie nazwa ; zła wiadomość jest taka, że nie jesteśmy daleko od miejsca, w którym zaczęliśmy.

Y_{n - 1}

$Y_{n-1}$

E [Y_{n}] \leq \frac{4}{n} \sum_{i = 0}^{n - 1} E [Y_{i}]

$\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$

W tym momencie CLRS wyciąga dowód indukcyjny nazwa z ich ... repertuaru doświadczeń matematycznych, takiego, który zawiera tożsamość które użytkownik musi udowodnić. Ważne w ich wyborze jest to, że jego największym terminem jest i przypominamy, że używamy wysokości wykładniczej tak że . Być może ktoś skomentuje, dlaczego wybrano ten konkretny dwumian. Jednak ogólną ideą jest ograniczenie z góry naszego ponownego wystąpienia wyrażeniem dla pewnego stałego . $\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$ $\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$ $n^3$ $Y_n=2^{h_n}$ $h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$ $n^k$ $k$

Na zakończenie z jedną linią:

2^{E [X_{n}]} \leq E [Y_{n}] \leq \frac{4}{n} \sum_{i = 0}^{n - 1} E [Y_{i}] \leq \frac{1}{4} (\binom{n + 3}{3}) = \frac{(n + 3) (n + 2) (n + 1)}{24} \to E [h_{n}] = O (\log n)

$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n)$

— Merbs
źródło

WOW. DZIĘKI !!!! Chociaż nie wiem o oczekiwanej wartości, ten rodzaj ma sens. Nie zrobiłem dyskretnego kursu matematyki przed zrobieniem algorytmów. W razie wątpliwości opublikuję więcej komentarzy. Dziękuję Merbs.

— user1675999,

ale dlaczego dokładnie wysokość wykładnicza jest mniejsza lub równa wybranemu dwumianowi? Nadal nie rozumiem, dlaczego nie możemy wybrać żadnego dwumianu z innym największym terminem i wykonać dokładnie taką samą matematykę ... prawdopodobnie jestem głupi, ale po prostu nie rozumiem, dlaczego ... i do tej pory dowód ma sens, wtedy musieli po prostu wyciągnąć coś całkowicie z

— zaskoczenia

@Zeks Możemy więc wybrać inne dwumianowe o większych terminach. Jeśli termin jest wciąż wielomianowy ( n^k), wniosek jest taki sam, ponieważ kjest on odrzucany w notacji big-O (sposób 3 został usunięty). Ale jeśli podstawimy coś wykładniczego ( e^n), nadal będzie to prawidłowa górna granica, po prostu nie ścisła . Wiemy, że oczekiwana wysokość jest co najmniej logarytmiczna, więc ustalenie, że jest co najwyżej logarytmiczne, czyni ją ciasną.

— Merbs

@DavidNathan Nie rozumiem twojej obawy - czy wątpisz, że 1 / n jest stałą, czy można ją przenieść poza podsumowanie? Podobnie jak stała 2, jest w dużej mierze pobierany w celach ilustracyjnych, aby uprościć pozostały dowód.

— Merbs