AVL-Baum

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 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.^{[Ref 1]} Diese Forderung 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.^{[Ref 2]} Damit ist der AVL-Baum die älteste Datenstruktur für balancierte Bäume.

Balance [Bearbeiten]

Als den Balance-Wert^{[Ref 3]} eines Knotens^{[Anm 1]} $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.^{[Anm 2]}

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^{[Ref 4]}

$\log_2 (n + 1) \leqq H(t) \leqq a \log_2 (n + 2) + b$ .^{[Anm 3]}

Die untere Schranke kommt vom vollständig balancierten Binärbaum; die obere 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 \$ ^{[Anm 4]}.

Ähnlich wie es bei einem unbalancierten binären Suchbaum eine hohe Wahrscheinlichkeit gibt, dass er bei zufälligen Einfügungen eine gewisse Balanciertheit erlangt,^{[Ref 5]} 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 balancierten Binärbaums abweicht. Wird über alle AVL-Bäume oder alle Einfügereihenfolgen gemittelt, beträgt der Unterschied zum Ideal weniger als 2 %.

Operationen [Bearbeiten]

Die wichtigsten Operationen bei den Suchbäumen – und damit beim AVL-Baum – sind: Suchen einerseits, sowie Einfügen und Löschen andererseits. 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.

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 [Bearbeiten]

Das Suchen eines Elements oder Schlüssels ist die wichtigste unter den Navigations-Operationen. Die Höhen-Balancierung des AVL-Baums 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. In der Vergleichsfunktion steckt 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. i. ein 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). Das Ergebnis der Suchfunktion ist dann der zuletzt aufgesuchte Knoten zusammen mit der zuletzt untersuchten Richtung.

Sowohl duplikatfreie als auch Bäume mit Duplikaten (u. U. gleichen Schlüsseln) lassen sich implementieren. (Das ist weniger eine Frage der Vergleichsfunktion als eine der Anwendung.) Bei letzteren ist eine Suchfunktion angebracht, die stets bis zu den (Halb-)Blättern hinab sucht und ermöglicht, ein Element gezielt je nach Anwendungssituation entweder links vom linkesten (am weitesten links liegenden) oder rechts vom rechtesten Duplikat einzufügen. Mit einer solchen Suchfunktion kann die existierende Reihenfolge von Elementen mit gleichem Schlüssel bewahrt (oder eben auch umgedreht) werden. Ist sie bspw. zusammen mit der Einfügefunktion Teil eines Sortieralgorithmus, dann wird dieser „stabil“ (s. Stabilität (Sortierverfahren) mit erklärenden Beispielen). Zur Implementierung 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) [Bearbeiten]

Die in-order-Traversierung, d. h. das Navigieren sowohl nach links wie nach rechts zum nächsten Nachbarn in der gegebenen (Sortier-)Folge, ist besonders nützlich, wenn sie als Einzel-Operation, als Querschritt, 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).^{[Anm 5]}

Aufsuchen erstes oder letztes Element [Bearbeiten]

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) [Bearbeiten]

Es sei angenommen, dass die Navigation zum Einfügepunkt bereits erfolgt 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 (auf den Raum zwischen ihnen bezogen) immer genau einer ein (Halb-)Blatt; dieser Knoten sei – zusammen mit der entsprechenden Richtung – als der unmittelbare Einfügepunkt bezeichnet; 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 ±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 ±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)^{[Anm 6]} und im schlechtesten Fall wie O(log n).

Unter der Voraussetzung, dass für die richtige Reihenfolge gesorgt ist, kostet das Einfügen von m vorsortierten Schlüsseln nur den Aufwand O(m).

Löschen (Austragen, Entfernen) [Bearbeiten]

Die Navigation zum zu löschenden Knoten kann mittels einer Suche, aber auch durch einen Querschritt erfolgen. Beim Löschen sind mehr Fälle zu unterscheiden als beim Einfügen (s. a. Binärbaum). Einfach sind die Fälle, wo der zu löschende Knoten ein (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 ±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 ±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 der ganze Baum auch schon wieder in AVL-Form 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 Löschen (ohne das Aufsuchen des zu löschenden Knotens) im Mittel wie O(1)^{[Anm 7]} 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(log(n)+m).^{[Anm 8]}

Rebalancierung [Bearbeiten]

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 Funktion) eine Rebalancierung durchgeführt werden. Geeignete Reparaturwerkzeuge sind die sog. Rotationen.

