Binäre Suchbäume | MathePrisma

so viel wie nötig,
so wenig wie möglich

Jetzt entwickeln wir eine Systematik, wie man mit möglichst wenig Rotationen eine akzeptabel kleine Höhe erreicht.
Dazu lüften wir erst einmal das Geheimnis um die blauen Indizes.

Balance-Index

In jedem Knoten k eines Suchbaumes ist der Balance-Index b(k) definiert durch:
b(k) = Höhe des rechten Teilbaums - Höhe des linken Teilbaums

Der Balance-Index ist also eine ganze Zahl, die positiv, null oder negativ sein kann.

AVL

Wir fordern jetzt eine über die Balance-Indizes erklärte zusätzliche Eigenschaft für einen binären Suchbaum. Nach den 'Erfindern' Adelson-Velskii und Landis nennt man solche Bäume dann 'AVL-Bäume'.

AVL-Baum

Ein binärer Suchbaum heißt AVL-Baum, wenn jeder seiner Knoten AVL-balanciert ist, d. h. wenn für jeden Knoten gilt:

Die Höhe seiner beiden Teilbäume unterscheidet sich um höchstens 1.

der Clou

Bei AVL-Bäumen werden die Operationen

einfügen
löschen

nun so modifiziert, dass (bei geringem Mehraufwand) die AVL-Balance erhalten bleibt.