AVL-Baeume

AVL wurden in den 60er Jahren von Adelson-Velskii und Landis entwickelt. AVL-Baeume waren die ersten dynamisch ausbalancierten Baeume, die vorgeschlagen wurden. AVL-Baeume sind Binaerbaeume mit folgenden Eigenschaften:

1. Die Hoehe der Unterbaeume eines beliebigen Knoten unterscheidet sich maximal um ``Eins''.
2. Jeder Unterbaum eines beliebigen Knoten ist wieder ein AVL-Baum.

Von Adelson-Velskii und Landis wurde folgende Definition von Ausbalanciertheit eines Baumes vorgeschlagen:

Definition 3.1a: Ein Knoten eines binaeren Baumes heisst ausgeglichen oder balanciert, wenn sich die Hoehen seiner beiden Unterbaeume um hoechstens ``Eins'' unterscheiden.

Alle AVL-Baeume haben deshalb folgende Eigenschaft:

Die Operationen Entnehmen, Einfuegen, Loeschen ist auch in einer dynamischen Umgebung stets mit einem Zeitaufwand von O(log n) durchfuehrbar.

Da auch andere Baeume existieren, fuer die die Operationen Entnehmen, Einfuegen, Loeschen mit einem Zeitaufwand von O(log n) durchfuehrbar sind, moechten wir ab sofort folgende Definition anstelle der Definition 3.1a benutzen:

Definition 3.1b: Ein Knoten eines binaeren Baumes heisst ausgeglichen oder balanciert, wenn die Operationen Einfuegen, Loeschen und Entnehmen alle stets in O(logn) Zeit durchfuehrbar sind. [Booth][Cormen]

Definition 3.2: Ein binaerer Baum heisst ausgeglichen, wenn alle seine Knoten ausgeglichen sind. [Cormen]