AVL-Baum

Der AVL-Baum ist eine Datenstruktur in der Informatik, und zwar ein balancierter binärer Suchbaum, bei dem für jeden Knoten die Höhe der beiden Teilbäume höchstens um 1 differiert. Diese Bedingung verhindert – bei einem moderaten Aufwand –, dass der Baum zu sehr aus der Balance gerät, und garantiert bei einer Belegung mit n Schlüsseln eine Höhe in O(log n). In O(log n) ist dann auch die maximale Anzahl der Schritte, um An- oder Abwesenheit eines Schlüssels festzustellen, sowie der maximale Aufwand beim Einfügen, Löschen und Traversieren.

Abb. 1: AVL-Baum mit Balance-Werten (grün)

AVL-Baum
	Komplexität
Platz	O(n)
Operation	im Mittel	Worst case
Suchen	O(log n)	O(log n)
Querschritt	O(1)	O(log n)
Min, Max	O(log n)	O(log n)
Einfügen	O(1)†	O(log n)
Löschen	O(1)†	O(log n)
n  Knoten im Baum †  ohne Navigation
Tab. 1: Platz- und Zeit-Komplexitäten

Der Name AVL leitet sich ab von den Erfindern Adelson-Velski und Landis, die diese Datenstruktur 1962 entwickelten. Der AVL-Baum ist damit die älteste Datenstruktur für balancierte Bäume.

Balance

Als Balance-Wert eines Knotens $t$ in einem Binärbaum bezeichnet man die Höhendifferenz

$\operatorname {bal} (t):=-H(t_{l})+H(t_{r})$,

wobei $H(t)$ die Höhe des Baums $t$, und $t_{l}$ der linke, $t_{r}$ der rechte Teilbaum von $t$ ist.

Ein binärer Suchbaum ist genau dann ein AVL-Baum, wenn stets für alle seine Knoten $t$ das „AVL-Kriterium“

$\operatorname {bal} (t)\in \{-1,0,1\}$

eingehalten wird – es also Vorkehrungen gibt, dass sich die Höhen von 2 Bruder-Teilbäumen um höchstens 1 unterscheiden.

Die Höhe $H(t)$ eines AVL-Baums $t$ mit $n$ Knoten ist beschränkt durch

$\log _{2}(n+1)\leqq H(t)\leqq a\log _{2}(n+2)+b$.

Die obere Schranke kommt vom Fibonacci-Baum, der bei gegebener Höhe einen AVL-Baum mit kleinster Knotenanzahl darstellt, also am schlechtesten balanciert ist. Strebt die Anzahl $n$ seiner Knoten gegen unendlich, so verhält sich seine mittlere Pfadlänge ${\bar {P}}_{n}$ bei Einheits-Zugriffswahrscheinlichkeiten über alle Knoten asymptotisch wie $c\log _{2}n\$.

Ähnlich wie es bei einem unbalancierten binären Suchbaum eine hohe Wahrscheinlichkeit gibt, dass er bei zufälligen Einfügungen eine gewisse Balanciertheit erlangt, ist auch beim AVL-Baum die Wahrscheinlichkeit sehr hoch, dass er besser balanciert herauskommt als seine am schlechtesten balancierte Ausprägung, der Fibonacci-Baum. Wie die Rechnung zeigt, kommt selbst letzterer beim Suchen im Mittel schon auf eine Effizienz, die nur um 4 % von der idealen eines vollständig (höhen-)balancierten Binärbaums abweicht. Wird über alle AVL-Bäume gemittelt, beträgt der Unterschied zum Ideal weniger als 2 %.

Operationen

Zum AVL-Baum gehören die drei Grundoperationen: Suchen, sowie Einfügen und Löschen eines Elements. Die Navigationsoperationen, d. s. die verschiedenen Suchoperationen, das Traversieren, Aufsuchen erstes oder letztes Element u. ä., lassen den Baum unverändert und funktionieren im Prinzip auf jedem binären Suchbaum. Sie liefern alle die Beschreibung einer Position im Baum, die hier – in Anlehnung an die Datenbanken – Cursor genannt sei. Bei anderen, z. B. den modifizierenden, Operationen ist der Cursor die Eingabe und spezifiziert den Einfügepunkt oder den zu löschenden Knoten.

Mit der Eigenschaft, dass alle genannten Operationen im schlechtesten Fall (worst case) die Komplexität O(log n) haben, gehört der AVL-Baum zu den höhen-balancierten binären Suchbäumen.

