AVL-Baum

Abbildung 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)
Traversieren	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
Tabelle 1: Platz- und Zeit-Komplexitäten

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.

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.

Suchen per Index

Wird in jedem Knoten die Anzahl der Elemente seines Teilbaums gehalten, kann ein Element anhand seines in-order-Index in O(log n) aufgesucht werden.

Da bei unveränderlichen Mengen der Zeigervektor den Zugriff in konstanter Zeit schafft, sind für dieses Zugriffsverfahren nur dynamische Anwendungssituationen interessant, bei denen es vor allem auf die relative Position der Elemente untereinander ankommt.

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 aufgehä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 neue Teilbaum die gleiche Höhe wie vor der Einfügeoperation. Danach ist die Balance des ganzen Baums auch schon in Ordnung.

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 der neue Teilbaum die gleiche Höhe hat wie vor dem Löschen.

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 Schlüssel kann mit einem einzigen Suchvorgang auskommen und kommt so einen Aufwand von O(m+log n).

Rebalancierung

Wenn durch eine Einfüge- bzw. Löschoperation die AVL-Balance zerstört wurde, d. h. ein Höhenunterschied von mehr als $1$ zwischen zwei Bruder-Teilbäumen entstanden ist, ist eine Rebalancierung durchzuführen. Zur besseren Orientierung sei die Wurzel des niedrigeren der beiden Teilbäume (in den Abbildungen 2 und 3 jeweils t₁) als der Angelknoten der Rebalancierung bezeichnet. Zwei Fälle kommen vor, die Einfachrotation und die Doppelrotation. (Obwohl es nur recht wenige Analogien gibt, hat sich die Metapher von der Rotation in der Literatur festgesetzt.) Eine Einfachrotation leistet die Rebalancierung, wenn der innere Sohn (in der Abbildung 2 die Wurzel von t₂₃; in der Abbildung 3 der Knoten Y) des höheren Bruders, d. h. der innere (= nähere) Neffe des Angelknotens, nicht höher ist als sein Bruder, der äußere (= fernere) Neffe. Der andere Fall, bei dem der innere Neffe höher ist, wird von einer Doppelrotation abgedeckt.

Eine Rotation (einfach oder doppelt) ändert nicht die vorhandene in-order-Reihenfolge, auch nicht gegenüber dem Rest des Baums. (Die Kleiner-Zeichen am oberen Rand der Abbildungen 2 und 3 sollen dies verdeutlichen.)

Eine Rotation (einfach oder doppelt) benötigt nur eine konstante Anzahl von Verknüpfungsänderungen an einer konstanten Anzahl von Knoten.

Nach einer Einfügeoperation kann die AVL-Balance des ganzen Baums immer mit 1 (einer) Einfach- oder Doppelrotation wiederhergestellt werden. Nach einer Löschoperation können mehrere Rebalancierungen vom jeweiligen Teilbaum aus bis hinauf zur Wurzel nötig sein, um die AVL-Balance wiederherzustellen.

Einfachrotation

Abbildung 2: Einfachrotation Links(X)

Die nebenstehende Abbildung 2 zeigt eine Einfachrotation. Auf der linken Seite ist ein Höhenunterschied von ${ \color{Red} 2 }$ bei den beiden Teilbäumen von Knoten X dargestellt. Der innere Neffe t₂₃ des Angelknotens t₁ ist nicht höher als sein Bruder, der äußere Neffe t₄. (Eine solche Situation kann z. B. nach einem Einfügen in den Teilbaum t₄ oder nach einem Löschen aus dem Teilbaum t₁ auftreten. Der in der Abbildung blass gehaltene Fall, dass t₂₃ gleich hoch ist wie t₄, kommt nur beim Löschen vor.)

Die Rebalancierung (gezeigt auf der rechten Seite der Abbildung) ändert lokal die Baumstruktur. Dazu werden einzelne Knoten und Teilbäume in der Hierarchie angehoben und andere abgesenkt – senkrechte rote Pfeile in der Abbildung. Bei der gezeigten Rotation nach links wird Knoten Z 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 Z zu X wechselt und Knoten X und Z ihre Position in der Hierarchie tauschen. Im resultierenden Baum ist die Balance wieder hergestellt.

Die Höhe des neuen Baums Z ist nach einer Einfügeoperation gleich wie die von X vor der Operation, während sie nach einer Löschoperation um $1$ vermindert oder unverändert ist, je nachdem ob Z rechtslastig war oder nicht.

Zur dargestellten Rotation nach links wird die gespiegelte Version (mit dem Angelknoten auf der rechten Seite) gleichermaßen benötigt.

Doppelrotation

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

Die in der Abbildung 3 gezeigte Situation unterscheidet sich von der aus Abbildung 2 darin, dass der mittlere Teilbaum (mit Wurzel Y), d. i. der innere Neffe des Angelknotens t₁, 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 Abbildung 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.) Eine Einfachrotation wie in Abbildung 2, die den linken Teilbaum absenkt und dafür den rechten anhebt, löst das Problem nicht, dagegen eine Rechtsrotation gefolgt von einer Linksrotation. Diese Doppelrotation, deren Ergebnis auf der rechten Seite von Abbildung 3 gezeigt ist, teilt den mittleren Teilbaum eine Ebene höher auf an die zwei Väter X und Z, senkt dafür X mit dem linken Teilbaum um eine Ebene ab und hebt Y um zwei Ebenen an, wobei Y neuer Vater von X und Z wird.

Die Höhe des neuen Baums Y ist nach einer Einfügeoperation gleich wie die von X vor der Operation, während sie nach einer Löschoperation um $1$ vermindert ist.

Auch von der Doppelrotation wird die gespiegelte Version benötigt.

Beispiel

Der AVL-Baum in der Abbildung 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 \tfrac12$ (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 der 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 relevant, 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 Knoten auf dem Pfad 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.

Siehe auch

• 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

• Algorithmenvisualisierung u.a. für AVL Bäume
• Ausführlichere Beschreibung mit Delphi-Programm
• Kurz gehaltene Beschreibung der Rotationen
• Animiertes Applet mit Sourcecode und ausführlicher Dokumentation
• Tutorial von Brad Appleton mit Implementierung in C++ (englisch)

• Ben Pfaff „Performance Analysis of BSTs in System Software“ Stanford University, 2004 (englisch)