|
Die älteste und bekannteste Datenstruktur für ausgeglichene Bäume ist der AVL-Baum. Diese Bäume haben die Eigenschaft, daß sich die Höhen der beiden Unterbäume jedes Knotens höchstens um eins unterscheiden. Falls diese Bedingung infolge einer Einfügung verletzt wird, so zeigt es sich, daß sie, unter Verwendung von Rotationen, wiederhergestellt werden kann. Dieser Algorithmus hat den Nachteil, daß erstens eine zusätzliche Schleife für die Rotation benötigt wird, und daß für jeden Knoten auch noch die Länge seiner jeweiligen Unterbäume gespeichert werden muß.
Eine zweite ausgeglichene Baumstruktur ist der 2-3-Baum, bei dem nur 2-Knoten und 3-Knoten zugelassen sind. Es ist möglich, ein Einfügen unter Verwendung einer "zusätzlichen Schleife" zu implementieren, wobei Rotationen wie bei AVL-Bäumen erforderlich sind, doch es ist nicht genügend viel Flexibilität vorhanden, um eine zweckmäßige Top-Down-Variante zu erhalten. Auch hier ist es möglich, daß eine Vereinfachung, unter Zuhilfenahme des Rot-Schwarz-Schemas, erreicht werden kann.
Es gibt auch noch einen anderen wichtigen Typ eines ausgeglichenen Baumes, eine Verallgemeinerung der 2-3-4-Bäume, die B-Bäume genannt werden. Diese gestatten bis zu M Schlüssel pro Knoten, und sie werden häufig für Suchanwendungen, bei denen sehr große Dateien auftreten, verwendet.
|
