Binärer Baum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:06 Fr 29.12.2006 | | Autor: | smee |
| Aufgabe | Sei B ein binärer Baum, in dem für jeden inneren Knoten u mit den Nachfolgern [mm] u_l [/mm] und [mm] u_r [/mm] der Höhenunterschied der beiden Teilbäume mit den Wurzeln [mm] u_l [/mm] und [mm] u_r [/mm] höchstens 2 ist. Sei h(B) die Höhe und n(B) die Anzahl der Knoten von B. Zeigen Sie, dass gilt:
[mm]h(B) \in O(log(n(B)))[/mm] |
Hallo alle!
Diese Aufgabe ist Teil einer Hausaufgabe, und ich tue mich etwas schwer, einen formal korrekten Ansatz für eine Lösung zu finden. Ich wäre deshalb für jede Hilfe dankbar.
Grundsätztlich leuchtet mir schon ein, warum die obige Beziehung gelten muss: Wenn ich bei einem Baum mit diesen Eigenschaften die Höhe verändern, also einen Knoten an die "unterste" Ebene hängen will, so muss ich dafür sorgen, dass die geforderten Eigenschaften erhalten bleiben (Höhenunterschied der Teilbäume). D.h. ich muss ggfs. die "oberen" Teilbäume mit Knoten ergänzen, bevor ich die Höhe des gesamten Baumes ändern kann ... Also je höher der Baum, desto mehr Knoten muss ich einfügen, um das nächste Level zu erreichen  ... woraus sich ergibt, dass die Höhe des Baumes sich logarithmisch zur Anzahl der Knoten verhält.
Das ist ein bisschen schwammig ausgedrückt. Und das ist eben mein Problem - ich weiß nicht so recht, wie ich das formal aufschreiben kann. Anbieten würde sich ja evtl. ein Beweis per Induktion?!
Was mir auch nicht ganz klar ist: Inwiefern die Definition aus der Aufgabe entartete Bäume zulässt. Das wären also Bäume, bei denen (fast) alle Knoten nur einen Nachfolger haben. Reicht es, diese Fälle als "Worst Case" außen vor zu lassen?
Übrigens ist nicht gefordert, dass wir einen vollständigen mathematischen Beweis liefern, soweit ich das verstanden habe. (Was auch immer das genau heißt).
Viele Grüße,
Carsten
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Sa 06.01.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