Zwei Fälle kommen vor: Einfachrotation und Doppelrotation. Eine Einfachrotation leistet die Rebalancierung, wenn der innere Sohn des um 2 höheren Bruders (Z in den zwei Abbildungen 2 und 3), d. i. der Sohn mit einer Sohnesrichtung, die der von Z entgegengesetzt ist, (t₂₃ in der Abbildung 2 bzw. Y in der Abbildung 3) nicht höher ist als sein Bruder, der äußere Sohn (t₄ in beiden Abbildungen). Dieser Fall wird in der Literatur als Rechts-Rechts- (resp. gespiegelt Links-Links-)Situation bezeichnet, da X rechts- und Z nicht linkslastig ist, d. h. die zwei Balance-Werte 2 und 1 (beim Löschen auch 0) sind, kurz: die Balance zweimal hintereinander die gleiche Richtung hat. Der andere Fall, bei dem der innere Sohn höher ist, wird von einer Doppelrotation abgedeckt – in der Literatur Rechts-Links- (resp. Links-Rechts-)Situation genannt, da X rechts- und Z linkslastig ist, d. h. die zwei Balance-Werte 2 und –1 sind, kurz: die Balance die Richtung wechselt.

Abb. 2: Einfachrotation Links(X)

Rotation in Binärbäumen [Bearbeiten]

Eine einzelne Rotation lässt sich durch die Rotationsrichtung Links oder Rechts und durch die Wurzel des betroffenen Teilbaums spezifizieren, z. B. Links(X) (wir beziehen uns in diesem Abschnitt auf die Abbildung 2). Sie bewirkt die Anhebung eines Knotens (hier: Z). Insgesamt geht es um die folgenden 3 Aktionen:

unten:	Einhängen des zwischen Z und seinem Vater X befindlichen Teilbaums (hier: des linken Sohns t₂₃ von Z) als (hier: rechten) Sohn bei X.^{[Anm 9]}
Wippe:	Einhängen von X als (hier: linken) Sohn bei Z.
oben:	Feststellen des Vaters (er sei V genannt) und der Sohnesrichtung von X bei V. Einhängen von Z bei V als Sohn dieser Richtung.^{[Anm 10]}

Balkenwippe mit Kindern

Kurz: Eine Rotation „wippt“ eine Kante (hier: X→Z) des Baums in ihre andere Orientierung (Z→X).^{[Anm 11]} Dazu kommen die notwendigen Anpassungen an den beiden inzidenten Knoten (hier: X und Z).

Die Schlüssel bewegen sich bei diesen „Rotationen“ nur vertikal (innerhalb der senkrechten Raster). Die in-order-Reihenfolge der Knoten bleibt also vollkommen erhalten.

Eine Rotation beinhaltet nur eine konstante Anzahl von Verknüpfungsänderungen an einer konstanten Anzahl von Knoten.

Einfachrotation [Bearbeiten]

Die nebenstehende Abbildung 2 zeigt eine Rechts-Rechts-Situation. In der oberen Hälfte haben die beiden Teilbäume Z und t₁ des Knotens X einen Höhenunterschied von 2. Der innere Sohn t₂₃ des um 2 höheren 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 Abbildung 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 Abbildung) gelingt durch eine Einfachrotation nach links. Sie ist bereits oben als einzelne Rotation beschrieben. Die anzupassenden 3 Verknüpfungen sind in der Abbildung verstärkt gezeichnet.

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

Die gespiegelte, die Links-Links-Situation wird von einer Einfachrotation nach rechts behandelt.

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

Doppelrotation [Bearbeiten]

Die in der Abbildung 3 gezeigte Situation unterscheidet sich von der in Abbildung 2 darin, dass der mittlere Teilbaum (mit Wurzel Y), d. i. der innere Sohn des um 2 höheren Knotens Z, höher ist als sein Bruder t₄ – eine Rechts-Links-Situation, da X rechts- und Z linkslastig ist.
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 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 Abbildung 3 gezeigt ist, ist eine Rechtsrotation durch Z (gegen die Linkslastigkeit von Z, mittleres Drittel) gefolgt von einer Linksrotation durch X (gegen die Rechtslastigkeit von X). Sie bewirkt eine zweimalige Anhebung des höheren (und inneren) Sohnes Y von Z.

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

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

Bei einer Links-Rechts-Situation wird die gespiegelte Version, d. h. eine Linksrotation gefolgt von einer Rechtsrotation, benötigt.

Beispiel [Bearbeiten]

Der AVL-Baum in der Abbildung 1 wird

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

rebalanciert.

Implementierung [Bearbeiten]

Zusätzlich zum Bedarf des binären Suchbaums muss in einem Knoten der Balance-Wert mit seinen 3 Werten untergebracht werden: macht 2 Bits.^{[Anm 12]}

Kopf [Bearbeiten]

Da die Wurzel einer Löschung oder einer Rotation anheim fallen, somit den Baum nicht repräsentieren kann, muss diese Rolle von einer anderen Datenstruktur übernommen werden, die in der Literatur Kopf^{[Ref 6]} genannt wird. Sie enthält den Zeiger zur Wurzel und fungiert als eine Art Vater der Wurzel.

