AVL - Baeume

[Back]    [Listen]   

                                                                   


Georgy Maximovich Adelson- Velsky (b. 8.1. 1922)          Yevgeniy Mikhailovich Landis (6.10.1921 - 12.12.1991)


Adelson - Velsky und Landis, zwei russische Gelehrte schufen 1962 die sogenannten AVL - Bäume. Mittels dieser Bäume war es möglich z.B. Suchalgorithmen bzw. Traversierungen weitaus effizienter als bis dato duchzuführen. Dabei ist die Grundstruktur einem binären Suchbaum ähnlich. Jeder Knoten besitzt maximal 2 Kinder, wobei der vom Wert her kleinere Knoten links steht.
Die AVL - Bäume sind darüber hinaus höhenbalanciert. Dabei gilt für jeden Knoten des Baumes :

Die Tiefe des linken und die Höhe des rechten Teilbaumes unterscheiden sich maximal um den Wert 1.

Um diese Eigenschaft zu erhalten, besteht die Notwendigkeit der Balance des Baumes. Im Wesentlichen unterscheidet man 4 Fälle, bei denen die Notwendigkeit besteht, diese Eigenschaft herzustellen, wobei diese Fälle paarweise symmetrisch sind.

Linksrotation.



Wie in nebenstehendem Bild erkennbar, erfüllt der Baum nach dem Einfügen der 7 oder 9 in den binären Suchbaum die Eigenschaft der Ausgeglichenheit nicht mehr. Er ist rechtslastig. Konkret würde dies bedeuten, die Differenz aus der Höhe des linken und des rechten Teilbaumes beträgt - 2. Mit diesem Wissen ist klar, dass die Balance im rechten Teilbaum verletzt wurde. Es besteht nun die Möglichkeit, dass der rechte Teilbaum nach außen oder nach innen wächst. Im obenstehenden Bild ist erkennbar, dass der Baum nach außen wächst, die Differenz aus Höhe des linken Baumes im rechten Baum und Höhe des rechten Baumes im rechten Baum -1 beträgt. Beide Kriterien bilden ein Gesamtkriterium für eine potenzielle Linksrotation. Bei dieser wird der gesamte Baum nach links gedreht und die 5 an die 4 gefügt.

Rechts - Linksrotation



Auch in diesem Beispiel ergibt die Differenz der Höhen - 2. Allerdings erfolgt das Wachstum, in diesem Fall durch 7 oder 10 veursacht, nach innen. Die entsprechende Untersuchung der Höhe im rechten Teilbaum liefert hier 1. Beide Kriterien sind hier Anlass zur Rechts- Linksrotation. Die einfache Rechtsrotation, bei der eine Drehung um 11 erfolgt und ein einfaches Umhängen der 10 notwendig wird, ist in einem ersten Schritt oben zu sehen. Die folgende Linksrotation um die 9 - mit Umhängen der 7 - liefert den gewünschten ausgeglichenene Baum.

In Haskell sind Rotationsalgorithmen relativ leicht mittels Musteranpassung realisierbar. Die eigentliche Einfügeoperation basiert auf der Untersuchung der oben genannten Kriterien.

Wahl der Rotation zur Schaffung der AVL - Eigenschaft

01 insert x Empty          = N Empty x Empty
02 insert x (N l a r)      | x <  a = mkavl (N (insert x l) a r)
03                         | x >  a = mkavl (N l a (insert x r))
04   
05  mkavl t         |  a ==   2  && b == 1 = lrrot t
06                  |  a == - 2  && c == 1 = rlrot t
07                  |  a ==   2            = rrot t
08                  |  a == - 2            = lrot t
09                  |  otherwise = t
11 
12                     where
13                       a = (hoe (ltree t)) -  (hoe (rtree t))
14                       b = (hoe (rtree (ltree t))  -  (hoe (ltree (ltree t))))
15                       c = (hoe (ltree (rtree t))  -  (hoe (rtree (rtree t))))


Zum Einfügen der Elemente einer Liste in einen Baum bietet sich folgende Methode an.


01   list2tree xs     = l2t (reverse xs)
02                             where l2t []     = Empty
03                                   l2t (x:xs) = insert x (list2tree xs)
 
 
[ Source ]