Suchen

Das Suchen eines Elements ist beim AVL-Baum die wichtigste unter den Navigations-Operationen. Die Höhen-Balancierung versucht, auf diese Operation hin zu optimieren. Sie ermöglicht einen sog. direkten Zugriff (i. Ggs. zum sequenziellen Zugriff der in-order-Traversierung). Sie wird i. d. R. als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.

Der binäre Suchbaum ist jederzeit so sortiert, dass links von jedem Knoten nur Knoten mit kleineren (oder gleichen) Schlüsseln, und rechts nur Knoten mit größeren (oder gleichen) Schlüsseln gespeichert sind. (Damit das funktioniert, muss die vom Benutzer zur Verfügung gestellte Vergleichsfunktion eine Totalordnung (genauer: eine totale Quasiordnung) etablieren. Implizit steckt in ihr auch die Spezifikation des „Schlüssels“.) Man findet also einen Schlüssel, indem man von der Wurzel des Baums ebenenweise nach unten wandert, und dabei jeweils nach links verzweigt, falls der gesuchte Schlüssel kleiner als der des aktuellen Knotens ist, oder rechts, wenn er größer ist. Stimmt ein Schlüssel überein, hat man ihn gefunden; erreicht man ein (Halb-)Blatt (d. h. einen Knoten mit Ausgangsgrad 0 oder 1), dessen Schlüssel nicht übereinstimmt und dem in der geforderten Richtung ein Nachfolger fehlt, ist garantiert, dass der Schlüssel im Baum nicht existiert (s. Suchen duplikatfrei).

Sowohl duplikatfreie als auch Bäume mit Duplikaten (u. U. gleichen Schlüsseln) lassen sich implementieren. (Das ist weniger eine Frage der Vergleichsfunktion als der Anwendungssituation.) Bei letzteren ist eine Suchoperation angebracht, die stets bis zu den (Halb-)Blättern hinab sucht und ermöglicht, ein Element gezielt links vom linkesten (am weitesten links liegenden) bzw. rechts vom rechtesten Duplikat einzufügen. Eine solche Suchoperation ist insbesondere dann interessant, wenn im Suchbaum nicht nur gesucht und gefunden werden soll, sondern auch sequenziell navigiert wird. Ferner erlaubt sie z. B., eine (möglicherweise unbekannte) Vorsortierung in einem Bereich zu retten, wo eine Einordnung nach dem aktuellen Sortiervergleichsschlüssel nur Duplikate produziert. Man nennt ein solches Verhalten „stabil“ (s. Stabilität (Sortierverfahren) mit erklärenden Beispielen). Zur Implementierung bei binären Suchbäumen s. Suchen mit Duplikaten.

Bei allen Varianten ist die Komplexität sowohl im Mittel wie auch im schlechtesten Fall O(log n). Das Sortieren einer Masse von n Elementen durch wiederholtes Suchen und Einfügen kostet O(n log n), also nicht mehr als mit den besten Sortierverfahren.

Traversieren (Iterieren, Enumerieren)

Die in-order-Traversierung (Querung), d. h. das Navigieren sowohl nach links als auch nach rechts zum nächsten Nachbarn in der gegebenen (Sortier-)Folge, ist besonders nützlich, wenn sie als Einzel-Operation vorliegt. So kann der Anwender eine Schleife in gewohnter Manier aufsetzen: Start mit der Suchfunktion (oder dem ersten Element), Iteration mit der Traversierfunktion.

Sie verhält sich im Mittel wie O(1) und im schlechtesten Fall wie O(log n). Eine Traversierung über den ganzen Baum kostet O(n).

Aufsuchen erstes oder letztes Element

Verwandt hiermit ist die Positionierung auf das kleinste oder größte Element im Baum, welche sowohl im Mittel wie auch im schlechtesten Fall O(log n) kostet.

Ein Intervallbegriff (sowohl eigentlich wie uneigentlich) über der total geordneten Menge der Elemente im Baum lässt sich realisieren wie auch eine Art „unscharfe“ Suche, nämlich nach „größer“ oder „kleiner“ (s. binärer Suchbaum (Proximitäts-Suche)), – ebenfalls mit Aufwand O(log n).

Einfügen (Eintragen)

