Erstmal Hallo!
Bei dieser (eigentlich leider trivialen) Aufgabe komm ich nicht weiter :beagolisc
--------------------------------
Sei B ein binärer Baum, in dem für jeden inneren Knoten u mit den Nachfolgern
ul und ur der Höhenunterschied der beiden Teilbäume mit den Wurzeln ul und ur höchstens
2 ist. Sei h( die Höhe und n( die Anzahl der Knoten von B. Zeigen Sie, dass für Bäume B dieser Art die folgende Beziehung gilt:
h( ∈ O(log(n())
-------------------------------
Eigentlich müsste man das ja so wie bei den AVL-Bäume mit der Fibbonnaci-Rekursion beweisen, oder?
Über einen Ansatz der mir weiter hilft, wäre ich sehr dankbar!
grüße
nubius