Iterative Programmierung [Bearbeiten]

Der Anwender hat Vorteile davon, wenn der Programmierer die vom Aufschreiben her eleganten Rekursionen durch simple Iterationen ersetzt, da dadurch O(log n) Prozeduraufrufe und -rücksprünge eingespart werden und der Speicherbedarf für den Programm-Stapelspeicher konstant gehalten wird. Für das Aufbewahren des Rückwegs zu Wurzel und Kopf, der bei der rekursiven Programmierung neben anderem im Programmstapelspeicher steckt, muss dann ein anderes, explizites Konstrukt gewählt werden, welches sich im Cursor (s. u.) subsumieren lässt. Dadurch wird eine Trennung der modifizierenden Operationen von der Navigation möglich.

Trennung der navigierenden von den modifizierenden Operationen [Bearbeiten]

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

Einsatz spezieller Navigationsfunktionen, z. B. in-order-Traversierung oder duplikat-transparentes Suchen;
Datenstrukturen, die mehrere Zugriffspfade besitzen, z. B. mehrere AVL-Strukturen.

Diese Modularisierung der Navigations- von den modifizierenden Operationen stellt den im Mittel unterlogarithmischen (sprich: konstanten) Aufwand der letzteren frei. In Anwendungen mit starkem sequenziellem Anteil kann sich das positiv auf die Laufzeit auswirken.

Cursor [Bearbeiten]

Beim Suchen wird ein Paar (Knoten, Richtung) erzeugt, welches geeignet ist, beim Einfügen den Einfügepunkt zu spezifizieren. Beim Löschen wird der zu löschende Knoten durch die Komponente Knoten bezeichnet, und die Komponente Richtung kann als Kennzeichnung eines Folgeknotens nach der Löschung verwendet werden. Und beim Traversieren gibt Knoten den Ausgangspunkt und Richtung die gewünschte Richtung der Navigation an. Damit benötigen alle wichtigen Funktionen ein Konstrukt, das (in Analogie z. B. zu den Datenbanken) Cursor genannt wird.^{[Ref 7]}

Die Größe und Komplexität des Cursors hängt entscheidend davon ab, ob die AVL-Knoten einen Zeiger zum Vater enthalten oder nicht.

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 Rückweg zu Wurzel und Kopf immer schon gesichert ist.
Wird die Wurzel durch ein besonderes Bit gekennzeichnet, dann kommen die meisten Funktionen ohne separate Angabe des Kopfes aus, da sie erkennen können, wann ein Vaterknoten zum Kopf wird.
Zeiger zum Vaterknoten nicht vorhanden:
Zusätzlich zum Paar (Knoten, Richtung) muss der Pfad vom Knoten zu Wurzel und Kopf im Cursor gehalten werden mit einer Länge in O(log n).^{[Anm 13]}
Es kostet sowohl bei der Einfüge- wie bei der Löschfunktion nur sehr wenige zusätzliche Maschinenbefehle, um den Eingabepfad in einen bei der Ausgabe gültigen Pfad zu transformieren. Benötigt die Anwendung allerdings gleichzeitig mehrere Cursor für ein und denselben Suchbaum und über eine Modifikation des Baumes hinweg, dann kann das Aufrechterhalten der Konsistenz dieser zusätzlichen Cursor leicht so aufwändig werden, dass es wirtschaftlicher ist, allen Knoten einen Zeiger zum Vaterknoten zu spendieren.

Beispiel einer Anwendung mit mehreren AVL-Zugriffspfaden [Bearbeiten]

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 Querschritts) 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 [Bearbeiten]

Wird iterativ programmiert, dann kann die Anpassungs- und Reparaturschleife auch in der umgekehrten Richtung, d. h. von Kopf und Wurzel zum Blatt, durchlaufen werden. 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^{[Anm 14]} 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 parallel zur laufenden Einfügung konsistent besichtigt und auch verändert werden könnten.

Laufzeitmessungen [Bearbeiten]

Realistische Anwendungssituationen mit Performancedaten und -vergleichen mit anderen Suchalgorithmen finden sich bei Ben Pfaff. Seine Ergebnisse zeigen in 79 Messungen u. a. die sehr große Ähnlichkeit von AVL-Bäumen (AVL) und Rot-Schwarz-Bäumen (RB) mit Laufzeitverhältnissen RB:AVL zwischen 0,929 und 1,476 bei einem Median von ≈1,056 und einem geometrischen Mittelwert von ≈1,098.

Anmerkungen [Bearbeiten]