Es sei angenommen, dass die Navigation zum „Einfügepunkt“ bereits erledigt ist. Ein Einfügepunkt ist ganz links oder ganz rechts oder zwischen 2 Knoten, kann also auf jeden Fall durch einen Knoten zusammen mit einer Richtung (links oder rechts) spezifiziert werden. Von 2 Nachbarknoten ist immer einer ein (Halb-)Blatt; dieser Knoten sei – zusammen mit der entsprechenden Richtung – als der unmittelbare Einfügepunkt bezeichnet. Ein solches Paar (Knoten, Richtung) stellt einen Cursor dar; so wird er auch von einer nicht erfolgreichen Suchoperation geliefert.

Der Knoten mit dem neuen Schlüssel wird als Blatt am Einfügepunkt eingehängt. Beim Rücksprung aus der rekursiven Einfüge-Funktion wird geprüft, ob es genügt, den Balance-Wert anzupassen, oder ob der Teilbaum rebalanciert werden muss. Wird der Balance-Wert zu $0$, dann kommen wir von einem Ast, der vorher niedriger war, und die Höhe des betrachteten Teilbaums ändert sich nicht. Wird der Balance-Wert zu $\pm 1$ (er muss vorher $0$ gewesen sein), erhöht sich die Höhe des Teilbaums um 1. Die aufgerufene Funktion teilt dies der aufrufenden mit, die es in die Überprüfung der nächsthöheren Ebene einbezieht. Wird auf einer Ebene der Balance-Wert zu $\pm 2$, muss der Teilbaum rebalanciert werden. Nach einer Rebalancierung hat der Teilbaum an dieser Stelle die gleiche Höhe wie vor der Einfügeoperation, so dass die AVL-Balance des ganzen Baums auch schon wieder in Ordnung ist.

Wird die Wahrscheinlichkeit für die Notwendigkeit, die Balance auf der nächsthöheren Ebene überprüfen zu müssen, als <1 angenommen, dann verhält sich das Einfügen (ohne das Finden der Einfügeposition) im Mittel wie O(1) und im schlechtesten Fall wie O(log n).

Unter der Voraussetzung, dass für die richtige Reihenfolge gesorgt ist, können also m vorsortierte Schlüssel mit Aufwand O(m) und ohne Suchvorgang eingefügt werden.

Löschen (Austragen, Entfernen)

Die Navigation zum zu löschenden Knoten kann z. B. mittels einer Suche erfolgen. Wie beim Binärbaum gezeigt, sind beim Löschen mehr Fälle zu unterscheiden als beim Einfügen. Recht übersichtlich sind die Fälle, wo der zu löschende Knoten ein Blatt oder Halb-Blatt ist. Hat er aber zwei Söhne, dann müssen die beiden frei werdenden Teilbäume neu aufgehängt werden. Dazu wählt man einen der in-order-Nachbarn, also entweder den rechtesten Knoten des linken Teilbaums oder den linkesten des rechten Teilbaums (von den beiden Teilbäumen kann man den evtl. höheren bevorzugen), um die beiden Teilbäume daran wieder aufzuhängen. Der hierfür erforderliche Abstieg geht maximal über O(log n) Stufen und im Mittel über genau eine. Der Knoten nimmt den Platz des gelöschten Knotens ein und muss dabei natürlich selbst aus seinem Herkunftsteilbaum entfernt werden – das ist einfach, da er ein (Halb-)Blatt ist (s. Binärbaum).

Im nun folgenden Rücksprung werden die Balance-Werte überprüft, ggf. adjustiert und nötigenfalls Rebalancierungen durchgeführt. Die rekursiv aufgerufene Funktion teilt ihrem Aufrufer mit, ob sich die Höhe verringert hat, so dass dies in die Überprüfung der nächsthöheren Ebene einbezogen werden kann. Wird der Balance-Wert eines Knotens zu $\pm 1$ (er war vorher $0$), dann ändert sich seine Höhe nicht, und die Überprüfung ist abgeschlossen. Wenn ein Balance-Wert zu $0$ wird, hat sich die Höhe des Teilbaums um 1 verringert und die Überprüfung muss weitergehen. Wird ein Balance-Wert zu $\pm 2$, muss der Teilbaum rebalanciert werden. Nach einer Rebalancierung mit Doppelrotation hat der neue Teilbaum eine um 1 niedrigere Höhe als vor der Löschoperation. Bei einer Einfachrotation kommt es aber auch vor, dass die gleiche Höhe wie vor dem Löschen herauskommt, womit dann der ganze Baum auch schon wieder in AVL-Form ist. Der Begründer dieser Theorie ist Peter Griffin.

