Was ist der effizienteste/elegante Weg, um eine flache Tabelle in einen Baum zu parsen?

Question

Angenommen, Sie haben eine flache Tabelle, die eine geordnete Baumhierarchie speichert:

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

Hier ist ein Diagramm, in dem wir Folgendes haben [id] Name . Der Wurzelknoten 0 ist fiktiv.

                       \[0\] ROOT
                          /    \\ 
              \[1\] Node 1          \[3\] Node 2
              /       \\                   \\
    \[2\] Node 1.1     \[6\] Node 1.2      \[5\] Node 2.1
          /          
 \[4\] Node 1.1.1

Welchen minimalistischen Ansatz würden Sie verwenden, um das in HTML (oder Text, was das betrifft) als korrekt geordneten, korrekt eingerückten Baum auszugeben?

Nehmen wir weiter an, Sie haben nur einfache Datenstrukturen (Arrays und Hashmaps), keine ausgefallenen Objekte mit Parent-Children-Referenzen, kein ORM, kein Framework, nur Ihre beiden Hände. Die Tabelle wird als Ergebnismenge dargestellt, auf die nach dem Zufallsprinzip zugegriffen werden kann.

Pseudocode oder einfaches Englisch ist in Ordnung, dies ist eine rein konzeptionelle Frage.

Bonusfrage: Gibt es eine grundsätzlich bessere Möglichkeit, eine Baumstruktur wie diese in einem RDBMS zu speichern?

---

BEARBEITUNGEN UND ERGÄNZUNGEN

Um die Frage eines Kommentators ( Mark Bessey ) Frage: Ein Root-Knoten ist nicht notwendig, da er ohnehin nie angezeigt wird. ParentId = 0 ist die Konvention, um auszudrücken, dass dies die oberste Ebene ist. Die Spalte Order definiert, wie Knoten mit demselben Parent sortiert werden sollen.

Die "Ergebnismenge", von der ich sprach, kann man sich als ein Array von Hashmaps vorstellen (um in dieser Terminologie zu bleiben). In meinem Beispiel sollte sie bereits vorhanden sein. Einige Antworten gehen die extra Meile und konstruieren es zuerst, aber das ist okay.

Der Baum kann beliebig tief sein. Jeder Knoten kann N Kinder haben. Ich hatte allerdings nicht unbedingt einen Baum mit "Millionen von Einträgen" im Sinn.

Verstehen Sie meine Wahl der Knotenbenennung ("Knoten 1.1.1") nicht als etwas, auf das Sie sich verlassen können. Die Knoten könnten genauso gut "Frank" oder "Bob" heißen, es wird keine Namensstruktur impliziert, dies diente lediglich der besseren Lesbarkeit.

Ich habe meine eigene Lösung gepostet, damit ihr sie in Stücke reißen könnt.

Answer 1

Wenn verschachtelte Hash-Maps oder Arrays erstellt werden können, kann ich einfach die Tabelle von Anfang an durchgehen und jedes Element dem verschachtelten Array hinzufügen. Ich muss jede Zeile bis zum Wurzelknoten zurückverfolgen, um zu wissen, in welche Ebene des verschachtelten Arrays ich einfügen muss. Ich kann die Memoisierung verwenden, so dass ich nicht immer wieder nach demselben übergeordneten Element suchen muss.

Bearbeiten: Ich würde die gesamte Tabelle in ein Array zuerst lesen, so dass es nicht die DB wiederholt abfragen. Natürlich wird dies nicht praktisch sein, wenn Ihre Tabelle sehr groß ist.

Nachdem die Struktur aufgebaut ist, muss ich sie zunächst in der Tiefe durchgehen und den HTML-Code ausdrucken.

