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

10

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

user1675999
quelle
1
Welche Frage? Welches Beispiel? Bitte bearbeiten und geben Sie alle Details.
Ran G.
3
Bitte vermeiden Sie die Verwendung von Abkürzungen (wie BST) und gehen Sie davon aus, dass die meisten von uns das CLRS-Buch nicht haben. Wenn Sie den Satz hier kopieren und erklären könnten, was Sie nicht verstehen, erhalten Sie weitere Antworten.
Ran G.
2
Dies hängt davon ab, wie der binäre Suchbaum erstellt wird. (Auch wenn das Ergebnis dies nicht tut, wird der Beweis dies tun.) Einige weitere Details wären nützlich.
Peter Shor

Antworten:

21

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:

Höhenausgeglichener binärer SuchbaumWorst-Case-Binärsuchbaum

pn=i=0h2i=2h+11hn2h+11hlog2(n+1)1log2nO(logn)n1O(n)

{1,2,,n}n

heighttree=1+max(heightleft subtree,heightright subtree)
ithi1Elemente 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:nihn=1+max(hi1,hni)E[hn]=1ni=1n[1+max(hi1,hni)]

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 .Yn=2hnYn=2×max(Yi1,Yni)

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

E[Yn]=i=1n1nE[2×max(Yi1,Yni)]=2ni=1nE[max(Yi1,Yni)]
1nici=ciiE[ax]=aE[x]maxFunktion 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 TermXYE[max(X,Y)]E[max(X,Y)+min(X,Y)]=E[X]+E[Y]
E[Yn]2ni=1n(E[Yi1]+E[Yni])=2ni=0n12E[Yi]
i=1Yi1=Y0Yni=Yn1i=nYi1=Yn1Yni=Y0Y0bis 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.Yn1E[Yn]4ni=0n1E[Yi]

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 .E[Yn]14(n+33)i=0n1(i+33)=(n+34)n3Yn=2hnhn=log2n3=3log2nO(logn)nkk

Um mit einem Einzeiler abzuschließen:

2E[Xn]E[Yn]4ni=0n1E[Yi]14(n+33)=(n+3)(n+2)(n+1)24E[hn]=O(logn)
Merbs
quelle
WOW, DANKE !!!! Auch wenn ich nichts über den erwarteten Wert weiß, macht diese Art von Sinn. Ich habe keinen diskreten Mathematikkurs gemacht, bevor ich Algorithmen gemacht habe. Ich werde weitere Kommentare veröffentlichen, wenn ich Zweifel habe. Danke Merbs.
user1675999
aber warum genau ist die exponentielle Höhe kleiner oder gleich dem gewählten Binomial? Ich verstehe immer noch nicht, warum wir kein anderes Binom mit einem anderen größten Begriff auswählen und genau die gleiche Mathematik durchführen können ... wahrscheinlich bin ich dumm, aber ich kann einfach nicht verstehen, warum ... und bis zu diesem Punkt Beweis macht vollkommen Sinn, dann mussten sie einfach etwas komplett aus heiterem Himmel herausziehen und ohne Erklärung sagen, dass es "beweist", dass sie Recht haben ...
Zeks
@Zeks Wir können also andere Binome mit größeren Begriffen auswählen. Wenn der Term immer noch polynomisch ist ( n^k), ist die Schlussfolgerung dieselbe, da die kin der Big-O-Notation gelöscht wird (wie 3 gelöscht wurde). Aber wenn wir etwas Exponentiales ( e^n) einsetzen würden, wäre es immer noch eine korrekte Obergrenze, nur keine enge . Wir wissen, dass die erwartete Höhe mindestens logarithmisch ist. Wenn wir also feststellen, dass sie höchstens logarithmisch ist, ist sie eng.
Merbs
@ DavidNathan Ich verstehe Ihr Anliegen nicht - bezweifeln Sie, dass 1 / n eine Konstante ist oder dass es außerhalb der Summation verschoben werden kann? Sie wird wie die Konstante 2 zur Veranschaulichung weitgehend herausgenommen, um den verbleibenden Beweis zu vereinfachen.
Merbs