↑ Da einem Knoten in umkehrbar eindeutiger Weise der von ihm gewurzelte maximale Unterbaum, „sein“ Teilbaum, zugeordnet werden kann, sollen der Kürze halber Eigenschaften wie Höhe, Balance, Vater-Sohn- und Bruder-Beziehung usw. einem Knoten und einem solchen Teilbaum in gleicher Weise zukommen.
Gleichzeitig fungiert ein Knoten, z. B. beim Umhängen eines Teilbaums, als dessen „Henkel“.
↑ Es spielt zwar für die Höhendifferenz keine Rolle, dennoch wird hier – wie auch sonst häufig bei gewurzelten Bäumen – dem leeren oder fehlenden Baum die Höhe 0 gegeben, einem Blatt die Höhe 1 und einem höheren Baum die Höhe 1+Höhe seines höchsten Unterbaums. Gezählt werden also die Ebenen der Knoten.
↑ mit $a:=\tfrac{1}{\log_2 \Phi} \approx 1{,}440420$ , $b:=\tfrac{a}{2} \log_2 5 -2 \approx -0{,}327724$ und $\Phi:=\tfrac{1+\sqrt 5}{2} \approx 1{,}618034$ (Zahl des goldenen Schnitts)
↑ mit $c := \tfrac{a \Phi}{\sqrt 5} \approx 1{,}042298$
↑ Jeder Bogen des Baums wird genau einmal absteigend und einmal aufsteigend besucht.

↑ Sei $G$ die Anzahl der Knoten, die nicht Blätter sind und die zwei Teilbäume gleicher Höhe haben, und $U$ die Anzahl der Knoten mit ungleich hohen Teilbäumen, dann ist $u:=\tfrac{U}{G+U}\in{[{0,1}]}$ der Anteil der unausgewogenen. Nur die Fibonacci-Bäume und die anderen dünnsten AVL-Bäume erreichen exakt $\scriptstyle u\,=\,1$ . Dagegen kommen nur die vollständig höhenbalancierten Binärbäume mit Knotenzahl $\scriptstyle 2^h-1$ auf exakt $\scriptstyle u\,=\,0$ . Ferner sei angenommen, dass der gespiegelte Baum gleich häufig vorkommt wie das Original.
Wir gehen rekursiv von folgender Situation aus: Bei einer Einfügung habe sich ergeben, dass die Höhe des Teilbaums, in dem die Einfügung stattfand, um 1 zugenommen hat. Beim Aufstieg zum Vaterknoten stellen wir fest, von welcher Seite wir kommen. Wir nehmen an: von rechts (das passt zu den Abbildungen 2 und 3; die gespiegelte Alternative führt überdies zu denselben Werten). Wir überprüfen die Lage im Vaterknoten und haben die folgenden Fälle zu unterscheiden:

$\operatorname{bal}$ vor Einfügung		Häufigkeit	$\operatorname{bal}$ nach Einfügung	Rebalan- cierung erforderlich	$\operatorname{bal}$ da- nach	Teilbaum wird höher um	Nächste Ebene zu überprüfen
–1	links höher	$u/2$	0	Nein		0	Nein
0	ausgewogen	$1-u$	1	Nein		1	Ja
1	rechts höher	$u/2$	2	Ja	0	0	Nein
Tab. 2: Nach dem Einfügen: Die neuen Balance-Werte in Abhängigkeit von den alten

Die Wahrscheinlichkeit, bei einer Einfügung ausgehend von einer Ebene die nächsthöhere überprüfen zu müssen, ist also $q:=1-u$ . Die Wahrscheinlichkeit, dass wenigstens $n$ Ebenen überprüft werden müssen, ist $q^n$ und, dass genau $n$ Ebenen überprüft werden müssen, ist $q^n-q^{n+1}=(1-q)q^n$ . Die Anzahl der zu überprüfenden Ebenen summiert sich dann im Mittel auf

$\begin{align}(1-q)(q+2q^2+3q^3+...)\;&=\;q+q^2+q^3+...\;\\&=\;\tfrac{q}{1-q}\;=\;\tfrac{1-u}{1-(1-u)}\;=\;\tfrac{1-u}{u}\end{align}$ ,

was bei dem plausiblen $u\approx \tfrac12$ ergibt, dass im Mittel etwa eine weitere Ebene überprüft werden muss.

↑ Über den Anteil der unausgewogenen Knoten seien dieselben Annahmen wie bei der Einfügung gemacht.
Folgende Situation sei rekursiv angenommen: Nach einer Löschung habe sich die Höhe des Teilbaums, in dem die Löschung stattfand, um 1 vermindert. Ferner handele es sich o. B. d. A. um einen linken Teilbaum. Wir überprüfen nun die Lage im Vaterknoten dieses Teilbaums und unterscheiden die folgenden Fälle:

