Entwickler-Ecke :: Thema anzeigen - Balancierung am AVL-Baum

jawo3 - So 20.02.11 21:36
Titel: Balancierung am AVL-Baum

Hi,
ich habe eine Programm, dass nach Eingabe von Werten grafisch einen Binärbaum ausgibt, was soweit auch wunderbar funktioniert.

Jetzt soll dies um eine Funktion erweitert werden, die nach Klick auf einen Button den Baum durchfährt und bei Bedarf entsprechende Rotationen ausführt.

Die Knoten sind so aufgebaut:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

type
  Zeiger = ^Knoten;                //Definition eines Zeigertyps
  tInhalt = string[1];             //Knoteninhalt wird auf ein Zeichen beschränkt
  Knoten = record
    links: Zeiger;       //Zeiger auf linkes Folge-Element
    rechts: Zeiger;      //Zeiger auf rechtes Folge-Element
    Inhalt: tInhalt;     //Inhalt des Knotens
    balance: integer;    //gibt Differenz der linken und rechten Folgeelemente an (z.B. -2 --> 2 Elemente links zu viel)
  end;

Die Funktion soll der Einfachheit halber erstmal nur einfache Rotation nach links erlauben. Hier mein Versuch:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

procedure TForm1.ButtonBalancierenClick(Sender: TObject);
var zw,zw2: Zeiger;                  //Zeiger zum Zwischenspeichern
  procedure Balancieren(var z: Zeiger);
  begin
    if z<> nil then
    begin
      Balancieren(z^.links);
        if z^.balance>1 then
        begin
          zw:=z;
          zw2:=z^.rechts;
          z:=zw2;
          z^.links:=zw;
        end
    end;
  end;
begin
  Balancieren(wurzel);
  ausgeben(wurzel);
end;

Dies funktioniert allerdings nicht. Es scheint irgendeinen logischen Fehler in meiner Balance-Prozedur zu geben.

Vielleicht könnt ihr mir einen kleinen Denkanstoß geben.

Vielen Dank im Voraus
jawo3

PS: Im Anhang mal ein Bild von der beabsichtigten Funktion.

Xion - Mo 21.02.11 11:26

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

  private TNode AVL_RotateLeft(TNode node)
  {
    //      x          y
    //     /         / \
    //    y    ->   z   x
    //   /
    //  z  
    
    //  x.LeftChild -> y.RightChild
    //  y.RightChild  -> x
    
    //  wobei x=node y=node.LeftChild und z=node.LeftChild.LeftChild
    
    TNode y;
    
    y=node.LeftChild;
    
    node.Balance=node.Balance+2;
    y.Balance=y.Balance+1;
    
    node.LeftChild=y.RightChild;
    y.RightChild=node;
    
    return y; // y ist neue Wurzel
  }

Ich hatte das mal mit Java gemacht. Gucks dir mal an ;)

jawo3 - Mo 21.02.11 23:06

Danke erstmal für die Antwort!

Ich habe jetzt einen ersten Lösungsansatz, der bei einmaligem Ausführen auch ohne Fehler für den von Xion oben angegebenen Fall funktioniert.
Allerdings sieht das ziemlich schlecht aus :D

Ich hoffe ihr könnt mir helfen, dass ein bisschen besser zu schreiben.
Ich habe auch noch nicht ganz verstanden, warum ich Fehler in der Grafik-Zeichnen-Prozedur erhalte, wenn ich nicht mit new() in der Balance-Prozedur die Zeiger zum Zwischenspeichern bekanntgebe und für alle Record-Elemente Werte vergebe.

Hier also mein Quelltext / ich hoffe ihr könnt mir damit helfen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

procedure TForm1.ButtonBalancierenClick(Sender: TObject);
var zw,zw2,zw3: Zeiger;                  //Zeiger zum Zwischenspeichern
  procedure Balancieren(var z: Zeiger);
  begin
    new(zw);                       
    zw^.rechts:=nil;
    zw^.links:=nil;
    zw^.balance:=0;
    new(zw2);
    zw2^.rechts:=nil;
    zw2^.links:=nil;
    zw2^.balance:=0;
    new(zw3);
    zw3^.rechts:=nil;
    zw3^.links:=nil;
    zw3^.balance:=0;

    zw:=z^.links;                  // Linker Teilbaum wird zwischengespeichert
    zw2^.inhalt:=z^.inhalt;        // Inhalt der Wurzel wird zwischengespeichert
    z:=zw;                         // Wurzel wird durch linken Teilbaum ersetzt
    zw3^.inhalt:=zw2^.inhalt;
    z^.rechts:=zw3;
  end;
begin
  Balancieren(wurzel);
  GrafikSteuerung();
end;

Vielen Dank im Voraus
jawo3

Xion - Di 22.02.11 00:34

