[Cologne-pm] table zu tree konvertieren

[A. Pagaltzis]

* Michael Lamertz <mike at lamertz.net> [2006-11-16 14:25]:
> Zum Verfahren:
> 
> Du nimmst ein node_id/parent_id Paar in die Hand. Zur node_id
> erzeugst Du ein neues Node-Objekt. Dann laesst Du ein 'find' ab
> der Root-Node auf den Baum los, in dem Du die parent_id suchst.
> Die zurueckgelieferte Referenz auf den Parent-Knoten wird dann
> benutzt, um die neue Node dort einzuhaengen (push
> @{$parent->{children}}, $node).

Hrmf. Wenn du die Grundannahme machst, dass die Liste bereits
dergestalt vorsortiert ist…

> Ich bin jetzt davon ausgegangen, dass Deine Liste derart
> sortiert ist, dass ein Parent existiert, wenn man die
> Child-Node in die Finger bekommt, und die Liste von hinten nach
> vorne durcharbeitet. Falls diese Bedingung in Deinen Daten
> nicht erfuellt ist, musst Du halt vorher ein bisschen
> sortieren...

… dann kann man das in O(n) durchführen, wie Johannes das schon
machen wollte. Dein Ansatz ist dagegen O(n^2) – mithin nicht so
furchtbar prickelnd. Du hast ja bereits von allen Knoten
eindeutige IDs; die ganze Sucherei ist überflüssig, der Kram kann
einfach in einen Hash nach ID.

Gruss,
-- 
Aristoteles Pagaltzis // <http://plasmasturm.org/>