AVL-Baum
aus www.iwiki.de, der freien Wissensdatenbank
Ein AVL-Baum ist eine Datenstruktur in der Informatik, genauer ein balancierter binärer Suchbaum. Dabei gilt: Die Höhen der Teilbäume dieses Knotens unterscheiden sich höchstens um 1. 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 |
Eigenschaften von AVL-Bäumen
1. Die folgenden Operationen benötigen einen Aufwand von höchstens Q (log2(n)):
- Suchen eines Knotens mit gegebenem Schlüssel - Einfügen eines Knotens - Löschen eines Knotens - Finden des K-ten Elements zu gegebenem k
2. Die Höhe eines AVL-Baums liegt zwischen log2(n) und 1.44 * log2(n+1)
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. 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.
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.
Entfernen eines Elementes -> remove
Die remove-Operation sucht, wie die find-Operation, zuerst den Schlüssel 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.
