Beweis für die Tiefe der ausgewogenen Suchbaum

Question

Wenn T ein ausgewogen BST mit n Elementen, L dem linken Teilbaum und r seine rechten, wie kann ich beweisen, dass ihre Tiefe weniger als oder gleich 2log (n) + 1?

Es ist ein Beweis durch Induktion, die ich habe, aber ich verstehe es nicht.

(Ich verstehe, dass Stackoverflow in erster Linie orientiert ist, Programmierung, aber ich fand einige Fragen über binäre Suchbäume und beschlossen, es zu versuchen, ich hoffe, nicht etwas, das nicht gut tue.))

Answer 1

Durch die Definition von „balanced“, Tiefen von jeweils linken und rechten Teilbäume von dem gleichen Knoten unterscheiden sich höchstens um eins. „Tiefe“ wird normalerweise als „Anzahl des Schrittes des längsten Weges von Baumwurzel bis zu leaf“ definiert ist, so beispielsweise ein BST mit einer Wurzel und zwei Blättern (drei Elemente in dem einzigen Weg, können sie in einem ausgewogenen BST angeordnet sein) ist gesagt haben, in die Tiefe ein (sieht aus wie Sie eine etwas andere Definition verwenden, die es Tiefe zwei? geben würde), so würde man mit einer Wurzel und einem Blatt (ob das Blatt ist die Wurzel linken oder rechten Unterbaum ist keinen Unterschied macht), während man mit nur einer Wurzel, die auch ein Blatt ist (ein einzelnes Element) Tiefe 0 aufweisen würde (Es gibt keine BST mit Null-Elementen).

Also für n <= 3 Elemente, rufen D (n) die Baumtiefe, wie oben definiert, klar D(n) < log(n) + 1 (mit log Bedeutung Basis-2-Logarithmus) durch Inspektion, da 1 = D(2) < log(2) + 1 = 2 (und 1 = D(3) auch für die die RHS der Ungleichheit, log(3) + 1, ist in der Tat > 2) und 0 = D(1) < log(1) + 1 = 1 - dies gibt uns die Induktionsbasis

.

den Beweis durch Induktion vervollständigen wir zeigen müssen, dass, wenn D(k) < log(k) + 1 für alle k < n, dann auch folgt, dass D(n) < log(n) + 1.

Wenn n ungerade ist, eindeutig linken und rechten Teilbaum haben jeweils Elemente (n-1)/2, und der Baum hat Tiefe 1 mehr als die Teilbäume; aber dann D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (durch die Induktionshypothese) = 1 + log(n-1) (da log((n-1)/2) = log(n-1) - 1) und damit erst recht < 1 + log(n), QED.

Wenn n sogar folgen Sie einfach die gleichen Schritte mit log(n) statt log(n-1) und ohne die „erst recht“ Finish, und der Beweis noch hält.

Answer 2

Ihre Antwort ist wahr, wenn Balanced Binärbaum abgeschlossen ist die Anzahl der Elemente in der rechten und linken Unterbaum sein kann (n-1) / 2, aber wenn es nicht vollständig ist, die Anzahl der Elemente müssen nicht sein (n-1) / 2 als letzte Ebene können unterschiedliche Elemente