Aufgabe: Binär-Bäume

[nubius]

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

[nubius]

Habs gelöst, hat sich somit erledigt.

[derJan]

nur so aus Neugierde, macht ihr solche Aufgaben in der Berufsschule?

[geloescht_Newlukai]

Wie lautet denn die Lösung?

[babakurmanj]

was für einen lösungsweg habt ihr verfolgt???

wäre sehr nett wenn ich paar hilfreiche tipps kriege..

danke:D