Nehmen wir zuerst an, dass der Baum vollständig ist - er hat 2 ^ N Blattknoten. Wir versuchen zu beweisen, dass Sie N rekursive Schritte für eine binäre Suche benötigen.
Mit jedem Rekursionsschritt schneiden Sie die Anzahl der Kandidatenblattknoten genau um die Hälfte (weil unser Baum vollständig ist). Dies bedeutet, dass nach N Halbierungsoperationen genau ein Kandidatenknoten übrig ist.
Da jeder Rekursionsschritt in unserem binären Suchalgorithmus genau einem Höhenniveau entspricht, ist die Höhe genau N.
Verallgemeinerung auf alle ausgeglichenen Binärbäume: Wenn der Baum weniger Knoten als 2 ^ N hat, brauchen wir keine mehr Halvings. Wir brauchen vielleicht weniger oder die gleiche Menge, aber nie mehr.
Ich gebe hier keinen mathematischen Beweis. Versuchen Sie, das Problem zu verstehen, indem Sie log auf die Basis 2 anwenden. Log 2 ist die normale Bedeutung der Anmeldung in der Informatik.
Zuerst verstehe ich binären Logarithmus (log 2 ) (Logarithmus zur Basis 2). Zum Beispiel
Für jede Höhe ist die Anzahl der Knoten in einem vollständig ausgeglichenen Baum
%Vor%Betrachten Sie einen ausgeglichenen Baum mit zwischen 8 und 15 Knoten (jede Zahl, sagen wir 10). Es wird immer die Höhe 3 sein, da log 2 einer beliebigen Zahl von 8 bis 15 3 ist.
In einem ausgeglichenen Binärbaum wird die Größe des zu lösenden Problems bei jeder Iteration halbiert. Somit werden ungefähr log 2 n Iterationen benötigt, um ein Problem der Größe 1 zu erhalten.
Ich hoffe, das hilft.
Unter der Annahme, dass wir einen vollständigen Baum haben, mit dem wir arbeiten können, können wir sagen, dass es in der Tiefe k 2 k -Knoten gibt. Sie können dies mit einer einfachen Induktion beweisen, basierend auf der Intuition, dass das Hinzufügen eines zusätzlichen Levels zum Baum die Anzahl der Knoten im gesamten Baum um die Anzahl der Knoten erhöht, die im vorherigen Level zwei Mal waren.
Die Höhe k des Baumes ist log (N), wobei N die Anzahl der Knoten ist. Dies kann als
angegeben werdenlog 2 (N) = k,
und es entspricht
N = 2 k
Um das zu verstehen, hier ein Beispiel:
16 = 2 4 = & gt; log 2 (16) = 4
Die Höhe des Baumes und die Anzahl der Knoten sind exponentiell . Wenn Sie das Protokoll der Anzahl der Knoten verwenden, können Sie nur rückwärts arbeiten, um die Höhe zu finden.
Schaut einfach den strengen Beweis in Knuth, Band 3 - Such- und Sortieralgorithmen nach ... Er macht es viel strenger als jeder andere, den ich mir vorstellen kann.
Sie finden es in jeder guten Computer Science Bibliothek und in den Bücherregalen vieler (sehr) alter Geeks.
Tags und Links performance tree binary-search-tree