Fehler beim Auflösen und Freigeben eines dynamischen Tree's

[noob2k9]

Hi DP-User,

ich habe einen Fehler identifiziert der mir nun schon einige Stunden Kopfzerbrechen bereitet.

Während der Laufzeit meines Programmes führe ich eine vollständige Enumeration (mit diversen Abbruchbedingungen) durch und generiere so in einem rekursiven Algorithmus einen Baum dessen Blätter immer auf die übergeordneten Äste/Elemente (Parents) zeigen.
Die Verknüpfung wird nur in eine Richtung "bottom-up" realisiert.

Die Blätter werden in dem Array variations gespeichert, so dass jede gefundene Lösung rekonstruiert werden kann in dem von dem Blatt jedes Parent zurückverfolgt wird bis man bei dem Root-Element ankommt.
Das Root-Element besitzt als Parent einen Pointer auf nil um so dass Ende zu markieren.

Nun stehe ich vor folgendem Problem: Wenn ich versuche den Speicher der durch den entstandenen Baum belegt wird freizugeben erhalte ich eine Zugriffsverletzung beim Schreiben auf den Speicher.
Ich habe die Ursache bereits soweit zurückverfolgt dass ich sagen kann wo der Fehler auftritt, nämlich sobald der Ast bereits "abgesägt" wurde - also ein anderes Child (Blatt) einen ähnlichen Pfad hatte und durch die while ... do - Schleife bis zum Parent/Root aufgelöst wurde.

Ergo: Das Record wurde bereits aufgelöst und der Zeiger zeigt nun irgendwo ins Nirvana.

Ich hoffe ich konnte das Problem ausreichend beschreiben.
Nun zur eigentlichen Frage: Gibt es eine Möglichkeit wie ich dies verhindern kann oder gar eine bessere Möglichkeit den Tree aufzulösen?

Delphi-Quellcode:

type
  T_Container_2D = record
    parent: Pointer;
    x1: Integer;
    y1: Integer;
    x2: Integer;
    y2: Integer;
  end;

type
  T_Variations_2D = Array of Pointer;

procedure Clear();
var
  i, l: Integer;
  now, next: P_Container_2D;
begin
  // Init
  i := 0;
  l := Length(variations) - 1;

  for i := l downto 0 do begin
    now := variations[i];
    while now <> nil do begin
      if now^.parent <> nil then begin
        next := now^.parent;
        FreeMemory(now);
        now := nil;
        now := next;
      end
      else begin
        now := nil;
      end;
    end;
  end;

  SetLength(variations, 0);
end;

[Bummi]

Delphi-Quellcode:

procedure Clear();
var
  i, l: Integer;
  now, next: P_Container_2D;
begin
  // Init
  i := 0;
  l := Length(variations) - 1;

  for i := l downto 0 do FreeMemory(variations[i]);
  SetLength(variations, 0);
end;

[noob2k9]

Auf diese Weise werden aber (wenn ich jetzt keinen groben Schnitzer habe) nicht die Parents mit aufgelöst? In dem Array variations werden wie bereits erwähnt nur die Childs der letzten Ebene gespeichert.

Edit: Im Anhang eine fixe Visualisierung des Trees

[Bummi]

sorry, hatte ich falsch verstanden.
Dann in Deinem "Löschlauf" nicht die Parents löschen, sondern in einer weiteren Liste Unique sammeln. Aus dieser Liste löschen.

[noob2k9]

So simpel dass ich es selbst übersehen habe - werde mich mal an die Umsetzung machen und berichten.

[noob2k9]

Ok, der Algorithmus funktioniert soweit dennoch stoße ich vor das nächste Problem: Die einzelnen Äste können unterschiedliche Längen aufweissen so dass es dennoch passieren kann (und auch passiert) dass ein Pointer bereits früher zurückgesetzt wird und anschließend in einem längeren Ast erneut versucht wird zurückzusetzen - was natürlich wieder zu einem Speicher-Leck führt.

Ich glaube ich komme nicht drum herum erst alle Äste komplett zu durchlaufen und ein Unique Array zu erzeugen und im Anschluss daran alle Elemente zu löschen. Dies kann im Worst-Case (~4 Mio. Leafs mit einer Tiefe bis zu ~25) allerdings recht aufwändig werden.