Tree aus Datenbank füllen - wie vorgehen?

[Grolle]

Hallo,

ich versuche einen Tree aus einer Datenbank zu laden, aber irgendwie finde ich nicht die richtige Lösung. Die Tabelle sieht so aus:

Zitat:

id | parent_id | name

Der Quelltext bisher (nach einigen fehlerhaften Versuchen:

Delphi-Quellcode:

  with searchQuery do
  begin
    SQL.Clear;
    SQL.Text := 'SELECT * FROM icstree ORDER BY parent ASC;';
    Open;
    while not eof do
    begin
      if FieldByName('parent').AsInteger = 0 then //oberste Ebene anhängen
      begin
        tmpNode := main.icstree.Items.AddObject(nil,FieldByName('name').AsString,Pointer(FieldByName('id').AsInteger));
      end
      else
      begin


      end;
...

Hat jemand einen Hinweis bzw. eine Best Practice, wie ich da weitermache?

Viele Grüße ...

[Medium]

Ich würd's anders herum machen.

Nodes wie sie hereinkommen in eine Liste werfen. Kommt ein Node, zwei Dinge tun:
1) Falls der Node einen Parent hat: Alle bestehenden Nodes absuchen, ob da dieser Parent bei ist (nicht vergessen die gesamten Teilbäume mit abzusuchen). Ist der Parent schon da, den neuen Node da dran hängen, ansonsten hinten an die Liste kleben.
2) Alle "First-Level"-Nodes durchsuchen (also diesmal nur die tatsächlich in der Liste stehenden, nicht was hinten dran ist), und schauen ob da welche den eben eingefügten als Parent haben. Diese dann an den neuen Node anhängen und aus der Liste löschen (damit wandert der ggf. daran hängende Teilbaum ja gleich mit).

Hat den Vorteil, dass du nur ein Mal durch die DB musst, und auch nicht nachträglich zusammenfügen o.ä. musst. Ausserdem entdeckst du evtl. auch noch fehler, wenn nämlich die Liste nachher >1 lang ist, sind Nodes ohne gültigen Parent in der DB

Die Suchoperation bei 2) lässt sich gut durch Sortierthalten der Liste optimieren, da dann z.B. mit Binary Serach gesucht werden kann. Bei 1) geht das nur, wenn sicher ist dass alle children des Nodes N eine kleinere ID als der Node N+1 in der sortierten Liste haben. (Was alles ohnehin nur bei Bäumen mit ein paar tausend Nodes merkbare Unterschiede machen sollte.)

[Medium]

