Aufgabe 2 (AVL-Baeume)
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur vom 05.08.2010
Hallo,
bin gerade bei der Aufgabe 2 (AVL-Baeume) der Klausur vom 05.08.2010.
habe bei der a) folgendes herausbekommen:
Passt das so?
AVL-Baum duerfte es demzufolge nicht sein, da sich die Hoehen der Teilbaeume um mehr als 1 unterscheiden.
Danke!
/edit:
bei der c) tut sich mir eine Frage auf:
man soll hier den vorgegebenen Rumpf ergaenzen…
Soll man hier den rechten Teilbaum auch zeichnen oder nur die Werte in den rechten Teilbaum einfuegen?
/edit2:
bei e) heisst es:
[quote=Aufgabenstellung]Begründen Sie, warum das Löschen in O(log n) möglich ist. Be-
trachten Sie dazu detailliert jeden Einzelschritt des Verfahrens.[/quote]
Jemand ne Idee?
Ich denke die meinen sowas wie: Suchen des zu löschenden Knotens O (log n). Ersetzen des Knotens mit dem dem am weitesten rechten Knoten. Diesen suchen im linken Teilbaum O(log n). Überschreiben des Knotens mit der Wurzel des (evtl. Teil-) Baums O(1). In jeder Hirarchie kann nun die AVL Eigenschaft verletzt sein → wiederherstellen O(log n). Gesamt: O(log n)
sieht richtig aus
genau
ich denke nur einfügen.
mmn ist die lösung bei der a) falsch.
man berechnet den balancefaktor doch so: linker teilbaum - balance MINUS rechter teilbaum - balance.
und -2-1 = -3
klärt mich auf, wenn ich mich irre.
und bei den nächsten teilaufgaben steht dann: “Ersetzen Sie falls n¨otig einen inneren Knoten durch den
größten Eintrag im linken Unterbaum.”
das ergibt für mich keinen sinn, weil wenn ich einen knoten ersetze, ist der ja weg und ich hab nen ganz anderen baum. das richtige verfahren wäre doch den baum zu rotieren.
zb bei der a) würde ich folgendes schreiben:
21
/ \
5 95
/ \
4 10
Ja, du irrst dich. Siehe Vorlesungsfolien.
Das „richtige“ Verfahren ist das, was die Aufgabenstellung vorgibt. Was machst du denn, wenn du einen Knoten loeschen musst, z.B. die Wurzel. Du hast zwei Unterbaeume, die du nicht nur durch Rotation verbinden kannst. Um die Suchbaumeigenschaft weiterhin zu erfuellen (wie es AVL-Baeume ja tun), muss man einen passenden Knoten an die Stelle setzen. Wenn in diesem Suchbaum x geloescht wird:
x
/
? …
/
? ?
/ /
… … y
hast du zwei Teilbaeume:
?
/
? ? und …
/ /
… … y
Aus der Suchbaumeigenschaft kannst du dir aber herleiten, dass y der Knoten im Baum ist der gerade noch kleiner ist als x und dass es keinen Knoten im Baum gibt mit einem Wert zwischen y und x (war auch mal eine Aufgabe, das selbst herauszufinden; hier vorgegeben, damit ihr nicht so viel Zeit mit der Ueberlegung verbraucht).
Mit diesem Wissen koennen wir y an die Stelle von x setzen, ohne die Suchbaumeigenschaft zu verletzen.
y
/
? …
/
? ?
/ /
… …
Danach muss natuerlich noch rotiert werden falls die AVL-Eigenschaft nicht erfuellt ist.
Das ist Teilaufgabe b.
ich komme bei d) auf folgenden baum
42
/ \
23 50
/ \ \
5 37 69
stimmt der so?
ich frage mich gerade, was die Aufgabe c) soll…
Standardmaessig sieht der Baum ja so aus:
(sry, die (30) sollte eigentlich weiter links stehen.)fixed.
Dann soll man die 28 einfuegen.
Da bekomm ich diesen Baum:
Man soll aber nur die rechte Seite ausfuellen, doch da aendert sich (zumindest bei mir) nichts.
Das kann eigentlich nur noch eins heissen…
hättest du den baum anständig gemalt wärs die aufgefallen.
die 30 ist kleiner als die 35 hängt also nach links. somit kannst du an die35 nicht links noch was dranhängen, sondern musst es an die 30 dranhängen.
das ist doch genau das, was ich mache.
Ich haenge es an die 30 und anschliessend muss ich rotieren, da AVL-Eigenschaft verletzt und erhalte den Baum weiter unten.
und wo genau ist jetzt das Problem?
naja, am rechten Teilbaum von der Wurzel aus gesehen aendert sich nichts, aber genau diesen soll man in der Skizze vervollstaendigen, was mich eben ein wenig stutzig macht 
Aber wenn’s soweit passt, auch nicht unrecht 
wie ist denn die Aufgabenstellung genau?
Hä…
Er hat doch deswegen auch die rechte Seite schon hingemalt und geschrieben: ergänzen sie den Rumpf. Damit wir net so viel schreibarbeit haben. find ich persönlich nett eigentlich.
ach so xD
dann hab ich das wohl etwas falsch interpretiert…alles klar, danke!