Baumaufbau

Anleitung

Refaktoriere einen Algorithmus zum Aufbau eines Baums.

Manche Webforen haben ein Baumlayout, sodass Beiträge als Baum dargestellt werden. Allerdings werden die Beiträge in der Regel als unsortierte Menge von Datensätzen in einer Datenbank gespeichert. Wenn man die Beiträge dann den Nutzern zeigt, muss die Baumstruktur rekonstruiert werden.

Deine Aufgabe ist es, ein funktionierendes, aber langsames und hässliches Stück Code zu refaktorieren, das die Logik zum Aufbau eines Baums für stark abstrahierte Datensätze umsetzt. Die Datensätze enthalten nur eine ID-Nummer und eine Eltern-ID-Nummer. Die ID-Nummer liegt immer zwischen 0 (einschließlich) und der Länge der Datensatzliste (ausschließlich). Bei allen Datensätzen ist die Eltern-ID kleiner als die eigene ID, außer beim Wurzel-Datensatz: Dort ist die Eltern-ID gleich der eigenen ID.

Ein Beispielbaum:

root (ID: 0, parent ID: 0)
|-- child1 (ID: 1, parent ID: 0)
|    |-- grandchild1 (ID: 2, parent ID: 1)
|    +-- grandchild2 (ID: 4, parent ID: 1)
+-- child2 (ID: 3, parent ID: 0)
|    +-- grandchild3 (ID: 6, parent ID: 3)
+-- child3 (ID: 5, parent ID: 0)