AVLBäume

AVL-Bäume sind eine Klasse selbstbalancierender binärer Suchbäume. Sie wurden 1962 von G. Adelson-Velsky und E. M. Landis eingeführt und tragen ihren Namen. Zentral für AVL-Bäume ist die Balancierung: Die Höhen der linken und rechten Teilbäume eines Knotens unterscheiden sich höchstens um eins. Diese Eigenschaft begrenzt die Baumhöhe auf O(log n) und sorgt dafür, dass Such-, Einfüge- und Löschoperationen im worst-case logarithmisch bleiben.

Jeder Knoten enthält in der Regel einen Schlüssel (und optional einen Wert) sowie Verweise auf linkes und rechtes Kind und eine Höheninformation oder einen Balancefaktor. Der übliche Balancefaktor BF wird definiert als Höhe(linkes Kind) minus Höhe(rechtes Kind) und nimmt die Werte −1, 0 oder 1 an. Nach Einfügungen oder Löschungen kann BF außerhalb dieses Bereichs geraten; dann werden Rotationen eingesetzt, um die Balance wiederherzustellen. Es gibt einfache Rotationen (rechtsrotation bzw. linksrotation) und doppelte Rotationen (Links-Rechts-Rotation und Rechts-Links-Rotation). Die Rotationen erfolgen abhängig vom Balancefaktor des Knotens und des betroffenen Kindes, um BF wieder in die Spannweite zu bringen.

Aufbau der Balancierung erfolgt nach dem BST-Prozess: Nach dem Einfügen oder Löschen werden Höhen aktualisiert und bei Bedarf Rotationen durchgeführt, um BF innerhalb von −1 bis 1 zu halten. Die Wahl der Rotation hängt von BF des betroffenen Knotens und BF des entsprechenden Kindes ab.

Komplexität und Anwendungen: Die worst-case Zeit für Suche, Einfügen und Löschen beträgt O(log n); der Platzbedarf ist O(n). AVL-Bäume finden Anwendung dort, wo eine garantierte logarithmische Tiefe wichtig ist, z. B. in dynamischen In-Memory-Strukturen. In vielen Standardbibliotheken dominieren andere balancierte Bäume (etwa Rot-Schwarz-Bäume) aufgrund Einfachheit, doch AVL-Bäume bleiben eine robuste Alternative, insbesondere bei vielen Updates, die eine strikte Balancierung erfordern.