Wird die Wahrscheinlichkeit für die Notwendigkeit, die Balance auf der nächsthöheren Ebene überprüfen zu müssen, als <1 angenommen, dann verhält sich das Löschen (ohne das Aufsuchen des zu löschenden Knotens) im Mittel wie O(1) und im schlechtesten Fall wie O(log n).

Das Entfernen eines Intervalls enthaltend m (≪ n) Schlüssel kann mit einem einzigen Suchvorgang auskommen und kommt so auf einen Aufwand von O(m+log n).

Rebalancierung

Wenn bei einer Einfügung bzw. Löschung die AVL-Balance zerstört wird, d. h. ein Höhenunterschied von mehr als $1$ zwischen zwei Bruder-Teilbäumen entsteht, muss (innerhalb der aufgerufenen Operation) eine Rebalancierung durchgeführt werden. Hilfsmittel hierfür sind sog. Rotationen. Zur Abkürzung sei die Wurzel des höheren der beiden Teilbäume (in den Abb.en 2 und 3 jeweils Z) als der „+2-Knoten der Rebalancierung“ bezeichnet.

Zwei Fälle kommen vor: Einfachrotation und Doppelrotation. Eine Einfachrotation leistet die Rebalancierung, wenn der innere Sohn des +2-Knotens Z, d. i. der Sohn mit einer Sohnesrichtung, die der von Z entgegengesetzt ist, (t₂₃ in der Abb. 2 bzw. Y in der Abb. 3) nicht höher ist als sein Bruder, der äußere Sohn. Der andere Fall, bei dem der innere Sohn höher ist, wird von einer Doppelrotation abgedeckt.

Abb. 2: Einfachrotation Links(X)

Rotation in Binärbäumen

Eine einzelne Rotation wird durch die Rotationsrichtung Links oder Rechts (im Bsp. Links) und (jeweils mit Bezug auf die Abb. 2) durch die Wurzel X des betroffenen Teilbaums spezifiziert. Das entspricht der Anhebung eines Knotens (hier: Z). Es geht um folgende Aktionen:

unten:	Einhängen den Teilbaum zwischen Z und seinem Vater X (im Bsp. den linken Sohn t23 von Z) als rechten Sohn bei X. Dieser Teilbaum kann auch fehlen (h=0 in der Abb. 2).
Wippe:	Einhängen X als linken Sohn bei Z.
oben:	Feststellen des Vaters und der Sohnesrichtung von X. Einhängen Z bei seinem Großvater als Sohn dieser Richtung.

Balkenwippe mit Kindern

Alle „Bewegungen“ sind nur „vertikal“ und ändern die vorhandene in-order-Reihenfolge nicht, was auch das senkrechte Raster und die <-Zeichen am oberen Rand der Abb.en verdeutlichen sollen.
Fazit: Eine Rotation „wippt“ eine Kante (hier: X→Z) des Baums in ihre andere Orientierung (Z→X). Damit verbunden sind notwendige Anpassungen an den beiden Endpunkten.

Eine Rotation benötigt nur eine konstante Anzahl von Verknüpfungsänderungen an einer konstanten Anzahl von Knoten. Die diesen Verknüpfungen entsprechenden Kanten sind in den Abb.en doppelt dick gezeichnet.

Einfachrotation

Die nebenstehende Abb. 2 zeigt eine Einfachrotation. In der oberen Hälfte ist ein Höhenunterschied von ${\color {Red}2}$ bei den beiden Teilbäumen von Knoten X dargestellt. Der innere Sohn t₂₃ des +2-Knotens Z ist nicht höher als sein Bruder t₄.
Dies kann nach einem Einfügen in den Teilbaum t₄ oder nach einem Löschen aus dem Teilbaum t₁ auftreten. Der in der Abb. 2 blass gehaltene Fall, dass t₂₃ gleich hoch ist wie t₄, kommt nur beim Löschen vor.

Die Rebalancierung (gezeigt in der unteren Hälfte der Abb.) gelingt durch eine Einfachrotation nach links. Sie ist bereits oben als einzelne Rotation beschrieben. Die anzupassenden 3 Verknüpfungen sind in der Abb. verstärkt gezeichnet.

Die Höhe des neuen Teilbaums Z ist bei einer Einfügung gleich der von X vor der Operation (Einfügung), während sie bei einer Löschung um $1$ vermindert oder unverändert ist, je nachdem ob Z rechtslastig war oder nicht.

