Not logged in. · Lost password · Register

blabori
:maerp
Member since Oct 2011
236 posts
Subject: 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:

[Image: http://i.imgur.com/lvTw8.png]

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 by Aufgabenstellung:
Begründen Sie, warum das Löschen in O(log n) möglich ist. Be-
trachten Sie dazu detailliert jeden Einzelschritt des Verfahrens.

Jemand ne Idee?
This post was edited 2 times, last on 2012-02-20, 19:28 by blabori.
Guanta
Avatar
Member since Oct 2005
307 posts
Quote by blabori:
bei e) heisst es:

Quote by Aufgabenstellung:
Begründen Sie, warum das Löschen in O(log n) möglich ist. Be-
trachten Sie dazu detailliert jeden Einzelschritt des Verfahrens.

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)
An eye for an eye will make the whole world blind. (Gandhi)
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #1
Quote by blabori:
Hallo,

bin gerade bei der Aufgabe 2 (AVL-Baeume) der Klausur vom 05.08.2010.

habe bei der a) folgendes herausbekommen:

[Image: http://i.imgur.com/lvTw8.png]

Passt das so?
sieht richtig aus
Quote by blabori:
AVL-Baum duerfte es demzufolge nicht sein, da sich die Hoehen der Teilbaeume um mehr als 1 unterscheiden.
genau
Quote by blabori:
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?
ich denke nur einfügen.
An eye for an eye will make the whole world blind. (Gandhi)
darkyke
Member since Nov 2011
97 posts
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
meisterT
Member since Nov 2005
994 posts
Quote by darkyke:
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.

Ja, du irrst dich. Siehe Vorlesungsfolien.


Quote by darkyke:
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.

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.


Quote by darkyke:
zb bei der a) würde ich folgendes schreiben:

                    21
                  /      \
               5          95
             /     \
          4        10

Das ist Teilaufgabe b.
FAU Online Judge
asdfg
Member since Jan 2012
4 posts
ich komme bei d) auf folgenden baum

                  42
                 /   \
               23   50
              /  \      \
             5   37    69

stimmt der so?
ri31hoky
Member since May 2011
452 posts
http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.h…
blabori
:maerp
Member since Oct 2011
236 posts
ich frage mich gerade, was die Aufgabe c) soll...

Standardmaessig sieht der Baum ja so aus:

[Image: http://i.imgur.com/AVZxp.png]
(sry, die (30) sollte eigentlich weiter links stehen.)fixed.

Dann soll man die 28 einfuegen.
Da bekomm ich diesen Baum:

[Image: http://i.imgur.com/gwFIA.png]

Man soll aber nur die rechte Seite ausfuellen, doch da aendert sich (zumindest bei mir) nichts.
Das kann eigentlich nur noch eins heissen...
This post was edited on 2012-02-21, 12:01 by blabori.
bewi1992
Member since Oct 2011
189 posts
Quote by blabori:
ich frage mich gerade, was die Aufgabe c) soll...

Standardmaessig sieht der Baum ja so aus:

[Image: http://i.imgur.com/oQJYY.png]
(sry, die (30) sollte eigentlich weiter links stehen.)

Dann soll man die 28 einfuegen.
Da bekomm ich diesen Baum:

[Image: http://i.imgur.com/gwFIA.png]

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.
blabori
:maerp
Member since Oct 2011
236 posts
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.
N.K.
Member since Nov 2011
87 posts
Quote by blabori:
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?
blabori
:maerp
Member since Oct 2011
236 posts
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 :D
bewi1992
Member since Oct 2011
189 posts
wie ist denn die Aufgabenstellung genau?
N.K.
Member since Nov 2011
87 posts
In reply to post #12
Quote by blabori:
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 :D

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.
blabori
:maerp
Member since Oct 2011
236 posts
ach so xD

dann hab ich das wohl _etwas_ falsch interpretiert...alles klar, danke!
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen