Baum-Interator implementieren

[VizeTE]

Hallo,

ich habe ein Baumstruktur und möchte für diese Struktur einen Iterator entwickeln.
Prinzipiell ist mir klar wie ein Iterator funktioniert.
Es soll ein externen Iterator werden, also der Klient steuert den Ablauf.

Was mir noch nicht so richtig klar ist, ist die Implementation des Methode "Next", also der Aufruf des nächsten Elements.

Ich stelle mir das folgendermaßen vor:
- ich übergebe das root-Element
- der erste Aufruf von Next gibt des erste Kind zurück
- der nächste Aufruf gib das erste Kind des Kindes zurück, sofern vorhanden
=> somit wird in die Tiefe gegangen
- hat das aktuelle Kind keine Kinder so wird der nächste Nachbar/Bruder zurückgegeben

Soweit ist mir das erstmal klar. Ich bin mir aber noch nicht sicher wie ich folgende
Situation abbilde:

Der Iterator steht aktuell auf einem Kind, welches das Letzte des Eltern-Elements ist.
Jetzt wird "Next" aufgerufen. Da das aktuelle Kind keine eigenen Kinder hat und selbst
das Letzt des Elternelements ist so muß "Next" den Bruder des Eltern-Elements zurückgeben.

Genau hier liegt mein Problem. Welche Möglichkeiten gibt es den Bruder des Eltern-Elements
herauszubekommen. Mir fallen 2 Möglichkeiten ein, die mir beide nicht 100%ig gefallen.

1. Ich gehe zum Eltern-Element und frage dessen Eltern-Element nach der Liste seine Kinder.
In dieser List suche ich mein Eltern-Element (von dem ich den Bruder haben möchte) und nehme
den Nachfolger. - Hat den Nachteil, daß hier ganz schön viel traversiert werden muß.

2. Beim einfügen des Elements in den Baum speichert dieses Element einen Pointer auf den Nachfoger.
- Diese Lösung hat aber den Nachteil, daß einiges mehr an Verwaltungsaufwand entsteht. Zudem kann ich dann das Element auch nicht in 2 unterschiedlichen Bäumen verwenden.


Ich hoffe ich habe mich nicht zu kompliziert ausgedrückt und ihr habt ne tolle Idee für mich :zwinker:
Schon mal Vielen Dank - Daniel

[Dax]

Wenn du einen Baum hast, nutzt du doch hoffentlich verlinkte Listen für die Elemente? Dann wäre der Bruder ganz einfach rauszubekommen: Parent.Next ;) Dabei speichert Parent in einem Element das Elternelement, Child das Kindelement, Next das nächste und Previous das vorherige Element^^

[BlackJack]

Zitat:

Zitat von VizeTE

Der Iterator steht aktuell auf einem Kind, welches das Letzte des Eltern-Elements ist.
Jetzt wird "Next" aufgerufen. Da das aktuelle Kind keine eigenen Kinder hat und selbst
das Letzt des Elternelements ist so muß "Next" den Bruder des Eltern-Elements zurückgeben.

wenn du .Next eines Knotens aufrufst, der keine Kinder hat, dann sollte doch eigentlich nil zurückgegeben werden, oder? wenn man dann einfach nen anderen knoten (z.b. nachbarn) zurückgibt, dann denkt man doch, der Knoten selber hätte Kinder.

[Hawkeye219]

Hallo Daniel,

Du könntest in einem vorbereitenden Schritt mit einer rekursiven Routine den Baum durchlaufen und dabei Verweise auf alle besuchten Knoten in einem (dynamischen) Array ablegen. Die Next-Routine muß dann dieses Array nur noch sequentiell abarbeiten.

Gruß Hawkeye

[VizeTE]

Zitat:

Zitat von Dax

Wenn du einen Baum hast, nutzt du doch hoffentlich verlinkte Listen für die Elemente? Dann wäre der Bruder ganz einfach rauszubekommen: Parent.Next ;) Dabei speichert Parent in einem Element das Elternelement, Child das Kindelement, Next das nächste und Previous das vorherige Element^^

Bisher keine verlinkte Liste. Das war je meine Idee in Punkt 2 des Eingangs-Posts. Gibt es eine fertige verlinkte Liste in Delphi 7 oder muß ich das selbst implementieren?
Wie würde das dann laufen. Wo werden die Links gespeichert? Ich möchte die Links ungern in den Elementen speichern da ich diese dann nicht in mehreren Bäumen gleichzeitg verwenden kann.
Wenn sich das ohne viel Verwaltungsaufwand lösen läßt ist das sicher eine gute Idee.

Zitat:

Zitat von BlackJack