$\operatorname{bal}$ vor Löschung		Häufigkeit		$\operatorname{bal}$ nach Löschung	Rebalan- cierung erforderlich	$\operatorname{bal}$ da- nach	Teilbaum wird nied- riger um	Nächste Ebene zu überprüfen
–1	links höher	$u/2$		0	Nein		1	Ja
0	ausgewogen	$1-u$		1	Nein		0	Nein
1	rechts höher	$\frac{u}{2}$	$\tfrac{u}{2}(1-u)$	2	Ja	1	0 ¹	Nein
			$\tfrac{u}{2}(\tfrac{u}{2}+\tfrac{u}{2})$			0	1 ²	Ja
¹ Die vorletzte Zeile bezieht sich auf den Fall der Einfachrotation mit gleich hohen Söhnen ² und die letzte auf Rotationen mit nicht gleich hohen Söhnen, d. h. Doppelrotation (linker Sohn höher) oder Einfachrotation mit dem rechten Sohn höher.
Tab. 3: Nach dem Löschen: Die neuen Balance-Werte in Abhängigkeit von den alten

Bei einer Löschung ergibt sich eine Wahrscheinlichkeit von weniger als $u$ für das Erfordernis, die nächsthöhere Ebene überprüfen zu müssen. Die Anzahl der zu überprüfenden Ebenen summiert sich dann im Mittel auf weniger als $\tfrac{u}{1-u}$ , was beim plausiblen $u\approx \tfrac12$ bedeutet, dass im Mittel weniger als $\approx 1$ Ebene eines Niveaus ≥ 2 überprüft werden muss.

↑ Dabei verhalten sich Sequenzen, die am linkesten oder rechtesten Knoten beginnen, besonders günstig, da diese Knoten selbst (Halb-)Blätter sind und der einzige Nachbar entweder Sohn oder Vater ist. Letzterer ist auch der einzige Knoten, der sowohl als Ersatz- wie als Nachfolgeknoten in Frage kommt. Wenn die Massenlöschung an einem Knoten mit zwei Söhnen beginnt und in eine vorgegebene Richtung fortschreiten soll, nimmt man am besten als Ersatzknoten den Nachbarn in der Gegenrichtung und als Nachfolgeknoten den Nachbarn in der vorgegebenen Richtung, der dann ein (Halb-)Blatt ist.
↑ t₂₃ kann leer sein, was dem Fall h=0 in der Abbildung 2 entspricht.
↑ Ist Z die Wurzel, dann ist V der „Kopf“ (s. den Abschnitt Kopf) und Z bei V als neue Wurzel einzuhängen.
↑ Solcherart als Spiegelung der Orientierung einer Kante aufgefasst, ist eine Binärbaumrotation eine Involution.
↑ 1 Bit, wenn bei den Söhnen aufgezeichnet, mit der Bedeutung: „Knoten ist höher“ als Bruder.

↑ Als eine Datenstruktur, die im homogenen Arbeitsspeicher (Hauptspeicher) untergebracht ist, ist der AVL-Baum durch die Größe desselben beschränkt. Dadurch ergeben sich auch Beschränkungen für die Pfadlänge. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten 8-Bit-Byte-Adressen.

Länge eines Zeigers in Bit	maximale Anzahl adressierbarer Bytes	minimale Knotenlänge (2 Zeiger+1 Byte +Nutzdaten¹)	maxi- male Anzahl Knoten	Knotenzahl des nächstgrößeren Fibonacci-Baums ...	... der Höhe
32	4294967296	2·4+1+3 = 12	3,6·10⁸	433494436	41
64	18446744073709551616	2·8+1+7 = 24	7,7·10¹⁸	1100087778366101930	86
¹ inklusive Schlüssel. Bei mehr Nutzdaten und weniger Hauptspeicher verringert sich die maximale Knotenzahl und Pfadlänge entsprechend.
Tab. 4: Maximale Pfadlänge in Abhängigkeit von der Adressierungsbreite

↑ Genau genommen bedarf es einer Kette mit den Gliedern Sperren(Sohn) und Entsperren(Vater) bis zum ersten unausgewogenen Knoten, der zunächst gesperrt bleibt, bis er in ein neues Wechselspiel mit den Gliedern Sperren(unausgewogenen Knoten) und Entsperren(Vorfahr) eintritt. (Dabei bedeutet Sperren(Knoten) eigentlich Sperren(Teilbaum). Und: bei einer potenziellen Rebalancierung muss die Sperre sogar eine Ebene höher gehalten werden.) Ist der Einfügepunkt erreicht, kann auch schon mit der Korrektur- und Entsprerrschleife begonnen werden – für maximale Parellelität wieder in einer Sohn-Vater-Kette.
Wenn alle nebenläufigen Mitspieler diese Gerichtetheit des Sperrprotokolls einhalten, kann eine zirkuläre Abhängigkeit und damit eine Verklemmung (deadlock) nicht entstehen.

