Beweis, dass ein zufällig erstellter binärer Suchbaum eine logarithmische Höhe hat

Wie beweisen Sie, dass die erwartete Höhe eines zufällig erstellten binären Suchbaums mit $n$ Knoten $O(\log n)$ ? Es gibt einen Beweis in der CLRS- Einführung in Algorithmen (Kapitel 12.4), aber ich verstehe ihn nicht.

Lassen Sie uns zunächst intuitiv darüber nachdenken. Im besten Fall ist der Baum perfekt ausbalanciert. Im schlimmsten Fall ist der Baum völlig unausgeglichen:

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

$\{ 1,2,\dots,n\}$$n$

$$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ $i^{th}$$i-1$Elemente und der rechte Teilbaum hat Elemente, also kompakter: . Von dort aus ist es sinnvoll, dass der erwartete Wert nur der Durchschnitt aller Fälle ist (und nicht ein gewichteter Durchschnitt), wenn jedes Element gleich wahrscheinlich ausgewählt wird. Daher:$n-i$$h_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})]$

Wie Sie sicher bemerkt haben, bin ich leicht davon abgewichen, wie CLRS dies beweist, da CLRS zwei relativ häufige Beweisverfahren verwendet, die für Uneingeweihte beunruhigend sind. Die erste besteht darin, Exponenten (oder Logarithmen) dessen zu verwenden, was wir finden möchten (in diesem Fall Höhe), wodurch die Mathematik etwas sauberer funktioniert. Die zweite besteht darin, Anzeigefunktionen zu verwenden (die ich hier nur ignorieren werde). CLRS definiert die exponentielle Höhe als , daher ist die analoge Wiederholung .$Y_n=2^{h_n}$$Y_n=2\times\max (Y_{i-1},Y_{n-i})$

Unter der Annahme, dass die Unabhängigkeit (dass jede Zeichnung eines Elements (aus den verfügbaren Elementen) die Wurzel eines Teilbaums ist, unabhängig von allen vorherigen Ziehungen) weiterhin die Beziehung hat: für die ich zwei Schritte ausgeführt habe: (1) Verschieben des außerhalb, weil es eine Konstante ist und eine der Eigenschaften von Summationen ist, dass , und (2) die 2 nach außen verschieben, weil es auch eine Konstante ist und eine der Eigenschaften der erwarteten Werte . Jetzt werden wir das ersetzen

$$\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$Funktion mit etwas Größerem, weil sonst die Vereinfachung schwierig ist. Wenn wir für nichtnegatives , argumentieren : , dann: , so dass der letzte Schritt von der Beobachtung folgt , daß für , und und gehen den ganzen Weg zu , und , also jeder Term$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$bis erscheint zweimal, so dass wir die gesamte Summe durch eine analoge ersetzen können. Die gute Nachricht ist, dass wir eine Wiederholung ; Die schlechte Nachricht ist, dass wir nicht viel weiter sind als dort, wo wir angefangen haben.$Y_{n-1}$$\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$

Zu diesem Zeitpunkt zieht CLRS einen Induktionsbeweis aus seinem ... Repertoire mathematischer Erfahrung heraus enthält eine Identität sie dem Benutzer zum Nachweis überlassen. Was bei ihrer Wahl wichtig ist, ist, dass sein größter Term , und erinnern Sie sich, dass wir die exponentielle Höhe so dass . Vielleicht wird jemand kommentieren, warum dieses spezielle Binom gewählt wurde. Die allgemeine Idee ist jedoch, unsere Wiederholung von oben mit einem Ausdruck für eine Konstante zu binden .$\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$

Um mit einem Einzeiler abzuschließen:

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