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)$

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

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.n = ∑ h i = 0 2 i = 2 h + 1 - 1 h n ≤ 2 h + 1 - 1 → h ≤ ⌈ log 2 ( n + 1 ) - 1 ⌉ ≤ ⌊ l o g 2 n ⌋ O ( log n ) n - 1 → O $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:n h e i g h t t r e e = 1 + max ( h e i g h t l e f t s u b t r e e , h e i g h t r i g h t s u $\{ 1,2,\dots,n\}$$n$i t h i - 1 n - i h n = 1 + max ( h i - 1 , h n - i ) E [ h n ] =

$$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ $i^{th}$$i-1$$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:$\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 × max ( Y i - 1 , Y n - $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

$$\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}$$\sum_i ci=c\sum_i i$$\operatorname{E}[ax]=a\operatorname{E}[x]$$\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$$Y$$\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$ $$\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$$Y_{i-1}=Y_{0}$$Y_{n-i}=Y_{n-1}$$i=n$$Y_{i-1}=Y_{n-1}$$Y_{n-i}=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}$$\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^{\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)$$