AVL-Baum

aus Wikipedia, der freien Enzyklopädie

Ein AVL-Baum ist eine Datenstruktur in der Informatik, genauer ein balancierter binärer Suchbaum. Als Invariante beim AVL-Baum gilt, dass sich für jeden Knoten k die Höhen h₁ und h₂ der beiden Teilbäume um höchstens 1 unterscheiden. Da diese Bedingung verhindert, dass der Baum aus der Balance gerät, nennt man ihn auch „ausgeglichen“. Die Höhe eines AVL-Baums mit n Knoten liegt in O(log n) und damit auch die maximale Anzahl der Schritte, um ein Element zu finden oder festzustellen, dass es nicht enthalten ist.

Der Name AVL leitet sich von den Erfindern Adelson-Velsky und Landis ab, die diese älteste Datenstruktur für ausgeglichende Bäume 1962 entwickelten.

Inhaltsverzeichnis 1 Balance 2 Operationen 2.1 Suchen eines Elementes find 2.2 Einfügen eines Elementes insert 2.3 Entfernen eines Elementes remove 3 Rebalancierung 3.1 Einfache Rotation 3.2 Doppelrotation 4 Implementierung 5 Siehe auch 6 Literatur 7 Weblinks

[Bearbeiten] Balance

Ein Binärbaum heißt vollständig ausgeglichen oder AVL-Baum, wenn sich für jeden seiner Teilbäume die Höhen des linken und rechten Astes höchstens um 1 unterscheiden (definiere dazu die Höhe des leeren Baumes als 0). Die Berechnung der Balance eines Knotens erfolgt dann folgendermaßen:

wobei t ein beliebiger Knoten im AVL-Baum ist und H(t_r) die Höhe des rechten Teilbaumes des Knotens t bezeichnet, H(t_l) analog die des linken Teilbaumes.

Ein binärer Suchbaum B ist genau dann ein AVL-Baum, wenn für alle Teilbäume c von B gilt:

Zu einer gegebenen Höhe entspricht ein Fibonacci-Baum einem AVL-Baum mit minimaler Knotenanzahl, er ist also am schlechtesten ausgeglichen.

[Bearbeiten] Operationen

Beim AVL-Baum gibt es drei Grundoperationen, das Suchen eines Elements, das den Baum unverändert lässt, sowie das Einfügen und das Löschen eines Elements. Wesentliche Eigenschaft des AVL-Baums ist, dass alle drei Operationen im schlechtesten Fall die Komplexität O(log n) haben.

[Bearbeiten] Suchen eines Elementes find

Die find-Operation ist im AVL-Baum die einfachste aller Operationen, und wird als grundlegende Operation in der insert-Operation als auch in der remove-Operation gebraucht. Daher wird sie hier zuerst diskutiert. Da der Suchbaum jederzeit so sortiert ist, dass rechts eines Knotens nur Knoten mit größeren Schlüsseln, und links vom Knoten nur Knoten mit kleineren (oder gleich großen) Schlüsseln gespeichert sind, findet man einen Schlüssel, indem man von der Wurzel des Baumes schrittweise nach unten wandert, und dabei jeweils nach rechts abbiegt, falls der gesuchte Schlüssel größer als der des aktuellen Knotens ist oder links wenn er kleiner ist. Stimmt der Schlüssel überein, hat man ihn gefunden, erreicht man ein Blatt, dessen Schlüssel nicht passt, ist garantiert, dass der Schlüssel nicht im Baum existiert.

[Bearbeiten] Einfügen eines Elementes insert

Die insert-Operation versucht zuerst den Schlüssel mit der find-Operation zu finden. Scheitert dies, so ist das passende Blatt bekannt, das jetzt zum Knoten wird. An diesem wird der neue Schlüssel als Blatt aufgehängt. Beim Rücksprung aus der rekursiven find-Funktion wird geprüft, ob der Baum rebalanciert werden muss, und dies ggf. durchgeführt (s.u.).

[Bearbeiten] Entfernen eines Elementes remove

Die remove-Operation sucht zuerst den Schlüssel wie die find-Operation und entfernt dann den entsprechenden Knoten. War es ein Blatt, geht es im Rücksprung des Rekursivaufrufs mit dem Rebalancieren weiter (s.u.), sonst müssen die beiden frei gewordenen Teilbäume neu aufgehängt werden. Dies wird realisiert, indem entweder das am weitesten links liegende Blatt des rechten Teilbaums oder das am weitesten rechts liegende Blatt des linken Teilbaums dazu benutzt wird, die beiden Teilbäume daran wieder aufzuhängen. Das Blatt nimmt den Platz des gelöschten Knotens ein. Im nun folgenden Rücksprung werden die ggf. nötigen Rebalancierungen durchgeführt.

[Bearbeiten] Rebalancierung

Wurde durch eine Einfüge- bzw. Löschoperation die Balance zerstört, wird zusätzlich eine Rebalancierung durchgeführt. Dabei wird zwischen zwei Fällen unterschieden, der einfachen Rotation und der Doppelrotation.

Eine einfache Rotation ist immer dann notwendig, wenn sich durch das Einfügen oder Löschen eines Elementes ein Höhenunterschied von mehr als 1 an einem der beiden äußersten Teilbäume eines Zweiges eines AVL-Baumes ergibt. Hingegen ist eine Doppelrotation notwendig, wenn der Höhenunterschied an inneren Teilbäumen auftritt.

[Bearbeiten] Einfache Rotation