wenn du .Next eines Knotens aufrufst, der keine Kinder hat, dann sollte doch eigentlich nil zurückgegeben werden, oder? wenn man dann einfach nen anderen knoten (z.b. nachbarn) zurückgibt, dann denkt man doch, der Knoten selber hätte Kinder.

Nicht ganz. Ich möchte dann nicht den Nachbarn des aktuellen Knotens sondern den Nachbarn des Elternknoten zurückgeben, sofern vorhanden. Es handelt sich um einen Baum und nicht um eine flache Liste.

Zitat:

Zitat von Hawkeye219

Du könntest in einem vorbereitenden Schritt mit einer rekursiven Routine den Baum durchlaufen und dabei Verweise auf alle besuchten Knoten in einem (dynamischen) Array ablegen. Die Next-Routine muß dann dieses Array nur noch sequentiell abarbeiten.

Das ist ne Idee. Ich befürchte aber, daß das zu viel Zeit kostet wenn die Bäume sehr groß werden. - Sorry, daß ich hier so negativ eingestellt bin. :zwinker:


Aber mir ist da auch noch was eingefallen. Was haltet ihr davon, wenn man innerhalb des Iterators einen Stack verwaltet. Jedes mal wenn ich eine Ebene in die Tiefe gehe wird ein neues Element auf den Stack gelegt, welches Informationen enthält, welchen Index das Element hat (von dem ich komme). Wenn ich dann wieder eine Ebene aufsteige bekomme ich so einfach den Index des Nachfolgers heraus und lösche das oberste Stack-Element.

[marabu]

Hallo Daniel,

Zitat:

Zitat von VizeTE

Was haltet ihr davon, wenn man innerhalb des Iterators einen Stack verwaltet.

jetzt bist du auf dem richtigen Weg.

Nachtrag: Bei weiterem Nachdenken komme ich zu dem Schluss, dass ich viel zu viele Annahmen mache, wo von deiner Seite fast keine Information über die Implementierung der Baumstruktur vorliegt. Ob du den Stack einsetzt oder besser mit Markierungen arbeitest, das hängt zum Teil auch von der Implementierung der Knoten ab.

Grüße vom marabu

[VizeTE]

Zitat:

Zitat von marabu

Nachtrag: Bei weiterem Nachdenken komme ich zu dem Schluss, dass ich viel zu viele Annahmen mache, wo von deiner Seite fast keine Information über die Implementierung der Baumstruktur vorliegt. Ob du den Stack einsetzt oder besser mit Markierungen arbeitest, das hängt zum Teil auch von der Implementierung der Knoten ab.

Die Definition der Baumstruktur liegt vollständig in meiner Hand. Von daher bin ich dort flexibel. Prinzipiell finde ich es gut wenn man die einzelnen Knoten auch in mehreren Bäumen verwenden kann. Ich weiß nicht genau wie du dir die Umsetzung mit Markierungen gedacht hast. Würde ich dann den Knoten selbst als solchen markieren, daß ich genau an diesem abgestiegen bin?
Könntest du mal kurz Umreißen wie du das Problem mit Markierungen angehen würdest?

Danke!

[Hawkeye219]

Hallo Daniel,

eine Markierung der Knoten hätte meiner Meinung nach den Nachteil, daß bei Änderungen im Baum alle Knoten zurückgesetzt werden müssen. Da Du offenbar mit einer großen Zahl von Knoten arbeitest, ist dies eine sehr teure Operation.

Ist der zusätzliche Aufwand zur Erstellung einer linearen Liste von Knoten wirklich so groß, wenn Du sowieso alle Knoten im Baum besuchen möchtest? Bei riesigen Bäumen fällt da eher der zusätzlich benötgte Speicherplatz ins Gewicht. Das ist dann der Preis, den Du für eine simple Next-Funktion bezahlst.

Dein Vorschlag mit dem Stack läßt sich sicher umsetzen, ohne die Knoten mit zusätzlichen Daten zu belasten. Der folgende Code ist ein Versuch(!), der von folgenden Voraussetzungen ausgeht:

1. Jeder Knoten besitzt eine Methode FirstChild, die einen Zeiger auf das erste Kind des Knotens liefert.
2. jeder Knoten besitzt eine Methode NextSibling, die einen Zeiger auf den rechten Bruder des Knotens liefert.
3. Es existiert ein Stack mit den Methoden Push, Pop und IsEmpty.

Delphi-Quellcode:

type
  TIterator = class
  private
    // Zeiger auf den nächsten zu liefernden Knoten
    FNext : TNode;
    // Zeiger auf die Wurzel des Baums
    FRoot : TNode;
  public
    // Konstruktor
    constructor Create (aRoot: TNode);
    // liefert den nächsten Knoten
    function Next: TNode;
    // Setzt den Iterator zurück
    procedure Reset;
  end; // TIterator

