avl bäume und aufbau < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:59 Fr 29.06.2007 | | Autor: | AriR |
| Aufgabe | Zeichnen Sie den AVLBaum, der entsteht, wenn man die Schlüssel 1 . . . 15 in dieser Reihenfolge
in einen anfangs leeren AVLBaum eingibt. Verallgemeinern Sie das Ergebnis (mit Beweis) auf die
Eingabe von 1 . . . 2k − 1 in sortierter Reihenfolge. |
hey leute,
das zeichnen des baumes ist erledigt.
ich hab nur par probleme mit dem beweis und zwar sieht man ja grob wie diese ca aufgebaut sind.
die blätter gehen alle ungerade zahlen von 1 bis 2k-1 durch
die wurzeln sind immer genau die geraden zahlen die zwischen den werten der zurgehörigen aüßeren blätter liegen nur ich hab absolut gar keine ahnung, wie man das beweisen kann oder ob überhaupt die genau mit aufbau des baumes gemeint ist.
dachte viell per induktion?
aber selbst wenn, hätte ich nicht einmal einen ansatz.
kann mir bitte einer von euch weiterhelfen
gruß ari :)
ahja hab mir auch noch gedacht man könnte zeige, dass diese bäume aufgrund der avl-bedingung und der 2k-1 knoten immer vollständig sind und diese, da sie ja auch binäre bäume sind, bei einer inorder-traversierung alle knoten in sortierter reihenfolge ausgeben
man anhand der anzahl der knoten einen baum mit noch leeren knoteninhalt zeichnen könnte und dann die werte einfach nachträglich in inorderreihenfolge in dem baum einträgt.
was mich hier jedoch stutig macht ist, ob man im beweis sagen kann "die wert in inorderreihenfolge eintragen" das hört sich nicht sehr formal an.
hat einer vielleicht noch ne idee, ob man diesen weg weitergehen könnte?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 03.07.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