Weitere Bäume [Bearbeiten]

Literatur [Bearbeiten]

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.
Kurt Mehlhorn Datenstrukturen und effiziente Algorithmen Teubner Stuttgart 1988, ISBN 3-519-12255-3.

Weblinks [Bearbeiten]

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)
Ben Pfaff „Performance Analysis of BSTs in System Software“, 2004 (englisch, PDF, 316 kB). Stanford University

Einzelnachweise [Bearbeiten]

↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7, S. 296.
↑ G. M. Adelson-Velsky, E. M. Landis: An algorithm for the organization of information (Englische Übersetzung aus Doklady Akademii Nauk SSSR 146). In: Soviet Math. Doklady. 3, 1962, S. 1259-1263.
↑ in der englischen Literatur häufig „balance factor“, so bei Knuth; „Höhenbalance“ bei #Mehlhorn
↑ Donald E. Knuth: The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition. Addison-Wesley, 1998, ISBN 0-201-89685-0, 6.2.3 Balanced Trees, S. 458–478.
↑ Ben Pfaff, a. a. O., S. 2
↑ „Header node“ und „HEAD“ bei Knuth a. a. O., S. 462; bei Ben Pfaff totum pro parte „tree data structure“
↑ Ben Pfaff, a. a. O. S. 3, gibt einem Objekt mit sehr ähnlicher Funktion den Namen traverser und offeriert für Suchen, Einfügen und Löschen eine normale und eine traverser Variante.

[4] Da einem Knoten in umkehrbar eindeutiger Weise der von ihm gewurzelte maximale Unterbaum, „sein“ Teilbaum, zugeordnet werden kann, sollen der Kürze halber Eigenschaften wie Höhe, Balance, Vater-Sohn- und Bruder-Beziehung usw. einem Knoten und einem solchen Teilbaum in gleicher Weise zukommen.
Gleichzeitig fungiert ein Knoten, z. B. beim Umhängen eines Teilbaums, als dessen „Henkel“.

[5] Es spielt zwar für die Höhendifferenz keine Rolle, dennoch wird hier – wie auch sonst häufig bei gewurzelten Bäumen – dem leeren oder fehlenden Baum die Höhe 0 gegeben, einem Blatt die Höhe 1 und einem höheren Baum die Höhe 1+Höhe seines höchsten Unterbaums. Gezählt werden also die Ebenen der Knoten.

[7] t $a:=\tfrac{1}{\log_2 \Phi} \approx 1{,}440420$ , $b:=\tfrac{a}{2} \log_2 5 -2 \approx -0{,}327724$ und $\Phi:=\tfrac{1+\sqrt 5}{2} \approx 1{,}618034$ (Zahl des goldenen Schnitts)

[8] t $c := \tfrac{a \Phi}{\sqrt 5} \approx 1{,}042298$

[10] Jeder Bogen des Baums wird genau einmal absteigend und einmal aufsteigend besucht.

[ISRT-11] Sei $G$ die Anzahl der Knoten, die nicht Blätter sind und die zwei Teilbäume gleicher Höhe haben, und $U$ die Anzahl der Knoten mit ungleich hohen Teilbäumen, dann ist $u:=\tfrac{U}{G+U}\in{[{0,1}]}$ der Anteil der unausgewogenen. Nur die Fibonacci-Bäume und die anderen dünnsten AVL-Bäume erreichen exakt $\scriptstyle u\,=\,1$ . Dagegen kommen nur die vollständig höhenbalancierten Binärbäume mit Knotenzahl $\scriptstyle 2^h-1$ auf exakt $\scriptstyle u\,=\,0$ . Ferner sei angenommen, dass der gespiegelte Baum gleich häufig vorkommt wie das Original.
Wir gehen rekursiv von folgender Situation aus: Bei einer Einfügung habe sich ergeben, dass die Höhe des Teilbaums, in dem die Einfügung stattfand, um 1 zugenommen hat. Beim Aufstieg zum Vaterknoten stellen wir fest, von welcher Seite wir kommen. Wir nehmen an: von rechts (das passt zu den Abbildungen 2 und 3; die gespiegelte Alternative führt überdies zu denselben Werten). Wir überprüfen die Lage im Vaterknoten und haben die folgenden Fälle zu unterscheiden:

$\operatorname{bal}$
vor
Einfügung Häufigkeit $\operatorname{bal}$
nach
Einfügung Rebalan-
cierung
erforderlich $\operatorname{bal}$
da-
nach Teilbaum
wird
höher um Nächste
Ebene zu
überprüfen

–1 links höher $u/2$ 0 Nein 0 Nein

0 ausgewogen $1-u$ 1 Nein 1 Ja

