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

Es gibt wirklich gute Lösungen, die die interne Btree-Darstellung von Sql-Indizes ausnutzen. Dies basiert auf einer großartigen Forschungsarbeit, die um 1998 herum durchgeführt wurde.

Hier ist eine Beispieltabelle (in mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

Die einzigen für die Baumdarstellung erforderlichen Felder sind:

• tw: Der DFS-Index für die Vorordnung von links nach rechts, wobei Root = 1 ist.
• pa: Der Verweis (mit tw) auf den übergeordneten Knoten, Root hat null.
• sz: Die Größe der Verzweigung des Knotens einschließlich seiner selbst.
• nc: wird als syntaktischer Zucker verwendet. Er ist tw+sz und stellt den tw des "nächsten Kindes" des Knotens dar.

Hier ist ein Beispiel für eine Population von 24 Knoten, geordnet nach tw:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

Jedes Baumergebnis kann nicht-rekursiv durchgeführt werden. Zum Beispiel, um eine Liste der Vorfahren des Knotens tw='22' zu erhalten

Vorfahren

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Geschwister und Kinder sind trivial - verwenden Sie einfach pa field ordering by tw.

Nachkommenschaft

Zum Beispiel die Menge (Zweig) der Knoten, die in tw = 17 verwurzelt sind.

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Zusätzliche Hinweise

Diese Methode ist äußerst nützlich, wenn die Zahl der Lesevorgänge die der Einfügungen oder Aktualisierungen weit übersteigt.

Da das Einfügen, Verschieben oder Aktualisieren eines Knotens im Baum eine Anpassung des Baums erfordert, muss die Tabelle gesperrt werden, bevor mit der Aktion begonnen wird.

Die Kosten für das Einfügen/Löschen sind hoch, da der tw-Index und die sz-Werte (Zweiggröße) für alle Knoten nach dem Einfügepunkt bzw. für alle Vorfahren aktualisiert werden müssen.

Beim Verschieben einer Verzweigung wird der tw-Wert der Verzweigung aus dem Bereich verschoben, so dass beim Verschieben einer Verzweigung auch die Fremdschlüssel-Beschränkungen deaktiviert werden müssen. Zum Verschieben einer Verzweigung sind im Wesentlichen vier Abfragen erforderlich:

• Bewegen Sie den Zweig aus der Reichweite.
• Schließen Sie die Lücke, die sie hinterlassen hat. (der verbleibende Baum ist jetzt normalisiert).
• Öffnen Sie die Lücke, in die er gehen soll.
• Bringen Sie den Zweig an seine neue Position.

Baumabfragen anpassen

Das Öffnen/Schließen von Lücken im Baum ist eine wichtige Unterfunktion, die von den Methoden "Erstellen/Aktualisieren/Löschen" verwendet wird, weshalb ich sie hier einfüge.

Wir benötigen zwei Parameter - ein Flag, das angibt, ob wir die Größe verkleinern oder vergrößern, und den tw-Index des Knotens. Zum Beispiel tw=18 (mit einer Zweiggröße von 5). Nehmen wir an, dass wir eine Verkleinerung vornehmen (tw entfernen) - das bedeutet, dass wir in den Aktualisierungen des folgenden Beispiels "-" statt "+" verwenden.

Wir verwenden zunächst eine (leicht abgewandelte) Vorgängerfunktion, um den Wert sz zu aktualisieren.

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

Dann müssen wir den tw für diejenigen anpassen, deren tw höher ist als der zu entfernende Zweig.

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

Dann müssen wir die Eltern für diejenigen anpassen, deren pa's tw höher ist als der zu entfernende Zweig.

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

Answer 2

Nun, wenn ich die Wahl hätte, würde ich Objekte verwenden. Ich würde ein Objekt für jeden Datensatz erstellen, wobei jedes Objekt eine children Sammlung und speichern sie alle in einem assoc-Array (/hashtable), wobei die Id der Schlüssel ist. Und blitz durch die Sammlung einmal, das Hinzufügen der Kinder zu den entsprechenden Kinder Felder. Einfach.

Aber weil Sie keinen Spaß durch die Einschränkung der Verwendung von einigen guten OOP sind, würde ich wahrscheinlich iterate basierend auf:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Bearbeiten: Dies ähnelt einigen anderen Einträgen, aber ich denke, es ist etwas sauberer. Eine Sache, die ich hinzufügen möchte: dies ist extrem SQL-intensiv. Es ist böse . Wenn Sie die Wahl haben, wählen Sie die OOP-Variante.

Answer 3

Dies wurde schnell geschrieben, und ist weder schön noch effizient (plus es autoboxes viel, die Umwandlung zwischen int y Integer ist ärgerlich!), aber es funktioniert.

Es verstößt wahrscheinlich gegen die Regeln, da ich meine eigenen Objekte erstelle, aber hey, ich mache das als Ablenkung von der echten Arbeit :)

Dies setzt auch voraus, dass die Ergebnismenge/Tabelle vollständig in eine Art Struktur eingelesen wird, bevor Sie mit dem Aufbau von Knoten beginnen, was bei Hunderttausenden von Zeilen nicht die beste Lösung wäre.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

Answer 4

Unter der Annahme, dass Sie wissen, dass die Root-Elemente Null sind, folgt hier der Pseudocode für die Ausgabe in Text:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)

for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

Answer 5

Sie können jede andere Datenstruktur mit einem Hashmap emulieren, das ist also keine große Einschränkung. Indem Sie von oben nach unten scannen, erstellen Sie eine Hashmap für jede Zeile der Datenbank, mit einem Eintrag für jede Spalte. Fügen Sie jede dieser Hashmaps zu einer "Master"-Hashmap hinzu, die auf der id verschlüsselt ist. Wenn ein Knoten einen "Elternteil" hat, den Sie noch nicht gesehen haben, erstellen Sie einen Platzhaltereintrag für ihn in der Master-Hashmap und füllen ihn aus, wenn Sie den tatsächlichen Knoten sehen.

Um sie auszudrucken, führen Sie einen einfachen Durchlauf in der Tiefe durch die Daten durch und behalten dabei die Einrückungsebene im Auge. Sie können dies vereinfachen, indem Sie für jede Zeile einen "Kinder"-Eintrag anlegen, den Sie beim Scannen der Daten auffüllen.

Ob es einen "besseren" Weg gibt, einen Baum in einer Datenbank zu speichern, hängt davon ab, wie Sie die Daten verwenden wollen. Ich habe schon Systeme gesehen, die eine bekannte maximale Tiefe hatten und für jede Ebene in der Hierarchie eine andere Tabelle verwendet haben. Das macht durchaus Sinn, wenn die Ebenen im Baum nicht ganz gleichwertig sind (Kategorien der obersten Ebene sind anders als die Blätter).