Die nebenstehende Abbildung zeigt eine einfache Rotation. Auf der linken Seite ergibt sich nach einer Einfügung ein Höhenunterschied von zwei bei den beiden Teilbäumen von Knoten x. Da dieser Baum nicht mehr balanciert wäre, muss eine Rebalancierung durchgeführt werden. Das Ergebnis dieser Operation ist auf der rechten Seite der Abbildung gezeigt.

Die Rebalancierung ändert lokal die Baumstruktur unter Beibehaltung der Sortierungsbedingung. Dazu werden einzelne Knoten und Teilbäume in der Hierarchie angehoben und andere abgesenkt. Dies ist in der Abbildung durch senkrechte rote Pfeile dargestellt. Obwohl bei der Rebalancierung keine Seitwärtsverschiebung stattfindet, wird diese Operation als Rotation bezeichnet. Bei der gezeigten Rotation nach links (gegen den Uhrzeigersinn) wird Knoten y und Teilbaum t₃ um eine Ebene erhöht und Knoten x und Teilbaum t₁ um eine abgesenkt. Die Verknüpfungen werden entsprechend angepasst, so dass Teilbaum t₂ seinen Vaterknoten von y zu x wechselt und Knoten x und y ihre Position in der Hierarchie tauschen. Im resultierenden Baum ist die Balance wieder hergestellt. Zur dargestellten Rotation nach links, die den Teilbaum links außen absenkt und dafür den Teilbaum rechts außen erhöht, existiert eine spiegelbildliche Variante, die in einer Rotation nach rechts den linken Teilbaum erhöht und dafür den rechten absenkt.

[Bearbeiten] Doppelrotation

Die in Abbildung 2 gezeigte Situation unterscheidet sich von der aus Abbildung 1 darin, dass die problematische Höhendifferenz zwischen dem linken Teilbaum t₁ und dem mittleren Teilbaum (mit Wurzel z) auftritt. Daher kann eine einfache Rotation wie in Abbildung 1, die den linken Teilbaum absenkt und dafür den rechten anhebt, keine Abhilfe schaffen. Die Doppelrotation, deren Ergebnis auf der rechten Seite von Abbildung 2 gezeigt ist, hebt den mittleren Teilbaum um zwei Ebenen an und senkt dafür den linken um eine Ebene ab. Dazu wird der Wurzelknoten z des mittleren Teilbaumes um zwei Ebenen erhöht und wird neuer Vaterknoten von x und y. Die dadurch entstehenden freien Teilbäume t₂ und t₃ werden an die Knoten x und y aufgeteilt. Auch bei der sog. Doppelrotation geschehen keine Seitwärtsverschiebungen, wodurch die Sortierreihenfolge der Knoten im AVL-Baum erhalten bleibt. Auch von der Doppelrotation existiert eine spiegelbildliche Variante, die ebenfalls den mittleren Teilbaum erhöht, dafür aber den rechten absenkt.

Nach einer Einfügung kann die Balance immer mit einer Rotationsoperation wiederhergestellt werden. Nach einer Löschoperation können mehrere Rebalancierungen vom jeweiligen Teilbaum aus bis hinauf zur Wurzel notwendig sein, um die Balance wiederherzustellen.

[Bearbeiten] Implementierung

Jeder Knoten des Baums muss neben dem Schlüssel einen Balance-Wert speichern, der angibt ob der Baum links- oder rechtslastig ist. Der Balancegrad eines Knotens k berechnet sich aus („Höhe des rechten Teilbaums“) − („Höhe des linken Teilbaums“). Er beträgt 0, wenn der Knoten ausgeglichen ist (also linker und rechter Teilbaum gleich tief sind); er ist positiv, wenn der rechte Teilbaum tiefer als der Linke ist und negativ, wenn der Linke tiefer als der Rechte ist. Bei einem Balance-Wert größer 1 oder kleiner −1 ist eine Rotation erforderlich.

Nach jedem Einfügen oder Löschen eines Knotens wird in allen seinen Vorgängern bis zur Wurzel der Balance-Wert angepasst und die Balancierung überprüft. Dies geschieht auf dem „Rückweg“ der rekursiven Aufruffolge, was einen separaten Prüf- und Korrekturlauf überflüssig macht. Eine Rotation benötigt nur eine konstante Anzahl von Verknüpfungsänderungen am betreffenden Knoten, seinem Vorgänger und den beiden Nachfolgern.

[Bearbeiten] Siehe auch

• B-Baum
• Rot-Schwarz-Baum

[Bearbeiten] Literatur

deutsch

• Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen, Stuttgart 2004, ISBN 3519221217

englisch

• Udi Manber: Introduction to Algorithms – A Creative Approach, 1989, Kapitel 4.3.4, S.75ff, Addison-Wesley Publishing Company

[Bearbeiten] Weblinks

• http://www.informatiktreff.de/materialien/sek_ii/algorithmen/avl/avlbaum.htm Ausführlichere Beschreibung
• http://alfi.ira.uka.de/lehre/sommer2002/AVLTreeApplet/avl.html Java Applet zum Durchspielen verschiedener Szenarien
• http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node60.html Gute kurzgehaltene Beschreibung
• http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm Noch ein Java Applet mit Animation
• http://fbim.fh-regensburg.de/~saj39122/bruhi/index.html Ein hübsches animiertes Applet mit Sourcecode und ausführlicher Dokumentation
• http://j-algo.binaervarianz.de/download.php Programm zur anschaulichen Visualisierung