1 rechts höher $u/2$ 2 Ja 0 0 Nein

Tab. 2: Nach dem Einfügen: Die neuen Balance-Werte in Abhängigkeit von den alten

Die Wahrscheinlichkeit, bei einer Einfügung ausgehend von einer Ebene die nächsthöhere überprüfen zu müssen, ist also $q:=1-u$ . Die Wahrscheinlichkeit, dass wenigstens $n$ Ebenen überprüft werden müssen, ist $q^n$ und, dass genau $n$ Ebenen überprüft werden müssen, ist $q^n-q^{n+1}=(1-q)q^n$ . Die Anzahl der zu überprüfenden Ebenen summiert sich dann im Mittel auf

$\begin{align}(1-q)(q+2q^2+3q^3+...)\;&=\;q+q^2+q^3+...\;\\&=\;\tfrac{q}{1-q}\;=\;\tfrac{1-u}{1-(1-u)}\;=\;\tfrac{1-u}{u}\end{align}$ ,

was bei dem plausiblen $u\approx \tfrac12$ ergibt, dass im Mittel etwa eine weitere Ebene überprüft werden muss.

[DLET-12] Über den Anteil der unausgewogenen Knoten seien dieselben Annahmen wie bei der Einfügung gemacht.
Folgende Situation sei rekursiv angenommen: Nach einer Löschung habe sich die Höhe des Teilbaums, in dem die Löschung stattfand, um 1 vermindert. Ferner handele es sich o. B. d. A. um einen linken Teilbaum. Wir überprüfen nun die Lage im Vaterknoten dieses Teilbaums und unterscheiden die folgenden Fälle:

$\operatorname{bal}$
vor
Löschung Häufigkeit $\operatorname{bal}$
nach
Löschung Rebalan-
cierung
erforderlich $\operatorname{bal}$
da-
nach Teilbaum
wird nied-
riger um Nächste
Ebene zu
überprüfen

–1 links höher $u/2$ 0 Nein 1 Ja

0 ausgewogen $1-u$ 1 Nein 0 Nein

1 rechts höher $\frac{u}{2}$ $\tfrac{u}{2}(1-u)$ 2 Ja 1 0 ¹ Nein

$\tfrac{u}{2}(\tfrac{u}{2}+\tfrac{u}{2})$ 0 1 ² Ja

¹ Die vorletzte Zeile bezieht sich auf den Fall der Einfachrotation mit gleich hohen Söhnen

² und die letzte auf Rotationen mit nicht gleich hohen Söhnen, d. h. Doppelrotation (linker Sohn höher)
oder Einfachrotation mit dem rechten Sohn höher.

Tab. 3: Nach dem Löschen: Die neuen Balance-Werte in Abhängigkeit von den alten

Bei einer Löschung ergibt sich eine Wahrscheinlichkeit von weniger als $u$ für das Erfordernis, die nächsthöhere Ebene überprüfen zu müssen. Die Anzahl der zu überprüfenden Ebenen summiert sich dann im Mittel auf weniger als $\tfrac{u}{1-u}$ , was beim plausiblen $u\approx \tfrac12$ bedeutet, dass im Mittel weniger als $\approx 1$ Ebene eines Niveaus ≥ 2 überprüft werden muss.

[13] Dabei verhalten sich Sequenzen, die am linkesten oder rechtesten Knoten beginnen, besonders günstig, da diese Knoten selbst (Halb-)Blätter sind und der einzige Nachbar entweder Sohn oder Vater ist. Letzterer ist auch der einzige Knoten, der sowohl als Ersatz- wie als Nachfolgeknoten in Frage kommt. Wenn die Massenlöschung an einem Knoten mit zwei Söhnen beginnt und in eine vorgegebene Richtung fortschreiten soll, nimmt man am besten als Ersatzknoten den Nachbarn in der Gegenrichtung und als Nachfolgeknoten den Nachbarn in der vorgegebenen Richtung, der dann ein (Halb-)Blatt ist.

[14] t₂₃ kann leer sein, was dem Fall h=0 in der Abbildung 2 entspricht.

[15] Ist Z die Wurzel, dann ist V der „Kopf“ (s. den Abschnitt Kopf) und Z bei V als neue Wurzel einzuhängen.

[16] Solcherart als Spiegelung der Orientierung einer Kante aufgefasst, ist eine Binärbaumrotation eine Involution.

[17] 1 Bit, wenn bei den Söhnen aufgezeichnet, mit der Bedeutung: „Knoten ist höher“ als Bruder.

[20] Als eine Datenstruktur, die im homogenen Arbeitsspeicher (Hauptspeicher) untergebracht ist, ist der AVL-Baum durch die Größe desselben beschränkt. Dadurch ergeben sich auch Beschränkungen für die Pfadlänge. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten 8-Bit-Byte-Adressen.