consturctor TIterator.Create (aRoot: TNode);
begin
  FRoot := aRoot;
  Reset;
end;

function TIterator.Next: TNode;
begin

  // Zeiger auf den nächsten abzuarbeitenden Knoten des Baums liefern
  Result := FNext;
  
  // Nächsten abzuarbeitenden Knoten ermitteln, falls noch Knoten vorhanden sind
  if Assigned(FNext) then

    // Prüfe, ob der aktuelle Knoten Kinder besitzt
    if Assigned(FNext.FirstChild) then
      begin
      
        // Der aktuelle Knoten besitzt Kinder.
        // Aktuellen Knoten im Stack speichern, Zeiger auf das erste Kind holen
        Stack.Push (FNext);
        FNext := FNext.FirstChild;
        
      end
    else
      repeat
        begin
      
          // Falls der aktuelle Knoten einen Bruder besitzt, ist dies der nächste Knoten
          FNext := FNext.NextSibling;
          if Assigned(FNext) then
            Break;

          // Der Teilbaum wurde komplett abgearbeitet, zurück zur vorigen Ebene
          if Stack.IsEmpty then
            FNext := NIL
          else
            FNext := Stack.Pop;
          
        end; // while Assigned()
      until (FNext = NIL);

end;

procedure TIterator.Reset;
begin
  FNext := FRoot;
end;

Ich hoffe, es sind nicht allzu viele Fehler drin.

Gruß Hawkeye

[r2c2]

Muss es unbedingt n Iterator sein? Reichts vielleicht auch, einfach nur ne rekursive Funktion zu benutzen:

Delphi-Quellcode:

//Pseudocode:
TNode = class
private
  ...
  FChildren: TNodeList; // Typed TObjectList
public
  ...
  property Chrildren: TNodeList read ... write ...;
end;

TBaum = class
private
  ...
  FRoot: TNode;
public
  ...
  procedure HandleAllNodes(AProc: <CallBackFunction>);
  ...
  property Root read FRoot write FRoot;
end;

procedure TBaum.HandleAllNodes(...);
begin
  // rekursiv alle Nodes durchgehen und die CallBackFunction aufrufen
end;

Wenn du unbedingt n Iterator haben willst, kannst du das so auch machen:

Delphi-Quellcode:

TIterator = class
private
  ...
  FCurrentNode: Integer; // Nummer des Knotens, der zuletzt ermittelt wurde
  FCounter: Integer; // Counter für Next;
public
  ...
  procedure Reset;
  function Next: TNode;
end;

function TIterator.Next: TNode;
begin
  // solange FCounter <= TCurrentNode
  // rekursiv durchsuchen
  // wenn FCounter = TCurrentNode
  // Suche abbrechen und Node zurückliefern
end;

Is vielleicht nicht die Beste Lösung, aber ne einfache... Oder hab ich was vergessen/falsch verstanden?

mfg

Christian

[marabu]

Hallo Daniel,

Zitat:

Zitat von marabu

Ob du den Stack einsetzt oder besser mit anderen Markierungen arbeitest, das hängt zum Teil auch von der Implementierung der Knoten ab.

wie ein einziges unterschlagenes Wort den Sinn entstellen kann. Bei Verwendung eines Stacks hast du bereits einen marking algorithm. Durch meinen Nachtrag wollte ich nur verhindern, dass mein erster Kommentar dich von weiterem Literaturstudium abhält. Grundsätzlich ist der Ansatz über den Stack sehr verbreitet. Andere marking Techniken spielen eher in allgemeinen Graphen eine Rolle.

Grüße vom marabu

[VizeTE]

Zitat:

Zitat von Hawkeye219

ein Versuch(!), der von folgenden Voraussetzungen ausgeht:

1. Jeder Knoten besitzt eine Methode FirstChild, die einen Zeiger auf das erste Kind des Knotens liefert.
2. jeder Knoten besitzt eine Methode NextSibling, die einen Zeiger auf den rechten Bruder des Knotens liefert.
3. Es existiert ein Stack mit den Methoden Push, Pop und IsEmpty.

Punkt 2 gefällt mir nicht so richtig. Wenn ich den Knoten auch zeitgleich in einem anderen Baum verwende kann ich mir nicht den rechten Nachbarn des zweiten Baumes merken.

Daher habe ich mir überlegt, daß auf dem Stack nicht der Knoten selbst abgelegt wird sondern dessen Index. So kann ich, wenn ich den nächsten Nachbarn benötige, einfach den Index + 1 Nachbarn verwenden. (und ggf. Maßnahmen ergreifen falls es den nicht gibt)

