Freepascal AVLTree, Binären Baum allgemein verstehen?

[peterbelow]

Du benutzt da eventuell die falsche Datenstruktur. Der Zweck eines (binären) Baumes ist es normalerweise, Daten in einer Weise zu organisieren, die es erlaubt, einen Eintrag (Knoten) so schnell wie möglich innerhalb des Baumes zu finden. Dazu muß man jeden Knoten an der richtigen Stelle in der Baumstruktur einfügen, und das erfordert oft sogar eine Reorganisation der existierenden Baumstruktur um den optimalen Aufbau für die Suche zu erhalten. All das sollte in der TAVLTree-Klasse gekapselt sein und die Add-Methode erledigt das Einsortieren. Das heißt:

Du erzeugst ein TMyData-Objekt und setzt seinen Inhalt, dann ein TAvlTreenode-Objekt und setzt dessen Data-Eigenschaft (oder Feld) auf die TMyData-Instanz. Dieses Node-Objekt übergibst Du an tree.Add.
Add sortiert den Node dann ein und setzt dabei dessen Parent, Left und Right-Felder. Das machst nicht Du!

Um einen Knoten zu suchen stellt die TAVLTree-Klasse (die ich nicht kenne) vermutlich eine Find oder Search-Methode zur Verfügung.

Eine solche Baumstruktur ist nicht dazu geeignet, eine existierende hierarchische Struktur (wie ein Festplattenverzeichnis) abzubilden. Dazu brauchst Du sowas wie die interne Struktur des VCL TTreeview. Die Knoten eines solchen "Baums" haben einen Parent-Node und eine Liste/Collection von Child-Nodes. Man kann in einem solchen Baum zwar jede Hierarchieebene sortieren aber das hilft nicht bei der Suche nach einem bestimmten Knoten, es sei denn, man sucht mit Hilfe eines kompletten Pfades. Ansonsten muß man den Baum komplett durchlaufen.

Es gab mal ein wirklich sehr gutes Buch zum Thema von Julian Bucknall: The Tomes of Delphi: Algorithms and Data Structures (ISBN 1-55622-736-1, Wordware Publishing). Google mal nach "Julian Bucknall Algorithm*"...

[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 ...