Länge
eines
Zeigers
in Bit maximale Anzahl adressierbarer Bytes minimale Knotenlänge
(2 Zeiger+1 Byte
+Nutzdaten¹) maxi-
male Anzahl Knoten Knotenzahl des nächstgrößeren Fibonacci-Baums ... ... der Höhe

32 4294967296 2·4+1+3 = 12 3,6·10⁸ 433494436 41

64 18446744073709551616 2·8+1+7 = 24 7,7·10¹⁸ 1100087778366101930 86

¹ inklusive Schlüssel. Bei mehr Nutzdaten und weniger Hauptspeicher
verringert sich die maximale Knotenzahl und Pfadlänge entsprechend.

Tab. 4: Maximale Pfadlänge in Abhängigkeit von der Adressierungsbreite

[21] Genau genommen bedarf es einer Kette mit den Gliedern Sperren(Sohn) und Entsperren(Vater) bis zum ersten unausgewogenen Knoten, der zunächst gesperrt bleibt, bis er in ein neues Wechselspiel mit den Gliedern Sperren(unausgewogenen Knoten) und Entsperren(Vorfahr) eintritt. (Dabei bedeutet Sperren(Knoten) eigentlich Sperren(Teilbaum). Und: bei einer potenziellen Rebalancierung muss die Sperre sogar eine Ebene höher gehalten werden.) Ist der Einfügepunkt erreicht, kann auch schon mit der Korrektur- und Entsprerrschleife begonnen werden – für maximale Parellelität wieder in einer Sohn-Vater-Kette.
Wenn alle nebenläufigen Mitspieler diese Gerichtetheit des Sperrprotokolls einhalten, kann eine zirkuläre Abhängigkeit und damit eine Verklemmung (deadlock) nicht entstehen.

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7, S. 296.

[2] G. M. Adelson-Velsky, E. M. Landis: An algorithm for the organization of information (Englische Übersetzung aus Doklady Akademii Nauk SSSR 146). In: Soviet Math. Doklady. 3, 1962, S. 1259-1263.

[3] r englischen Literatur häufig „balance factor“, so bei Knuth; „Höhenbalance“ bei #Mehlhorn

[6] Donald E. Knuth: The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition. Addison-Wesley, 1998, ISBN 0-201-89685-0, 6.2.3 Balanced Trees, S. 458–478.

[9] Ben Pfaff, a. a. O., S. 2

[18] „Header node“ und „HEAD“ bei Knuth a. a. O., S. 462; bei Ben Pfaff totum pro parte „tree data structure“

[19] Ben Pfaff, a. a. O. S. 3, gibt einem Objekt mit sehr ähnlicher Funktion den Namen traverser und offeriert für Suchen, Einfügen und Löschen eine normale und eine traverser Variante.

[Ref 1]

[Ref 2]

[Ref 3]

[Anm 1]

[Anm 2]

[Ref 4]

[Anm 3]

[Anm 4]

[Ref 5]

[Anm 5]

[Anm 6]

[Anm 7]

[Anm 8]

[Anm 9]

[Anm 10]

[Anm 11]

[Anm 12]

[Ref 6]

[Ref 7]

[Anm 13]

[Anm 14]

AVL-Baum

Inhaltsverzeichnis

Balance [Bearbeiten]

Operationen [Bearbeiten]

Suchen [Bearbeiten]

Traversieren (Iterieren, Enumerieren) [Bearbeiten]

Aufsuchen erstes oder letztes Element [Bearbeiten]

Einfügen (Eintragen) [Bearbeiten]

Löschen (Austragen, Entfernen) [Bearbeiten]

Rebalancierung [Bearbeiten]

Rotation in Binärbäumen [Bearbeiten]

Einfachrotation [Bearbeiten]

Doppelrotation [Bearbeiten]

Beispiel [Bearbeiten]

Implementierung [Bearbeiten]

Kopf [Bearbeiten]

Iterative Programmierung [Bearbeiten]

Trennung der navigierenden von den modifizierenden Operationen [Bearbeiten]

Cursor [Bearbeiten]

Beispiel einer Anwendung mit mehreren AVL-Zugriffspfaden [Bearbeiten]

Parallelisierung [Bearbeiten]

Laufzeitmessungen [Bearbeiten]

Anmerkungen [Bearbeiten]

Weitere Bäume [Bearbeiten]

Literatur [Bearbeiten]

Weblinks [Bearbeiten]

Einzelnachweise [Bearbeiten]

Navigationsmenü

Meine Werkzeuge

Namensräume

Varianten

Ansichten

Aktionen

Suche

Navigation

Mitmachen

Drucken/exportieren

Werkzeuge

In anderen Sprachen