Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel AVL-Baum aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

AVL-Baum

thumb|right|270px|Ein_AVL-Baum_mit_Balance-Angaben
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\_1$ und $h\_2$ 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 ausgeglichene Bäume 1962 entwickelten
.

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:
:$\backslash operatorname\{bal\}(t)\; =\; H(t\_r)\; -\; H(t\_l)$
: 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: $\backslash operatorname\{bal\}(c)\; \backslash in\; \backslash \{\; -1,0,1\; \backslash \}$

Zu einer gegebenen Höhe entspricht ein B-Baum
Rot-Schwarz-Baum

Referenzen

Literatur

deutsch
* Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen, Stuttgart 2004, ISBN 9783519221210

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

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
* http://herbert.gandraxa.com/herbert/avl.asp Reich kommentierte iterative Implementierung von Herbert Glarner in Linoleum, einem Plattforum-unabhängigen Assembler, englisch
* http://cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html AVL Trees: Tutorial und Implementierung in C++, von Brad Appleton, englisch
* http://home.earthlink.net/~akonshin/delphi_components.htm Implementation in Delphi von Alex Konshin, englisch

       VIDEO-NEWS UND ANGEBOTE