Noch eine bessere Idee! (Ich mach's bewusst nicht als Edit, da du grad online bist und es sonst ggf. nicht siehst.)

Folgendes funktioniert, wenn sicher gestellt ist, dass eine ID immer > seines Parent's ID ist:

Einfach alle erstmal in eine Liste werfen, aufsteigend nach ID sortiert. Dann immer den hintersten Node nehmen, und die Liste nach seinem Parent durchsuchen (ist ja sortiert, geht fix). Node an den Parent, raus aus der Liste. Neuen letzten Node nehmen, und immer so weiter bis nur noch der Root-Node über ist. Das spart das quasi-lineare traversieren der Teilbäume aus meinem vorigen Vorschlag!
Nur klappt das nicht, wenn eine Parent-ID > Node ist, da dieser Parent ja schon zuvor irgendwo angehängt wurde, und nicht mehr auf erster Ebene der Liste liegt -> man müsste wieder die Teilbäume absuchen.

[Grolle]

Hi,

Zitat von Medium:

Folgendes funktioniert, wenn sicher gestellt ist, dass eine ID immer > seines Parent's ID ist:

das ist nur in der oberen Ebene nicht so. Die Knoten haben immer eine 0 als parent_id.

Viele Grüße ...

[Medium]

Öhm wie jetzt? Alle Knoten haben den Parent 0? Dann ist das doch implizit nur eine Liste... ich versteh nicht ganz was du sagen willst glaub ich.

[Grolle]

Äh ne, ich mein natürlich nur die Knoten in der obersten Ebene haben die parent_id 0 (weil haben ja keinen parent Knoten). Bin heute verbal etwas daneben

[Medium]

Da gibt's mehrere von? Dann stehen in der Tabelle also quasi mehrere Bäume?

Edit: Wenn ja, dann ist das für das genannte Verfahren aber egal, da diese ja keinem mehr untergeordnet werden müssen. Und desen eigene ID sollte ja auch >0 sein, also größer iherer quasi-Parent-ID. Hab ich das nu richtig? Bin auch nicht mehr der wacheste...

[alzaimar]

Falls Du die Tabelle noch erweitern kannst, würde ich in jedem Fall noch die Eigenschaften 'Level' und 'Rank' einführen.
'Level' bezeichnet die Ebene des Knotens (0=Wurzel, 1=1.Ebene, 2=2.Ebene usw.)
'Rank' die Reihenfolge eines Knotens im Zweig. Die ist für das hier beschriebene Verfahren zwar nicht nötig, ich würde sie aber i.a. trotzdem mit angeben, wenn die Reihenfolge eine Rolle spielt.

'Level' erleichtert Dir das Einlesen in einen Baum und 'Rank' stellt die Reihenfolge der Knoten im Zweig sicher.

Dann liest Du die Tabelle ein, sortierst nach Level und Rank und gehst so vor (Pseudocode):

Delphi-Quellcode:

Query.SQL.Text := 'Select ParentID, Level, Rank, ID, Data From Tree Order by Level, Rank';
// Alternativ unsortiert einlesen und in-Memory sortieren, um den SQL-Server zu entlasten
// Geht bei einer TADOTable über die IndexFieldNames-Eigenschaft.
Query.Active := True;
While not Query.Eof Do Begin
// Suche Eltern-Knoten. Da wir nach Level sortieren, ist der garantiert schon angelegt.
// Der Microsoft-Tree definiert NIL als Wurzelknoten, sodaß eine Suche nach der Wurzel-ID
// hier fehlschlägt bzw. NIL liefert, was aber auch ok ist.
  ParentNode := Tree.FindNodeByID(Query['ParentID']); 

// Lege neuen Baumknoten an
  Node := TTreeNode.Create(Query['ID'], Query['Data']);
// Und hänge ihn an den Eltern-Knoten. Hier vielleicht eine Fallunterscheidung zwischen
// ParentNode=NIL (Wurzelknoten) und anderen Knoten
  Tree.AddNode (ParentNode, Node);
// Nächsten Datensatz einlesen
  Query.Next
End;

Der Bottleneck ist hier die Suche nach dem Elternknoten, der aber durch Verwendung z.B. einer Hashmap drastisch verkürzt werden kann.

Vorteil ggü. Mediums Variante: Kommt ohne Liste aus und ist einfacher umzusetzen.
Nachteil ggü. Mediums Variante: Es wird ein weiteres Feld ('Level') benötigt. Allerdings ist so eine Level-Information manchmal sehr brauchbar, wenn nämliche die Ebene selbst eine Information darstellt.
Beispiel: Mitarbeiterhierarchie (Chef->Werksleiter->Abteilungsleiter...)
Dann findet man sehr schnell z.B. alle Werksleiter ('Level=2').

Natürlich sollte man auf diese Variante verzichten, wenn Teilbäume frei herumgeschoben werden dürfen und die Änderungen direkt in der DB vorgenommen werden sollen. Denn dann müssten auch alle Level neu durchnummeriert werden, wenn ein Teilbaum verschoben wird.

Ich würde erst festlegen, ob die hier vorgeschlagenen Zusatzinformationen wichtig sind und dann das Verfahren wählen. Wenn Du also die Ebeneninformation brauchst, nimm meine Variante, ansonsten die vom Medium.

Wenn man eine Liste/Queue verwenden darf, dann ruhig rekursiv:

Delphi-Quellcode:

Procedure CreateTree (Tree : TTree; Elements : TList);
Begin
// Einfach jedes Element in den Baum eintragen
   While not Elements.IsEmpty Do
    InsertNode(Tree, Elements, Elements.Items[0]);
End;

Function InsertNode (Tree: TTree; Elements: TList; Element : TElement) : TTreeNode;
Begin
  If Element=Nil Then
    Result := RootNode
  Else Begin
    Result := TTreeNode.Create(Element);
    Elements.Remove (Element);
// Erstmal den Elternknoten finden
    ParentNode := Tree.FindNodeByID (Element.ParentID); // Hier wieder optimieren
// Wenn es noch keinen gibt, dann eben den erst anlegen (rekursiv)
    If ParentNode=Nil Then 
      ParentNode := InsertNode (Tree, Elements, Elements.FindElementByID (Element.ParentID));
// Knoten an Elternknoten hängen. Wenn ParentNode=Nil, an die Wurzel hängen
      Tree.AddNode (ParentNode, Result);
    End;
  End
End;

Kurz und knapp. Fix sollte das auch sein.

[haentschman]

Hallo Grolle...

wenn du nicht unbedingt lernen möchtest wie das zu Fuß funktioniert, könntest du dir den JvDBTreeView von den Jedis anschauen. Deine Tabellenstruktur entspricht schon den "Vorgaben" die nötig sind. Das bedeutet Einlesen... und fertsch

[Grolle]

Danke für eure Antworten . Das werde ich heute Abend mal in Ruhe durchgehen.