Freepascal AVLTree, Binären Baum allgemein verstehen?

[Gausi]

Wie Peter schon geschrieben hat, verwendest du vermutlich die falsche Datenstruktur. In einem Binärbaum hat jeder Knoten zwei Nachfolger. Das gilt für eine Verzeichnisstruktur ja in der Regel nicht - hier kann ein Ordner durchaus mehr als zwei Unterordner haben.

Ein AVL-Baum ist ein besonderer Binärbaum. Hier gilt zusätzlich, dass der Baum balanciert ist - d.h. die Teilbäume am linken und rechten Knoten sind gleich hoch bzw. tief (+/- 1). Dadurch ist sichergestellt, dass man in diesem binären Suchbaum (d.h. im linken Knoten sind Elemente enthalten, die kleiner sind als die Wurzel, rechts die, die größer sind) in logarithmischer Zeit ein Element wieder finden kann (oder zum Ergebnis kommt, dass es nicht enthalten ist).

Du kannst natürlich deinen Knoten-Objekten Parents und Childs zuweisen, wie in deinem Codesegment. Aber wenn TAVLTree einen AVL-Baum implementiert, dann wird Tree.Add(Node) all diese Zuweisungen über den Haufen werfen und den Knoten so in den AVL-Baum einfügen, dass der Baum weiter balanciert bleibt. Dafür wird ggf. der gesamte Baum umgebaut - selbst der Wurzelknoten kann danach anders sein. Das mag umständlich klingen, ist aber für den Zweck der Datenstruktur "AVL-Baum" sinnvoll und effizient.

Zum Abbilden einer Verzeichnisstruktur oder anderen hierarchisch organsierten Daten sind allgemeine Baumstrukturen besser geeignet. Dabei wird es dann vermutlich keine direkte Methode Tree.Add geben, weil es dann ja an den Daten liegt, wo sie im Baum eingefügt werden soll. Beim AVL-Baum ist das egal. Hier ist der Zweck in erster Linie, die eingefügten Objekte schnell wiederzufinden. Und zwar in Fällen, in denen häufig Objekte eingefügt und wieder gelöscht werden. Bei eher statischen Situationen könnte man einfach eine sortierte Liste nehmen ...