Praktikum 6

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Beitrag von Siggi »

ja, wenn du den baum direkt so erstells, hats du recht.
Aber hier geht es um den Fall, das du den baum schon richtig erstellt hast, und dann nen Knoten löschst. Stell dir einfach vor, an der 1 hängt links ne 0.

Code: Alles auswählen

     1  
   /   \ 
  0     3
      /   \ 
     2     4

Dann ist das ein gültiger Baum. Wenn du jetzt die 0 löschtst, dann stehts du vor dem Problem, wie du rotierst.

Der Baum kann aber auch ohen Problem einfach rotiert werden:

Code: Alles auswählen


 1                                     3
   \                                  /  \
    3                               1     4
  /   \                              \
 2     4                             2


P.S. Du musst den Baum als Code schreben, dann klappts :)

qveXx
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 2. Dez 2005 19:02

Beitrag von qveXx »

Siggi hat geschrieben:Der Baum kann aber auch ohen Problem einfach rotiert werden:
Hast Recht, hab mir mal die Folien etwas genauer angeschaut und habe bemerkt, dass diese Variante einfach rotieren ist. Aus irgend einem Grund dachte ich, dass es ne doppelte Rotation wäre ;)

Siggi hat geschrieben:P.S. Du musst den Baum als Code schreben, dann klappts :)
Man lernt als Iinformatiker nie aus :p

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag von RomanSoldier »

qveXx hat geschrieben: PS: kA wieso mein Baum in der Vorschau halbwegs lesbar dargestellt wird, aber hier nicht ;)
Weil Leerzeichen in der Ausgabe gelöscht werden; am besten benutzt du die code-Umgebung.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

Naja, der Baum entsteht nur beim Löschen.

Also zum Beispiel:

Code: Alles auswählen

  1
0  3
   2 4
Und dann wird die 0 gelöscht.

Jetzt kann man rotieren wie man will ...

RR:
Dann hat B1 und B2 beide die Höhe h+1.

oder
RL:
B2 und B3 beide h-1 (also 0)
"Copy & Passed"

Wahlspruch der Plagiatoren

Erebos
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 27. Apr 2007 00:51

Beitrag von Erebos »

Ich steh grad ein bisschen auf dem Schlauch was die erkennung von Doppel-Rotation angeht, als Beispiel folgender Baum:

Code: Alles auswählen

      2
   /    \
 1       5
        /   \
       4     6
So und wenn ich jetzt | 3 | einfügen will kommt es ja nur RL-Rotation. Meine Frage ist nun, wie erkennt ihr eine solche?
Ich gehe normalerweise vom eingefügten Knoten nach oben und setzte die Höhe an jeder Wurzel plus 1, wenn ich einen BF von -2/plus2 entdecke mache ich an diesem die Rotation.
Das geht aber logischerweise in dem Beispiel schief.
Geht ihr, wenn ihr einen BF von -2 entdeckt zurück bis ihr einen BF mit +1 entdeckt und rotiert erst an diesem?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

es geht ums löschen.. denk dir mal an die linke seite von 1 noch ne 0, wenn du die 0 jetzt löschst hast du genau den baum und kannst ihn sowohl durch einfach- als auch durch doppelrotation ausbalancieren.

Erebos
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 27. Apr 2007 00:51

Beitrag von Erebos »

bei meiner Frage geht es nicht ums löschen, sondern ums hinzufügen
ich wollt jetzt nicht extra ein neues Thema aufmachen, sondern einfach nur wissen welche Strategie man für mein Problem nehmen sollte

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

oh äh ups, ich hab deinen baum irgendwie falsch gelesen, sorry..

die RL-Rotation erkennst du daran, dass auf deinem pfad vom eingefügten knoten irgendwann ein balanceungleichgewicht von -2 entsteht, bei deinem baum im knoten 2, und am größer-kindknoten (5 in deinem baum) ein ungleichgewicht von +1. dann hast du ne RL-Rotation in dem knoten wo die 2 war.

Erebos
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 27. Apr 2007 00:51

Beitrag von Erebos »

Ok danke erstmal :)
Nur was wäre wenn das ungleichgewicht nicht direkt ein Kind ist, dann muss man doch den pfad rückwärts laufen und schauen ob es ein ungleichgewicht gibt?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