jawo3 hat folgendes geschrieben :

Delphi-Quelltext

1:
2:
3:
4:
5:

    zw:=z^.links;                  // Linker Teilbaum wird zwischengespeichert
    zw2^.inhalt:=z^.inhalt;        // Inhalt der Wurzel wird zwischengespeichert
    z:=zw;                         // Wurzel wird durch linken Teilbaum ersetzt
    zw3^.inhalt:=zw2^.inhalt;
    z^.rechts:=zw3;

Du machst das irgendwie komisch. Mal davon abgesehen, dass die nichtssagenden Namen deiner Variablen mich total durcheinander bringen, verschiebst du ja "Inhalt" durch die Gegend. Du musst die Knoten verschieben, da diese ja weiter Unterbäume haben können. Die müssen mitverschoben werden. So wie in der ersten Zeile.

Edit:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

    var y:Zeiger;
    [...]
    y:=z^.links;
    
    z^.Balance:=z^.Balance+2;
    y^.Balance:=y^.Balance+1;
    
    z^.links:=y^.rechts;
    y^.rechts:=z;

Probiers mal so, dass ist ne Adaption von meinem Java-Code ;)

jawo3 - So 27.02.11 01:15

Soooo...

Ich habe heute versucht, eine Doppelrotation-Funktion einzubauen, da der Baum bisher ja nicht optimal ausbalanciert werden kann. Wenn ich zum Beispiel: "D,A,C" eingebe, schafft die bisherige Prozedur keine gescheite Balancierung.

Wenn ich das richtig verstanden habe, setzt die Doppelrotation immer dann ein, wenn das Folgeelement des betroffenen Elements mit zu hohem oder zu niedrigem Balancewert eine genau gegensätzliche Balancestufe hat z.B. Wurzel hat zu viel links und das linke Folgeelement hat zu viel rechts.

Also habe ich eine Abfrage eingebaut, die genau dies testet und dann entsprechend zwei verschiedene Rotationen ausführt.

Lasse ich das Programm mit folgendem Quelltext laufen, erhalte ich allerdings immer die Fehlermeldung "EAccessViolation", wenn ich die Balance-Prozedur aufrufe.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:

procedure TForm1.ButtonBalancierenClick(Sender: TObject);
var y,x: Zeiger;                                                          //Zeiger zum Zwischenspeichern
procedure Balancieren(var z: Zeiger);
  begin
    if z<>nil then
    begin
      Balancieren(z^.links);
      if z^.balance<-1 then
      begin
        y:=z^.links;
        if y^.balance>0 then
          begin
            x:=y;
            y^.Balance:=y^.Balance-2;
            x^.Balance:=x^.Balance-1;
            y^.rechts:=x^.links;
            x^.links:=y;
            y:=x;
          end
        else
          begin
            z^.Balance:=z^.Balance+2;
            y^.Balance:=y^.Balance+1;
            z^.links:=y^.rechts;
            y^.rechts:=z;
            z:=y;
          end;
        end;
      end
      else if z^.balance>1 then
      begin
        y:=z^.rechts;
        if y^.balance<0 then
          begin
            x:=y;
            y^.Balance:=y^.Balance+2;
            x^.Balance:=x^.Balance+1;
            y^.links:=x^.rechts;
            x^.rechts:=y;
            y:=x;
          end
        else
        begin
          z^.Balance:=z^.Balance-2;
          y^.Balance:=y^.Balance-1;
          z^.rechts:=y^.links;
          y^.links:=z;
          z:=y;
        end;
      end;
    Balancieren(z^.rechts);
  end;
begin
  Balancieren(wurzel);                      //Aufruf der Balance-Prozedur
  Balance_Test(wurzel);                     //Neue Balancewerte werden ermittelt
  GrafikSteuerung();                        //Grafik wird neu gezeichnet
end;

Vielleicht könnt ihr mir nochmal einen kleinen Denkanstoß geben, das wäre super!

Vielen Dank im Voraus
jawo3

Horst_H - So 27.02.11 10:53

Hallo,

es gab im Forum schon mal die Anfrage AVl-Baum:
http://www.delphi-forum.de/viewtopic.php?t=45516&highlight=avlbaum
der Link auf Borland's Version ist nun auf
http://www.efg2.com/Lab/Library/UseNet/2000/0315c.txt
gelandet.Ich habe es mal komprimiert angehängt.
Da hat man direkt zu begin die rotate Befehle implementiert und sieht die diversen Bedingungen, die beim Umhängen der Knoten beachtet werden müssen.
Du kannst ja Kommentare dazu schreiben, was in jeder Zeile passiert, indem Du es aufzeichnest oder in der obengenannten PDF ab Seite 357 dies Schritt für Schritt verfolgst.

Gruß Horst

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!