Abb. 3: Doppelrotation RechtsLinks(Z, X) = Rechts(Z) dann Links(X)

Doppelrotation

Die in der Abb. 3 gezeigte Situation unterscheidet sich von der in Abb. 2 darin, dass der mittlere Teilbaum (mit Wurzel Y), d. i. der innere Sohn des +2-Knotens Z, höher ist als sein Bruder t₄.
Das kann nach einer Einfügung in einen der Teilbäume t₂ oder t₃ oder nach einer Löschung aus dem Teilbaum t₁ passieren. Der in der Abb. 3 in Standardfarbe gehaltene Fall, bei dem t₂ gleich hoch ist wie t₃, kommt nur beim Löschen vor, während die 2 höhenungleichen Fälle (genau ein Teilbaum blass) sowohl beim Einfügen wie beim Löschen vorkommen. Der vierte Fall (zweimal blass) bedarf keiner Rebalancierung.

Die Doppelrotation, deren Ergebnis im unteren Drittel der Abb. 3 gezeigt ist, ist eine Rechtsrotation durch Z gefolgt von einer Linksrotation durch X. Sie entspricht der zweimaligen Anhebung des höheren (und inneren) Sohnes Y des +2-Knotens Z.

Die anzupassenden 5 Verknüpfungen sind in der Abb. verstärkt gezeichnet.

Die Höhe des neuen Teilbaums Y ist bei einer Einfügung gleich wie die von X vor der Operation (Einfügung), während sie sich bei einer Löschung um $1$ vermindert.

Beispiel

Der AVL-Baum in der Abb. 1 wird

• nach der Löschung des Knotens G durch 2 Einfachrotationen Rechts(F), später Links(J)
• nach der Einfügung eines Knotens T durch die Doppelrotation RechtsLinks(V, P)

rebalanciert.

Implementierung

Zusätzlich zum Bedarf des binären Suchbaums muss in einem Knoten der Balance-Wert mit seinen 3 Möglichkeiten untergebracht werden: macht 2 Bits.

Nach jedem Einfügen oder Löschen eines Knotens wird in allen seinen Vorfahren der Balance-Wert überprüft, berichtigt und ggf. auf AVL-Niveau gebracht. Erreicht man eine Ebene, bei der sich die Höhe des betroffenen Teilbaums nicht mehr ändert, ist die Operation abgeschlossen. Die Anpassungs- und Reparatur-Welle hat pro Ebene einen Dämpfungsfaktor von $\approx {\tfrac {1}{2}}$ (gemäß der Annahme, dass etwa die Hälfte der Knoten ausgewogen ist, die andere Hälfte nicht), so dass die Summe der Aufwände für Einfügung und Überprüfung sowie für Löschung und Überprüfung jeweils im Mittel konstant ist.

Da eine Rotation auch durch die Wurzel gehen kann, wird eine zusätzliche Datenstruktur benötigt, die den Baum repräsentiert und die hier Anker genannt sei. Sie enthält den Zeiger zur Wurzel und ist auf diese Weise Vater der Wurzel und Bestandteil der Datenstruktur AVL-Baum.

Iterative Programmierung

Der Anwender hat Vorteile davon, wenn der Programmierer die vom Aufschreiben her eleganten Rekursionen durch simple Iterationen ersetzt, da dadurch zunächst einmal der Speicherbedarf für den Programm-Stapelspeicher konstant gehalten werden kann. Für das Aufbewahren des Rückwegs zur Wurzel, der bei der rekursiven Programmierung meist im Programmstapelspeicher steckt, muss dann ein anderes, explizites Konstrukt gewählt werden, wie es der Cursor eines ist. Er kann sowohl als Einfügepunkt, zur Kennzeichnung des Löschkandidaten wie auch als Navigationsvehikel beim Traversieren dienen. Dadurch wird eine Trennung der modifizierenden Operationen von der Navigation möglich.

Trennung der Navigation von den modifizierenden Operationen

Einfüge- und Löschfunktion sind sinnvollerweise von der Suchfunktion zu trennen bei:

• Einsatz zusätzlicher Navigationsfunktionen, z. B. einer in-order-Traversierung
• Datenstrukturen, die mehrere Zugriffspfade besitzen, z. B. mehrere AVL-Strukturen