Grundsätzlich gibt es keine bessere Möglichkeit, diese Informationen in einer Tabelle zu speichern (ich könnte mich allerdings irren ;) und würde mich freuen, wenn es eine bessere Lösung gäbe). Wenn Sie jedoch ein Schema erstellen, um dynamisch erstellte DB-Tabellen zu verwenden, dann haben Sie eine ganz neue Welt eröffnet, allerdings auf Kosten der Einfachheit und mit dem Risiko der SQL-Hölle ;).

Answer 2

Um Bills SQL-Lösung zu erweitern, können Sie im Grunde dasselbe mit einem flachen Array tun. Wenn die Strings alle die gleiche Länge haben und die maximale Anzahl der Kinder bekannt ist (z.B. in einem binären Baum), kann man das mit einem einzigen String (Character Array) machen. Wenn Sie eine beliebige Anzahl von Kindern haben, wird die Sache etwas komplizierter... Ich müsste in meinen alten Notizen nachsehen, was man tun kann.

Dann, opfern ein bisschen Speicher, vor allem, wenn Ihr Baum ist spärlich und / oder unbalanced, können Sie, mit ein bisschen Index Mathematik, Zugriff auf alle Zeichenfolgen zufällig durch Speichern Ihrer Baum, Breite zuerst in das Array wie so (für einen binären Baum):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

Sie kennen die Länge Ihrer Saite, Sie kennen sie

Ich bin jetzt bei der Arbeit, kann also nicht viel Zeit damit verbringen, aber bei Interesse kann ich ein bisschen Code holen, um dies zu tun.

Wir verwenden es, um in binären Bäumen aus DNA-Codons zu suchen, ein Prozess baute den Baum auf, dann flachten wir ihn ab, um nach Textmustern zu suchen, und wenn wir sie gefunden haben, erhalten wir durch Indexmathematik (umgekehrt von oben) den Knoten zurück... sehr schnell und effizient, obwohl unser Baum selten leere Knoten hatte, aber wir konnten im Handumdrehen Gigabytes von Daten durchsuchen.

Answer 3

Wenn die Elemente, wie in Ihrem Beispiel, in einer Baumstruktur angeordnet sind, können Sie etwas wie das folgende Python-Beispiel verwenden:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

Dabei wird ein Stapel verwaltet, der die aktuelle Position in der Baumstruktur darstellt. Für jedes Element in der Tabelle werden die Stack-Elemente ausgeklappt (und die entsprechenden Divs geschlossen), bis das übergeordnete Element des aktuellen Elements gefunden wird. Dann wird der Anfang dieses Knotens ausgegeben und in den Stapel verschoben.

Wenn Sie den Baum nicht mit verschachtelten Elementen, sondern mit Einrückungen ausgeben wollen, können Sie die print-Anweisungen zum Drucken der divs einfach überspringen und vor jedem Element eine Anzahl von Leerzeichen ausgeben, die einem Vielfachen der Größe des Stapels entspricht. Zum Beispiel, in Python:

print "  " * len(stack)

Sie können diese Methode auch leicht verwenden, um eine Reihe von verschachtelten Listen oder Wörterbüchern zu erstellen.

Edit: Ihrer Klarstellung entnehme ich, dass die Namen nicht als Knotenpfade gedacht waren. Das deutet auf einen alternativen Ansatz hin:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

Dies konstruiert einen Baum aus Arrays von Tupeln(!). idx[0] steht für die Wurzel(n) des Baums. Jedes Element in einem Array ist ein 2-Tupel, das aus dem Knoten selbst und einer Liste aller seiner Kinder besteht. Sobald der Baum aufgebaut ist, können Sie idx[0] behalten und idx verwerfen, es sei denn, Sie wollen auf die Knoten über ihre ID zugreifen.

Answer 4

Denken Sie über den Einsatz von Nosql-Tools wie neo4j für hierarchische Strukturen nach. Eine vernetzte Anwendung wie Linkedin verwendet z. B. Couchbase (eine weitere Nosql-Lösung).

Verwenden Sie nosql jedoch nur für Abfragen auf Data-Mart-Ebene und nicht zum Speichern und Verwalten von Transaktionen.