Da muß ich dann aber wiederrum höllisch aufpassen, daß nicht während des Vorgangs eine Knoten eingefügt wird, der meinen Index durcheinander bringt. Vielleicht sollte ich doch den Knoten in den Stack schreiben und der Knoten gibt dann seinen aktuellen Index zurück. Wenn der Knoten aber in mehreren Bäumen verwendet wird weiß der Knoten auch wieder nicht welchen Index er zurückgeben soll. Da müßte ich noch einen Bezug zum Kontext herstellen können - man ist das kompliziert :zwinker:

Irgendwo habe ich mal gelesen, daß man dafür sogenannte "robuste Iteratoren" implementieren kann. Der registriert sich beim Baum und bekommt dann Infos wenn ein Knoten eingefügt bzw. gelöscht wird. So kann dann entsprechend auf den verschobenen Index reagiert werden.

Ansonsten entspricht dein Versuch auch etwa meinen Vorstellungen.

[VizeTE]

Zitat:

Zitat von r2c2

Muss es unbedingt n Iterator sein? Reichts vielleicht auch, einfach nur ne rekursive Funktion zu benutzen

Wahrscheinlich würde es auch mit einer Rekursion gehen. Ich wollte aber gern den Code aus dem Baum raushalten. Außerdem gehts mir auch um den Lerneffekt ;)

Zitat:

Zitat von r2c2

Wenn du unbedingt n Iterator haben willst, kannst du das so auch machen

In diese Richtung gingen auch meine ersten Überlegungen. Bei dieser Implementierung gibt es aber das Problem, daß die rekursive Suche abgebrochen wird wenn ein Element gefunden wurde. Du schreibst ja in deinem Code-Beispiel selbst: // Suche abbrechen und Node zurückliefern
Wenn ich jetzt also ein Element gefunden habe, welches meinen Kriterien entspricht und ich dann aber weitersuchen möchte ob es noch mehr davon gibt dann beginnt ja eine neue Rekursion. So kann ich weiter nach unten in den Baum suchen aber beim aufsteigen komme ich dann genau zu meinem Problem. Wo weitermachen wenn das Parent-Element nicht seine Nachbarn kennt?

[VizeTE]

Zitat:

Zitat von marabu

wie ein einziges unterschlagenes Wort den Sinn entstellen kann

Das ist vielleicht sowas wie "der Fluch des Programmierers" ;)
Der Teufel liegt eigentlich immer im Detail.

[Hawkeye219]

Möchtest Du wirklich die Knoten in mehreren Bäumen benutzen oder nur die Daten? Bei einer sauberen Trennung zwischen der Verwaltung (Knoten) und den Daten (mit einem Verweis auf die Daten in den Knoten) sollte es doch möglich sein, die Daten mehrfach zu nutzen. Bei der Verwendung von Interfaces bekommst Du die Referenzzählung sogar umsonst. :wink: Von der mehrfachen Verwendung der Knoten würde ich abraten, weil es meiner Meinung nach die Datenstruktur allzu sehr einschränkt.

Gruß Hawkeye

[VizeTE]

Zitat:

Zitat von Hawkeye219

Möchtest Du wirklich die Knoten in mehreren Bäumen benutzen oder nur die Daten?

Eigentlich nur die Daten.
Ich habe mir die Klassen für die Knoten erstellt und davon meine Daten-Klassen abgeleitet. Vielleicht ist es wirklich flexibler wenn ich diese beiden Dinge voneinander trenne.

[r2c2]

Zitat:

Zitat von VizeTE

Außerdem gehts mir auch um den Lerneffekt ;)

Das is immer gut. :thumb:

Zitat:

Zitat:

Zitat von r2c2

Wenn du unbedingt n Iterator haben willst, kannst du das so auch machen

In diese Richtung gingen auch meine ersten Überlegungen. Bei dieser Implementierung gibt es aber das Problem, daß die rekursive Suche abgebrochen wird wenn ein Element gefunden wurde. Du schreibst ja in deinem Code-Beispiel selbst: // Suche abbrechen und Node zurückliefern
Wenn ich jetzt also ein Element gefunden habe, welches meinen Kriterien entspricht und ich dann aber weitersuchen möchte ob es noch mehr davon gibt dann beginnt ja eine neue Rekursion. So kann ich weiter nach unten in den Baum suchen aber beim aufsteigen komme ich dann genau zu meinem Problem. Wo weitermachen wenn das Parent-Element nicht seine Nachbarn kennt?

Das macht ja mein Trick-17. Indem ich mit die Nummer der des Iterationsknotens merke kann ich durch anhalten davor/danach wieder an die Stelle zurrückkehren und weitermachen. Besonders performant is das nicht; sollte aber funktionieren. Ansonsten werd ich den Thread hier auch weiterverfolgen, da ich auch grad was mit nem Baum anstelle...

mfg

Christian