du gehst von dem knoten aus wo du den neuen eingefügt hast den ganzen pfad nach oben. Wenn du bis zur wurzel kommst ohne ein ungleichgewicht von +2 oder -2 anzutreffen brauchst du garnicht rotieren, sobald du aber eins findest musst du in dem entsprechenden knoten ne rotation machen, welche hängt vom direkten kind ab (größer-kind bei -2, kleiner-kind bei +2). Wenn du beim einfügen einmal rotiert hast brauchst du die weiter oben liegenden knoten theoretisch nicht mehr zu prüfen, die sind alle balanciert dann, aber das noch einzubauen ist wesentlich mehr aufwand als einfach alle knoten nach oben auf +-2 balance zu testen, geht einfacher und ist auch für den rechner nicht mehr arbeit. Beim löschen musst du aber dann auf jeden fall für jeden knoten auf dem pfad zur wurzel die balance testen, steht ja auch im script. da können bis zu log(n) rotationen nötig sein. da die ganzen rotationen aber O(1) haben stört das keinen.

qveXx
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 2. Dez 2005 19:02

Beitrag von qveXx »

Erebos hat geschrieben:Ich steh grad ein bisschen auf dem Schlauch was die erkennung von Doppel-Rotation angeht, als Beispiel folgender Baum:

Code: Alles auswählen

      2
   /    \
 1       5
        /   \
       4     6
So und wenn ich jetzt | 3 | einfügen will kommt es ja nur RL-Rotation. Meine Frage ist nun, wie erkennt ihr eine solche?
Ich gehe normalerweise vom eingefügten Knoten nach oben und setzte die Höhe an jeder Wurzel plus 1, wenn ich einen BF von -2/plus2 entdecke mache ich an diesem die Rotation.
Das geht aber logischerweise in dem Beispiel schief.
Geht ihr, wenn ihr einen BF von -2 entdeckt zurück bis ihr einen BF mit +1 entdeckt und rotiert erst an diesem?
Wie Mister bereits erwähnt hat, schauste dir dazu einfach die Folien an und vergleichst die Knoten, wie deren Balance jeweils vor der Rotation ausschaut und wie anhand dieser dann in den Folien rotiert wird.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Also nur mal um das klarzustellen:

Es gibt prinzipiell 4 eindeutige Fälle der Rotation:
1. Fall RR (Knoten hat Balance -2, rechtes Kind hat Balance -1)
2. Fall RL (Knoten hat Balance -2, rechtes Kind hat Balance 1)
3. Fall LL (Knoten hat Balance 2, linkes Kind hat Balance 1)
4. Fall LR (Knoten hat Balance 2, linkes Kind hat Balance -1)

und 2 nicht eindeutige, die aber durch die Aufgabenstellung präzisiert worden sind:
1. Fall RR (Knoten hat Balance -2, rechtes Kind hat Balance 0)
2. Fall LL (Knoten hat Balance 2, linkes Kind hat Balance 0)

So, und wie man jetzt bei welchem Fall rotiert, sollte man aus den Folien entnehmen können.

Und wenn ein Fall eintritt: Knoten hat Balance 2, linkes Kind hat Balance -2, etc.
dann würde ich empfehlen an diesen Stellen keine Rotation durchzuführen, weil diese evtl unnötig wäre, weil das "Problem" auch am nächsten Knoten (mit Balance -2) noch gelöst werden kann.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

ähm oO
wenn das kind ne balance von +- 2 hat hast du vorher was falsch gemacht, da hättest du schon im kind rotieren müssen. du gehst normalerweise die knoten von unten nach oben durch..

Benutzeravatar
seth2k1
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 29. Sep 2006 00:53
Wohnort: Darmstadt - Eberstadt

Beitrag von seth2k1 »

hat er das nicht geschrieben dass sich das problem dann schon im kind befindet? ;)
kommt drauf an wie man vorgeht, aber von unten nach oben ist es einfacher. das stimmt
"Hallo, ich verkaufe diese modischen Lederjacken!"

benrub
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 3. Dez 2006 01:26

Beitrag von benrub »

An qveXx' 2. punkt ist was wahres dran. Kein wunder, daß es so einen Test nicht gibt :)

Antworten

Zurück zu „Archiv“