TypeScript: Effizient Flat-Daten in einen Baum umwandeln

Manchmal stehst du vor der Herausforderung, Flat-Daten in eine Baum-Struktur umzuwandeln. Jeder Flat-Datensatz beinhaltet dabei in der Regel eine Id und eine ParentId wobei letzteres die Id des jeweils übergeordneten Knoten ist. Ist die ParentId null handelt es sich um einen Wurzelknoten.

Zum Beispiel sollst du

[
  {
    "Id": 1,
    "Name": "1",
    "ParentId": null
  },
  {
    "Id": 2,
    "Name": "1 - 1",
    "ParentId": 1
  },
  {
    "Id": 3,
    "Name": "1 - 2",
    "ParentId": 1
  },
  {
    "Id": 4,
    "Name": "1 - 3",
    "ParentId": 1
  },
  {
    "Id": 5,
    "Name": "1 - 2 - 1",
    "ParentId": 3
  }
]

in folgende Struktur umwandeln:

[
  {
    "Id": 1,
    "Name": "1",
    "ParentId": null,
    "Children": [
      {
        "Id": 2,
        "Name": "1 - 1",
        "ParentId": 1,
        "Children": []
      },
      {
        "Id": 3,
        "Name": "1 - 2",
        "ParentId": 1,
        "Children": [
          {
            "Id": 5,
            "Name": "1 - 2 - 1",
            "ParentId": 3,
            "Children": []
          }
        ]
      },
      {
        "Id": 4,
        "Name": "1 - 3",
        "ParentId": 1,
        "Children": []
      }
    ]
  }
]

Der rekursive Ansatz

Der erste Ansatz an den man dabei denkt, wäre folgendes rekursives Konstrukt:

1. Man sucht sich alle Wurzelknoten (ParentId = null) raus und verschiebt diese in ein neues Array.
2. Anschließend iteriert man rekursiv über die restlichen Knoten und prüft, ob die ParentId des aktuellen Knoten der Id einem der Wurzelknoten bzw. deren Kindknoten entspricht.
3. Falls dem so ist, fügt man dem gefundenen Knoten den aktuellen Knoten als Kindknoten hinzu. Falls nicht, schiebt man den Knoten wieder in die Liste zurück.

Ein großer Nachteil:
Wir müssen für jeden Knoten im Worst-Case den kompletten Baum rekursiv runter laufen.

Der Do-While-Shift-Push-Reference-Type Ansatz

Ok, den Namen habe ich mir gerade ausgedacht, gibt aber genau wieder, wie es effizienter und auch sauberer geht.

In JavaScript ist alles was kein primitiver Datentyp ist, ein Objekt. Objekte sind, Reference-Types. Primitive Datentypen sind Value-Types.

Wer den Unterschied nicht kennt:

(Quelle: Internet)

Dieses Verhalten können wir uns zu Nutze machen.

Dass ein Knoten ein Reference-Type sind, ist denke ich klar. Bei dem Children-Property am Knoten handelt es sich um ein Array mit weiteren Knoten. Ein Array ist ebenfalls kein primitiver Datentyp und somit auch ein Reference-Type.

Der Ansatz ist folgender:

1. Man erzeugt ein leeres Array für den tree.
2. Man erzeugt eine leere Map.
3. In einer do-while (oder while je nachdem was du mehr magst 😅) Iterierst du so lange, bis das Datenarray leer ist. In jeder iteration machst du folgendes:
   1. Erzeuge eine leeres array, welches die Kindknoten für den aktuellen Eintrag halten soll.
   2. data.shift() um den nächsten Eintrag aus dem Daten-Array zu holen
   3. Prüfe ob der Eintrag ein Wurzelknoten ist.
      • Falls ja, erzeuge einen Baumknoten und ordne diesem das gerade erzeugte Array als Array für die Kindknoten hinzu. Diesen Baumknoten fügst du in das tree Array ein und legst in der Map einen Eintrag mit der ID des Knoten und den Kindknoten array hinzu.
      • Falls nein und die ParentId in der Map vorhanden ist, wiederhole den vorherigen Schritt mit der Ausnahme, dass du den Baumknoten nicht dem tree Array sondern dem Kindknoten Array aus der Map hinzufügst.
      • Ansonsten machst du ein data.push(node) um den Knoten wieder hinten anzufügen.

Als Code könnte es zum Beispiel so aussehen:

interface FlatNode {
  Id: number;
  Name: string;
  ParentId?: number;
}

interface TreeNode extends FlatNode {
  Children: TreeNode[];
}

const data: FlatNode[] = [
  {Id: 1, Name: '1', ParentId: null},
  {Id: 2, Name: '1 - 1', ParentId: 1},
  {Id: 3, Name: '1 - 2', ParentId: 1},
  {Id: 4, Name: '1 - 3', ParentId: 1},
  {Id: 5, Name: '1 - 2 - 1', ParentId: 3},
];

const tree: TreeNode[] = [];
const childrenMap = {};
let notFoundCounter = 0;

do {
  const next = data.shift();

  const nextChildren = [];
  if (next.ParentId == null) {
    tree.push({...next, Children: nextChildren});
  } else if (next.ParentId in childrenMap) {
    childrenMap[next.ParentId].push({...next, Children: nextChildren});
  } else {
    notFoundCounter++;
    data.push(next);
    continue;
  }

  childrenMap[next.Id] = nextChildren;
  if (notFoundCounter > 0) {
    notFoundCounter--;
  }
} while (data.length > 0 && notFoundCounter < data.length);

Und das wars auch schon 🙂
Da es sich bei der Map lediglich um Referenzen zu den Arrays mit den Kindknoten der jeweiligen Knoten handelt, ist der Overhead an Speicherverbrauch entsprechend gering.

Wer's bequemer haben möchte, kann es natürlich auch noch in eine Funktion packen:

function unflat<T>(data: T[],
                   id: (o: T) => (string | number),
                   parentId: (o: T) => (string | number),
                   childrenPropertyName: string = 'Children',
): (T & any)[] {

  if (!data || data.length <= 0) {
    return [];
  }

  const tree = [];
  const childrenMap = {};

  let notFoundCounter = 0;

  do {
    const current = data.shift();

    const nextChildren = [];
    const currentParentId = parentId(current);

    if (currentParentId == null) {
      tree.push({...current, [childrenPropertyName]: nextChildren});
    } else if (currentParentId in childrenMap) {
      childrenMap[currentParentId].push({...current, [childrenPropertyName]: nextChildren});
    } else {
      notFoundCounter++;
      data.push(current);
      continue;
    }

    childrenMap[id(current)] = nextChildren;
    if (notFoundCounter > 0) {
      notFoundCounter--;
    }
  } while (data.length > 0 && notFoundCounter < data.length);

  return tree;
}

const data: FlatNode[] = [
  {Id: 1, Name: '1', ParentId: null},
  {Id: 2, Name: '1 - 1', ParentId: 1},
  {Id: 3, Name: '1 - 2', ParentId: 1},
  {Id: 4, Name: '1 - 3', ParentId: 1},
  {Id: 5, Name: '1 - 2 - 1', ParentId: 3},
];

const tree = unflat(data, (o) => o.Id, (o) => o.ParentId);
console.log(tree);

Ich finde dieses Beispiel ist ein gutes Beispiel dafür, dass man nicht immer nur auf Algorithmen selber sondern auch auf die Datenhaltung schauen sollte, wenn man schnellen und zugleich verständlichen Code schreiben möchte.

Was hältst du von dem Ansatz? Vorschläge? Alternativen? Ab in die Kommentare damit.