Vom Vorhandensein zusätzlicher Zugriffspfade hängt es auch ab, ob es genügt, den Stapel der Vorfahren im Cursor zu halten, oder ob ein Zeiger auf den Vater in jedem Knoten gebraucht wird – somit der Cursor nur aus Knotenzeiger und Richtung besteht.

Diese Modularisierung der Navigations- von den modifizierenden Operationen ist Voraussetzung für den im Mittel unterlogarithmischen (konstanten) Aufwand der letzteren, der in Anwendungssituationen mit starkem sequenziellem Anteil zu Buche schlagen kann.

Cursor

Die Größe und Komplexität des Cursors hängt entscheidend davon ab, ob der AVL-Knoten einen Zeiger zum Vaterknoten enthält oder nicht.

1. Zeiger zum Vaterknoten vorhanden:
   Das Paar (Knoten, Richtung) stellt einen vollwertigen Cursor dar.
   Mit dem prozentualen Aufschlag auf den Speicherbedarf erkauft man sich auf jeden Fall eine prozentuale Einsparung an Laufzeit, da der Stapel der Vorfahren immer schon vorliegt.
2. Zeiger zum Vaterknoten nicht vorhanden:
   Zusätzlich zum Paar (Knoten, Richtung) muss der Pfad vom Knoten zum Anker im Cursor gehalten werden mit einer Länge in O(log n).

Anwendung mit mehreren AVL-Zugriffspfaden

Als Beispiel für eine Anwendung mit 2 Zugriffspfaden sei ein klassisches Speichermanagement gebracht. Elemente der Datenstruktur sind die freien Blöcke mit den Attributen (Feldern) Größe und Ort. Für beide Felder gebe es je eine Suchstruktur. Beim Akquirieren wird ein Block von Mindestgröße gesucht, ausgetragen und ein evtl. Rest wieder eingetragen. Bei der Speicherrückgabe wird nach Ort gesucht, auf Konfliktfreiheit mit den Nachbarblöcken geprüft (ebenfalls ein Beispiel für die Nützlichkeit der Einzel-Traversierung) und der zurückzugebende Block ggf. mit diesen verschmolzen. Alle Veränderungen müssen auf beiden Suchstrukturen durchgezogen werden. Enthalten die Datenstrukturen auch den Zeiger zum Vaterknoten, dann erspart das Hangeln von der einen Suchstruktur zur anderen einen Suchvorgang.

Parallelisierung

Bei iterativer Programmierung kann man die Anpassungs- und Reparaturschleife auch in der umgekehrten Richtung, d. h. von der Wurzel zum Blatt, durchlaufen. Das ist insbesondere dann interessant, wenn auf den Baum hochgradig parallel (konkurrent) zugegriffen werden soll. Z. B. würde in einem Szenario „Suchen und Einfügen“ die Suchfunktion sich den tiefsten (letzten) unausgewogenen Knoten auf dem Pfad merken, ab dort den Baum sperren und die Vergleichsergebnisse aufbewahren. Zum Fertigstellen der Einfügeoperation müsste dann der gesperrte Vorfahr (ggf. nach einer Rebalancierung) auf ausgewogen und alle seine Nachfahren bis zum Blatt auf die den eingeschlagenen Richtungen entsprechenden Balance-Werte gesetzt werden. Der Vorteil wäre, dass alle Knoten außerhalb des gesperrten Teilbaums von den anderen Prozessorkernen gleichzeitig mit der laufenden Einfügung konsistent besichtigt und auch verändert werden könnten.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen mit anderen Suchalgorithmen sind zu finden bspw. bei Ben Pfaff.

Weitere Bäume

• Binärbaum
• Binärer Suchbaum
• Balancierter Baum
• Rot-Schwarz-Baum
• Splay-Baum
• Gewichteter binärer Suchbaum

Literatur

• Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen. Stuttgart 2004, ISBN 9783519221210.
• Udi Manber: Introduction to Algorithms – A Creative Approach. 1989, Kapitel 4.3.4, S.75ff, Addison-Wesley Publishing Company.

Weblinks

Commons: AVL-Bäume – Sammlung von Bildern, Videos und Audiodateien

• Algorithmenvisualisierung u. a. für AVL-Bäume
• Kurz gehaltene Beschreibung der Rotationen
• Animiertes Applet mit Sourcecode und ausführlicher Dokumentation
• Tutorial von Brad Appleton mit Implementierung in C++ (englisch)
• Stanford University: Ben Pfaff „Performance Analysis of BSTs in System Software“, 2004 (englisch, PDF, 309 KiB)