AVL-Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Abb. 1: AVL-Baum mit Balance-Faktoren (grün)
AVL-Baum
Komplexität
Platz \scriptstyle \mathcal{O}(n)
Operation im Mittel Worst Case
Suchen \scriptstyle \mathcal{O}(\log n) \scriptstyle \mathcal{O}(\log n)
Querschritt \scriptstyle \mathcal{O}(1) \scriptstyle \mathcal{O}(\log n)
Min, Max \scriptstyle \mathcal{O}(\log n) \scriptstyle \mathcal{O}(\log n)
Einfügen \scriptstyle \mathcal{O}(1) \scriptstyle \mathcal{O}(\log n)
Löschen \scriptstyle \mathcal{O}(1) \scriptstyle \mathcal{O}(\log n)
Verketten \scriptstyle \mathcal{O}(\log n) \scriptstyle \mathcal{O}(\log n)
Spalten \scriptstyle \mathcal{O}(\log n) \scriptstyle \mathcal{O}(\log n)
\scriptstyle n  Knoten im Baum
Tab. 1: Platz- und Zeit-Komplexitäten

Der AVL-Baum ist eine Datenstruktur in der Informatik, und zwar ein binärer Suchbaum mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens eins unterscheidet.[1] Diese Eigenschaft lässt seine Höhe nur logarithmisch mit der Zahl der Schlüssel wachsen und macht ihn zu einem balancierten binären Suchbaum. Die maximale (und mittlere) Anzahl der Schritte (Vergleiche), die nötig sind, um An- oder Abwesenheit eines Schlüssels festzustellen, hängt direkt mit der Höhe zusammen. Ferner ist der maximale Aufwand für Operationen zum Einfügen und Entfernen eines Schlüssels proportional zur Höhe des Baums und damit ebenfalls logarithmisch in der Zahl der Schlüssel; der mittlere Aufwand ist sogar konstant, wenn das Positionieren auf das Zielelement nicht mitgerechnet wird.

Viele Operationen, insbesondere die Navigationsoperationen, sind direkt von den binären Suchbäumen zu übernehmen. Bei den modifizierenden Operationen jedoch muss das AVL-Kriterium beobachtet werden, womit auf jeden Fall kleine Anpassungen verbunden sind, die bis zu Höhenkorrekturen durch so genannte Rotationen reichen können.

Der AVL-Baum ist benannt nach den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Velski und Jewgeni Michailowitsch Landis, die die Datenstruktur im Jahr 1962 vorstellten.[2] Damit ist der AVL-Baum die älteste Datenstruktur für balancierte Bäume.

Motivation[Bearbeiten]

Suchbäume – und damit auch die AVL-Bäume – sind Lösungen des sogenannten „Wörterbuchproblems“. Eine prinzipielle Erläuterung findet sich im Abschnitt Motivation im Artikel Binärer Suchbaum.

Den Suchbäumen gemeinsam ist, dass sie Dynamik unterstützen, das heißt, dass Einfügen und/oder Löschen von Elementen wichtig ist. Da bei diesen Operationen die Gefahr besteht, dass die Balance des Baums verloren geht, wurden verschiedene Balance-Kriterien für Binärbäume entwickelt. Bei den meisten sind die Aufwände für das Suchen, Einfügen und Löschen zumindest im Mittel logarithmisch, wenn auch mit unterschiedlichen konstanten Faktoren.

Beim AVL-Baum wird die Balance über die Höhe definiert, er ist ein höhen-balancierter binärer Suchbaum.

Das AVL-Kriterium[Bearbeiten]

Als den Balance-Faktor[3] BF(t) eines Knotens resp. Teilbaums[Anm 1] t in einem Binärbaum bezeichnet man die Höhendifferenz

BF(t) := -H(t_l) + H(t_r),

wobei H(t) die Höhe des Baums t, und tl der linke, tr der rechte Kindbaum von t ist.

Ein binärer (Such-)Baum ist genau dann ein AVL-Baum, wenn die AVL-Bedingung

-1 \; \leqq \; BF(t) \; \leqq \; +1

an jedem Knoten t eingehalten wird.

Eigenschaften[Bearbeiten]

Diese Definition beschränkt die Höhe H(t) eines AVL-Baums t mit n Knoten durch die Ungleichung[4]

\log_2 (n + 1) \; \leqq \; H(t) \; \leqq \; c \log_2 (n + 2) + b

mit c := 1log2 Φ ≈ 1,440420, b := c2 log2 5 – 2 ≈ –0,327724 und Φ := 1+52 ≈ 1,618034 (Zahl des goldenen Schnitts).

Die untere Schranke kommt vom vollständig balancierten Binärbaum (bei dem bis auf die unterste Ebene alle Ebenen komplett sind); die obere vom Fibonacci-Baum, der bei gegebener Höhe einen AVL-Baum mit kleinster Knotenanzahl darstellt, also am schlechtesten balanciert ist.[Anm 2]

Datenstruktur[Bearbeiten]

Werden der Datenstruktur AVL-Baum Operationen zum Zugriff und zur Verwaltung beigegeben, so werden diese nur dann als zugehörig angesehen, wenn sie die AVL-Eigenschaft aufrechterhalten. So erweitert wird die Datenstruktur zu einem Abstrakten Datentyp (ADT). Bei Suchbäumen gibt es im Englischen dafür auch die Charakterisierung als self-balancing tree.

Operationen[Bearbeiten]

Die wichtigsten Operationen bei den Suchbäumen – und damit beim AVL-Baum – sind: Suchen einerseits sowie Einfügen und Löschen andererseits. Mit der Eigenschaft, dass alle diese Operationen im schlechtesten Fall (Worst Case) logarithmische Komplexität haben, gehört der AVL-Baum zu den höhenbalancierten binären Suchbäumen.

Navigieren[Bearbeiten]

Die Navigationsoperationen, das sind die verschiedenen Suchoperationen, das Traversieren, Aufsuchen erstes oder letztes Element und ähnliche, lassen den Baum unverändert und funktionieren im Prinzip auf jedem binären Suchbaum. Die dortigen Angaben zur Komplexität gelten genauso für AVL-Bäume, mit der Präzisierung, dass die Höhe des AVL-Baums sich logarithmisch zur Anzahl der Knoten verhält.

Das Suchen (englisch: find, search oder locate) eines Elements anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. Die Höhen-Balancierung des AVL-Baums versucht, auf diese Operation hin zu optimieren. Sie ermöglicht einen sogenannten direkten Zugriff (im Gegensatz zum sequentiellen Zugriff der Traversierung). Sie wird in der Regel als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.

Das Suchen setzt eine totale Quasiordnung auf der Menge der Schlüssel voraus, die am flexibelsten durch eine Vergleichsfunktion repräsentiert wird.

Einfügen (Eintragen)[Bearbeiten]

Es sei angenommen, dass die Navigation zum Einfügepunkt bereits erfolgt ist. Ein Einfügepunkt ist ein externes Blatt und liegt ganz links oder ganz rechts oder zwischen 2 internen (und Schlüssel tragenden) Knoten, kann also auf jeden Fall durch einen (internen) Knoten zusammen mit einer Richtung (links oder rechts) spezifiziert werden. Die Knoten ganz links oder ganz rechts sind immer (Halb-)Blätter, wie auch von 2 Nachbarknoten immer genau einer ein (Halb-)Blatt ist. Ein solcher Knoten sei – zusammen mit der entsprechenden Richtung – als der unmittelbare Einfügepunkt bezeichnet. So wird er auch von einer nicht erfolgreichen Suchoperation geliefert.

Zur Einfügung (englisch: insert oder add) wird der Knoten mit dem neuen Schlüssel als Blatt am Einfügepunkt eingehängt – mit anderen Worten: das externe Blatt wird zum internen Blatt. Die Höhe des aus diesem Blatt bestehenden Teilbaums erhöht sich von 0 auf 1. Beim Aufstieg zum Elterknoten, und später bei jedem weiteren Aufstieg, gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors dieses Knotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

  1. Wird der Balance-Faktor zu 0, dann kommt man von einem Kindbaum, der vorher niedriger war, und die Höhe des Knotens ändert sich nicht – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum erfüllt ist.
  2. Wird der Balance-Faktor zu ±1 (er muss vorher 0 gewesen sein), erhöht sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.
  3. Wird auf einer Ebene der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe Rebalancierung weiter unten). Danach hat bei einer Einfügeoperation der Teilbaum die gleiche Höhe wie vorher – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum auch schon erfüllt ist.

Das Einfügen des (n+1)-ten Knotens in einen AVL-Baum mit n Knoten hat im schlechtesten Fall logarithmischen Aufwand, beispielsweise wenn jede Ebene bis hinauf zur Wurzel überprüft werden muss. Da aber hierfür die Wahrscheinlichkeit von Ebene zu Ebene nach oben hin exponentiell abnimmt, ist der Aufwand für das Einfügen im Mittel konstant.[Anm 3] Hierbei ist das Aufsuchen der Einfügeposition nicht mitgerechnet.

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 (englisch: delete oder remove) sind mehr Fälle zu unterscheiden als beim Einfügen (siehe auch Binärbaum). Einfach sind die Fälle, wo der zu löschende Knoten ein (Halb-)Blatt ist. Hat er aber zwei Kinder, 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 eventuell höheren bevorzugen), um die beiden Teilbäume daran wieder aufzuhängen. Der hierfür erforderliche Abstieg geht maximal über so viele Stufen, wie die Höhe beträgt, und im Mittel über genau eine. Der Ersatzknoten wird in der Hierarchie des Baums an der Stelle des gelöschten Knotens eingeklinkt, muss dabei aber selbst aus seinem Herkunftsteilbaum entfernt werden – das ist einfach, da er ein (Halb-)Blatt ist.

Da letztlich in jedem Fall ein Blatt, das ist ein Teilbaum bestehend aus 1 Knoten, entfernt wird, vermindert sich dessen Höhe von 1 auf 0. Beim Aufstieg zum Elterknoten (und später bei jedem weiteren Aufstieg) gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors dieses Knotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

  1. Wird der Balance-Faktor zu ±1 (er war vorher 0), dann ändert sich dessen Höhe nicht – mit der Folge, dass die Balance-Faktoren oberhalb bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum erfüllt ist.
  2. Wird der Balance-Faktor zu 0, verringert sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.
  3. Wird der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe Rebalancierung weiter unten). Danach kann bei der Löschoperation der neue Teilbaum eine um 1 niedrigere Höhe als haben vorher – mit der Folge, dass weiterhin überprüft und gegebenenfalls rebalanciert werden muss.
    Es kommt aber auch vor, dass sich die gleiche Höhe wie vor dem Löschen ergibt, sodass die Balance-Faktoren oberhalb bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum auch schon erfüllt ist.

Der Aufwand fürs Löschen ist im schlechtesten Fall logarithmisch (mit oder ohne Suchen); im Mittel aber, wenn man das Auffinden des Löschkandidaten nicht mitrechnet, ist er konstant, da die Wahrscheinlichkeit für die Notwendigkeit, die Balance auf der nächsthöheren Ebene überprüfen zu müssen, nach oben hin exponentiell abnimmt.[Anm 4]

Rebalancierung[Bearbeiten]

Abb. 2: Einfachrotation
Links(X)

Wenn bei einer Operation ein Höhenunterschied von mehr als 1 zwischen zwei Geschwister-Teilbäumen entsteht, muss um der Einhaltung des AVL-Kriteriums willen eine Rebalancierung durchgeführt werden. Als Reparaturwerkzeuge hierfür eignen sich die sogenannten Rotationen.

Für Einfügungen und Löschungen, bei denen die temporäre Höhendifferenz nie über 2 hinausgeht, werden zwei Varianten benötigt: Einfach- und Doppelrotation. Eine Einfachrotation leistet die Rebalancierung, wenn das innere Kind des um 2 höheren Geschwisters (Z in den zwei Abbildungen 2 und 3), das ist das Kind mit einer Kindesrichtung, die der von Z entgegengesetzt ist, (t23 in der Abbildung 2 beziehungsweise Y in der Abbildung 3) nicht höher ist als sein Geschwister, das äußere Kind (t4 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, das heißt die zwei Balance-Faktoren 2 und 1 (beim Löschen auch 0) sind, kurz: die Balance zweimal hintereinander die gleiche Richtung hat. Der andere Fall, bei dem das innere Kind 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, das heißt die zwei Balance-Faktoren 2 und –1 sind, kurz: die Balance die Richtung wechselt.

Die Schlüssel bewegen sich bei Rotationen nur „vertikal“ (innerhalb der senkrechten Raster). Die In-order-Reihenfolge der Knoten, die ja die Sortierreihenfolge abbildet, bleibt also vollkommen erhalten.

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

Einfachrotation[Bearbeiten]

Sie wird im Original Малое вращение (kleine Drehung) genannt.

Die obenstehende Abbildung 2 zeigt eine Rechts-Rechts-Situation. In der oberen Hälfte haben die beiden Teilbäume Z und t1 des Knotens X einen Höhenunterschied von 2. Das innere Kind t23 des um 2 höheren Knotens Z ist nicht höher als sein Geschwister t4.
Dies kann nach einem Einfügen in den Teilbaum t4 oder nach einem Löschen aus dem Teilbaum t1 auftreten. Der in der Abbildung 2 blass gehaltene Fall, dass t23 gleich hoch ist wie t4, kommt nur beim Löschen vor.

Die Rebalancierung (gezeigt in der unteren Hälfte der Abbildung) gelingt durch eine Einfachrotation nach links. 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. Dies ist bei einer Löschung genauso, wenn Z nicht rechtslastig war. Bei rechtslastigem Z ist die Höhe jedoch um 1 vermindert, in welchem Fall die Überprüfung der Balance-Faktoren oberhalb weitergehen muss.

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

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

Doppelrotation[Bearbeiten]

Sie wird im Original Большое вращение (große Drehung) genannt.

Die oben in der Abbildung 3 gezeigte Situation unterscheidet sich von der in Abbildung 2 darin, dass der mittlere Teilbaum (mit Wurzel Y), das ist das innere Kind des um 2 höheren Knotens Z, höher ist als sein Geschwister t4 – eine Rechts-Links-Situation, da X rechts- und Z linkslastig ist.
Das kann nach einer Einfügung in einen der Teilbäume t2 oder t3 oder nach einer Löschung aus dem Teilbaum t1 passieren. Der in der Abbildung 3 in Standardfarbe gehaltene Fall, bei dem t2 gleich hoch ist wie t3, 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. 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) Kindes Y von Z.

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

Die Höhe des neuen Teilbaums Y ist nach einer Einfügung gleich wie die von X vor der Operation. Bei einer Löschung ist die Höhe jedoch um 1 vermindert, mit der Folge, dass oberhalb die Überprüfung der Balance-Faktoren weitergehen muss.

Bei einer Links-Rechts-Situation wird die gespiegelte Version, das heißt 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(VP)

rebalanciert.

Operationen mit ganzen AVL-Bäumen[Bearbeiten]

Die folgenden zwei Operationen haben ganze AVL-Bäume als Ein- und Ausgabeoperanden. Sie gehören nicht zum Standardsatz und fehlen in manchen Implementierungen. Es soll aber hier gezeigt werden, dass auch sie mit logarithmischem Aufwand durchgeführt werden können.

Verketten[Bearbeiten]

Abb. 4: Verkettung von 2 AVL-Bäumen

Zwei AVL-Bäume können mit logarithmischem Aufwand verkettet (konkateniert) werden (englisch: concat oder auch nur cat). Für die Sortierfolge müssen natürlich alle Schlüssel des ersten Baums allen Schlüsseln des zweiten vorangehen.

Algorithmus

Man steigt an der rechten Flanke des ersten Baums (siehe Abbildung 4. Die grauen Pfeile zeigen den Weg durch den Graphen.) und an der linken des zweiten bis zu den Blättern hinab und merkt sich die Knoten auf den Pfaden zusammen mit ihren Höhen.
Ohne Beschränkung der Allgemeinheit sei der erste Baum der höhere (wie in der Abbildung). Dem zweiten Baum wird sein erstes Element H entnommen. Es spielt nachher die Rolle eines „Bindeglieds“. Die Höhe des zweiten Baums sei jetzt h. Man sucht nun in der rechten Flanke des ersten Baums nach einem Knoten G der Höhe h+1 oder h (einen von beiden muss es geben; gibt es beide, sei der höhere bevorzugt). Man macht den zweiten Baum zum Geschwister von G, wobei das Bindeglied H als Elter von beiden eingesetzt wird. Dann wird H beim Elter F von G an Gs Stelle als Kind eingehängt. Der maximale Höhenunterschied zwischen E und dem neuen H ist 2 (wenn E die Höhe h–1 hat, dann hat G die Höhe h, und das neue H die Höhe h+1). Nach einer ersten Anpassung mit eventueller (Doppel-)Rotation müssen noch aufsteigend die Balance-Faktoren wie bei einer Einfügung überprüft und gegebenenfalls korrigiert werden.

Dabei kann die Höhe des Baums um 1 zunehmen.

Spalten[Bearbeiten]

Etwas komplizierter als das Verketten ist das Spalten (englisch: split) eines AVL-Baums in zwei separate AVL-Bäume an einem externen Knoten, also einer Stelle zwischen zwei internen Knoten (Schlüsseln), die als Paar (Knoten, Richtung) einschließlich des Pfades zur Wurzel gegeben sei. Links davon liegt die linke Partition mit den kleineren Schlüsseln und rechts davon die rechte mit den größeren. Die so spezifizierte Trennlinie (rot in der Abbildung 5) zerschneidet Kanten des gegebenen Baums auf dem Pfad des Knotens zur Wurzel, so dass sich links wie rechts ein Wald von „Schnipseln“ ergibt. Schließlich kann jeder der beiden Wälder mit logarithmischem Aufwand zu einem AVL-Baum zusammengefügt werden.

Abb. 5: Ein Induktionsschritt beim Spalten eines AVL-Baums
Algorithmus

Die Schnipsel sind Bäume in AVL-Form bis auf eventuell einen Knoten („Stummel“) (Knoten H in der Abbildung 5) auf hoher Ebene mit Ausgangsgrad 1 (nicht unbedingt die Wurzel des Schnipsels), der beim Verketten mit dem nächstniedrigeren Schnipsel auf der gleichen Seite als Bindeglied fungiert.

Vollständige Induktion nach den Schnipseln, auszuführen auf beiden Seiten der Trennlinie

Induktionsanfang: Gibt es ein Kind des gegebenen Knotens in der gegebenen Richtung, dann stellt der Teilbaum dieses Kindes einen Schnipsel dar, welcher schon in AVL-Form ist. Der gegebene Knoten liegt auf der Gegenseite und ist zum Stummel geworden. Er wird in den Teilbaum seines nunmehr „Einzelkindes“ je nach Seite als rechtestes beziehungsweise linkestes Element einfügt. Auf beiden Seiten ist der niedrigste Schnipsel jetzt ein AVL-Baum. Damit ist der Induktionsanfang auf beiden Seiten geschafft.

Induktionsschritt (siehe Abbildung 5): Der niedrigste Schnipsel von beiden Seiten ist nach Induktionsannahme ein AVL-Baum. Ohne Beschränkung der Allgemeinheit sei er links und heiße I. Beim Aufstieg im Pfad gelangt man zum nächsthöheren ebenfalls linken Stummel H, dessen ursprüngliche Höhe mit h bezeichnet sei. Zerschnittene Kanten (gestrichelte schwarze Pfeile in der Abbildung) und die von ihnen zurück gelassenen Stummel erkennt man am Wechsel der Kindesrichtungen beim Aufstieg im Pfad. Die Höhen sind anhand der Balance-Faktoren aufs genaueste mitzuschreiben. Der Teilbaum des Einzelkindes D von H wird mit dem Schnipsel I unter Einsatz von H als Bindeglied verkettet. (Was die bei der Verkettung involvierten Knoten anbetrifft, entsprechen die Namen in der Abbildung 5 denen der Abbildung 4.) Dabei kann seine Höhe um 1 zunehmen. Nun wird D zum Kind seines vormaligen Großelters C gemacht in der Kindesrichtung seines vormaligen Elters H, das heißt zum Geschwister seines vormaligen Onkels B. Die Höhendifferenz zu letzterem ist maximal 3. Die lokale AVL-Balance lässt sich durch Rotationen herstellen, wobei die Höhe des Teilbaums um 1 abnehmen kann. (Die Vorgehensweise bei einem Höhenunterschied von 3 ähnelt der bei einem von 2: Ist das innere Kind des höheren Geschwisters niedriger als das äußere Kind, kann man die AVL-Balance mit einer Einfachrotation herstellen. Ist es höher, kommt man mit einer Doppelrotation durch. Sind beide Kinder gleich hoch, hängt es vom Balance-Faktor des inneren Kindes ab: ist der ausgewogen, macht’s eine Doppelrotation; ist er außenlastig, schaffen’s zwei Rotationen; ist er innenlastig, geht’s mit drei Rotationen.) Bei den Ebenen darüber sind die Balance-Faktoren wie bei einer Löschung zu überprüfen und gegebenenfalls anzupassen, wobei die Gesamthöhe wieder um 1 abnehmen kann. Damit ist I so in den neuen Schnipsel A integriert, dass A wieder ein AVL-Baum ist – und den Schnipsel I des nächsten Rekursionsschrittes darstellt.

Die innerhalb eines Rekursionsschrittes besuchten Kanten (graue Pfeile in der Abbildung 5) betreffen nur Ebenen zwischen den Wurzeln von zwei Schnipseln, die auf derselben Seite übereinander liegen. Die Rekursionsschritte auf der linken und rechten Seite greifen reißverschlussartig ineinander: der Aufstieg auf der rechten wird auf der linken Seite beim Verketten ab- und wieder aufgestiegen, woran sich ein Aufstieg anschließt, der auf der rechten Seite ab- und wieder aufgestiegen wird, usw. Eine Ebene wird höchstens dreimal besucht, jedes Mal mit konstantem Aufwand. Damit ist der Gesamtaufwand fürs Spalten proportional zur Gesamthöhe.[5]

Anwendungsbeispiele[Bearbeiten]

Die Massenlöschung von allen Schlüsseln in einem zusammenhängenden Bereich (Intervall) kann durch zweimaliges Spalten und einmaliges Verketten geschehen oder, wenn das kleinste oder größte Element mit dabei ist, durch einmaliges Spalten. In ähnlicher Weise lässt sich ein Intervall mit logarithmischem Aufwand als AVL-Baum aus einem AVL-Baum herauspräparieren.

Eine Masseneinfügung kann durch einmaliges Spalten und zweimaliges Verketten durchgeführt werden, sofern die Menge als AVL-Baum vorbereitet ist und ihre Schlüssel in einem Intervall liegen, das im Zielbaum nicht vorkommt.

Implementierung[Bearbeiten]

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

Insbesondere wenn der Prozessor korrekt ausgerichtete Zeiger bevorzugt oder erzwingt, können die Balance-Bits von einem Zeigerfeld im Knoten absorbiert werden, so dass sie kein extra Speicherwort benötigen.

Ansonsten gelten für die Implementierung von AVL-Bäumen dieselben Empfehlungen wie für die binären Suchbäume im Allgemeinen. Auf die Besonderheiten des AVL-Cursors sei im Folgenden explizit eingegangen.

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 zur Angabe verwendet werden, wohin der Cursor nach der Löschung fortschreiten soll. Beim Traversieren gibt Knoten den Ausgangspunkt und Richtung die gewünschte Richtung der Navigation an, um im Ergebnis wieder bei einem solchen Paar anzukommen. Damit erzeugen und/oder verbrauchen alle wichtigen Operationen ein Konstrukt, das (in Analogie zum Beispiel zu den Datenbanken) Cursor genannt wird.[6]

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

  1. Elterzeiger vorhanden: Ein Paar (Knoten, Richtung) stellt einen vollwertigen Cursor dar.
    Ein Cursor wird nach einer (den Cursor nicht pflegenden) Operation dann und nur dann ungültig, wenn es sich um eine Löschung des Knotens dieses Cursors handelt.
    Mit dem prozentualen Aufschlag auf den Speicherbedarf für die Datenstruktur erkauft man sich auf jeden Fall eine prozentuale Einsparung an Laufzeit, da der Rückweg zu Wurzel und Kopf immer schon gesichert ist.
  2. Zeiger zum Elterknoten nicht vorhanden („Cursor mit Stapel“): Zusätzlich zum Paar (Knoten, Richtung) muss der Pfad vom Knoten zu Wurzel und Kopf im Cursor gehalten werden. Die Länge des Cursors entspricht damit der maximalen Höhe des Baums.[Anm 6]
    Bei allen Operationen ist der Zugriff zum Elterknoten über den Stapel im Cursor geringfügig teurer als über den Elterzeiger. Soll der Pfad im Cursor auch nach einer modifizierenden Operation gültig gehalten werden (beispielsweise für sequentielle Einfügungen oder Löschungen), kommt noch ein zusätzlicher prozentualer (im Mittel konstanter und im schlechtesten Fall logarithmischer) Aufschlag hinzu. Dies kann so aber nur für einen Cursor, den Eingabecursor, erbracht werden.

Benötigt eine Anwendung mehrere Cursor für ein und denselben Suchbaum und über Änderungen hinweg, dann kann das Aufrechterhalten der Konsistenz der Cursor mit Stapel (zum Beispiel durch erneutes Suchen mit im Mittel logarithmischen Kosten) so aufwändig werden, dass es wirtschaftlicher ist, dem Baum Elterzeiger zu spendieren.

Trennung der navigierenden von den modifizierenden Operationen[Bearbeiten]

Die Einführung des Cursors erlaubt die Modularisierung der Navigations- von den modifizierenden Operationen. Diese setzt den im Mittel unterlogarithmischen (sprich: konstanten) Aufwand der letzteren frei, denn ein Aufstieg bis zur Wurzel ist (wie in[Anm 3] und[Anm 4] gezeigt) nur in Ausnahmefällen erforderlich. In Anwendungen mit starkem sequentiellem Anteil kann sich das positiv auf die Laufzeit auswirken.

Parallelisierung[Bearbeiten]

Wird iterativ programmiert, dann kann die Überprüfungs- und Reparaturschleife auch in der umgekehrten Richtung, das heißt von Kopf und Wurzel zum Blatt, durchlaufen werden.[7] Das ist insbesondere dann interessant, wenn auf den Baum hochgradig parallel (konkurrent) zugegriffen werden soll. Zum Beispiel würde in einem Szenario „Suchen und Einfügen“ die Suchoperation sich den tiefsten (letzten) unausgewogenen Knoten auf dem Pfad merken, ab dort den Baum sperren[Anm 7] und die Vergleichsergebnisse aufbewahren. Zum Fertigstellen der Einfügeoperation müsste dann der gesperrte Vorfahr (gegebenenfalls nach einer Rebalancierung) auf ausgewogen und alle seine Nachfahren bis zum Blatt auf die den eingeschlagenen Richtungen entsprechenden Balance-Faktoren 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.

Vergleich mit Rot-Schwarz-Baum[Bearbeiten]

Die Menge der AVL-Bäume ist eine echte Teilmenge in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der das AVL-Kriterium erfüllt, lässt sich in einer das Rot-Schwarz-Kriterium erfüllenden Weise einfärben.

Beweis
4 kleine AVL-Bäume in Rot-Schwarz-Färbung.
Bei den geteilten Knoten gehen beide Farben.

Behauptung: Hat der AVL-Baum eine gerade Höhe h, dann lässt er sich mit Schwarztiefe h2 bei schwarzer Wurzel einfärben; ist h ungerade, dann mit Schwarztiefe h+12 und einer schwarzen oder mit h–12 und einer roten Wurzel. (Die NIL-Knoten sind dabei nicht mitgezählt.)

Beweis: Die Behauptung ist richtig für h ≤ 1 (siehe Abbildung).
Bei größerem geradem h gibt es einen Kindbaum mit der ungeraden Höhe h–1, der sich nach Induktionsvoraussetzung mit roter Wurzel und Schwarztiefe h–22 einfärben lässt. Hat der andere Kindbaum dieselbe Höhe, so gilt für ihn dasselbe. Ist er niedriger, dann ist seine Höhe h–2 und gerade; er lässt sich also mit der gleichen Schwarztiefe (bei schwarzer Wurzel) einfärben. Nachdem die neue Wurzel schwarz eingefärbt ist, ist die Schwarztiefe im zusammengesetzten Baum h2 für alle Pfade.
Bei größerem ungeradem h hat einer der Kindbäume die gerade Höhe h–1 und lässt sich mit schwarzer Wurzel und Schwarztiefe h–12 einfärben. Ist ein Kindbaum niedriger, dann ist seine Höhe h–2 und ungerade, lässt sich also mit glücklicherweise derselben Schwarztiefe h–12 und mit schwarzer Wurzel einfärben. Wird die neue Wurzel schwarz eingefärbt, dann ist die neue Schwarztiefe h+12. Da beide Kindbäume jedoch schwarze Wurzel haben, kann die neue Wurzel auch rot eingefärbt werden, in welchem Fall sich eine Schwarztiefe von h–12 ergibt.  ■

Kein AVL-Baum

Es gibt aber Rot-Schwarz-Bäume, die das AVL-Kriterium nicht erfüllen. Die nebenstehende Abb. zeigt zum Beispiel einen Rot-Schwarz-Baum mit 6 (inneren) Knoten und der externen Pfadlängensumme 21, während 20 die größte externe Pfadlängensumme bei AVL-Bäumen (und zugleich die kleinstmögliche für alle Binärbäume) dieser Größe ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar um den (konstanten) Faktor c20,720. Allgemein werden AVL-Bäume als besser balanciert und ihr Suchzeitverhalten als günstiger angesehen.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für die Farbe gegenüber 2 oder auch 1 Bit(s)[Anm 5] für den Balance-Faktor.

Der Platzbedarf und das Laufzeitverhalten für die angeführten Operationen verhalten sich im Mittel und im Worst Case identisch. Zwar bietet der Rot-Schwarz-Baum amortisiert konstante Modifikationskosten[8] und der AVL-Baum nur im Mittel konstante.[Anm 8] Anwendungen von binären Suchbäumen, die nur Sequenzen von Einfügungen und Löschungen – ganz ohne intervenierende Suchoperationen – enthalten, gehen am Zweck des Suchbaums vorbei. Sieht man also von dieser Art Anwendungen ab, ist das Gesamtverhalten einer Mischung von Suchen und Modifikation bei beiden Datenstrukturen amortisiert, im Mittel und im Worst Case logarithmisch.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen – auch mit weiteren Suchalgorithmen und Spielarten der Datenstrukturen – finden sich bei Ben Pfaff.[9] Seine Ergebnisse zeigen in 79 Messungen unter anderem die sehr große Ähnlichkeit von AVL-Bäumen (AVL) und Rot-Schwarz-Bäumen (RB) mit Laufzeitverhältnissen AVLRB zwischen 0,677 und 1,077 bei einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.

Anwendungen[Bearbeiten]

Als grundlegende Hilfsmittel der Informatik haben die binären Suchbäume ein großes Einsatzgebiet, in welchem sie aber auch hochgradig untereinander austauschbar sind. Konkrete Beispiele und Auswahlkriterien finden sich in Binärer Suchbaum#Anwendungen.

Weiterführende Informationen[Bearbeiten]

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

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

Einzelnachweise[Bearbeiten]

  1. Thomas H. Cormen u.a.: Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge (Massachusetts) 2001, S. 296.
  2. G. M. Adelson-Velsky, E. M. Landis: Один алгоритм организации информации. In: Doklady Akademii Nauk SSSR. 146, 1962, S. 263–266. (russisch)
    Englische Übersetzung von Myron J. Ricci: An algorithm for the organization of information. In: Soviet Mathematics 3, 1962, S. 1259–1263.
  3. In der englischen Literatur meist „balance factor“, so bei Donald E. Knuth: The Art of Computer Programming, Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 459; „Höhenbalance“ bei Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner, Stuttgart 1988, S. 295.
  4. Donald E. Knuth: The Art of Computer Programming, Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 460.
  5. Costin S, der in seinem Projekt AvlTree.cs AVL-Bäume mit Concat- und Splitoperationen implementiert, fordert dazu die Aufzeichnung der vollen absoluten Höhe in jedem Knoten. Man kann aber – wie gezeigt – mit den Balance-Faktoren auskommen, ohne den Aufwand zu erhöhen.
  6. Ben Pfaff gibt einem Objekt mit sehr ähnlicher Funktionalität den Namen „traverser“ und offeriert für Suchen, Einfügen und Löschen eine Standard- und eine Traverser-Variante. (An Introduction to Binary Search Trees and Balanced Trees. S. 15 und Performance Analysis of BSTs in System Software. S. 3)
  7. „Top-Down-Strategie“ bei Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner, Stuttgart 1988, S. 197–198.
  8.  Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0. S. 165.
  9. Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University 2004.

Anmerkungen[Bearbeiten]

  1. 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, Elter-Kind- und Geschwister-Beziehung usw. einem Knoten und einem solchen Teilbaum in gleicher Weise zukommen. Umgekehrt fungiert, zum Beispiel beim Umhängen eines Teilbaums, dessen Wurzel als „Henkel“.
  2. Ähnlich wie es bei einem unbalancierten binären Suchbaum eine hohe Wahrscheinlichkeit gibt, dass er bei zufälligen Einfügungen eine gewisse Balanciertheit erlangt (siehe auch Pfaff 2004b S. 2.), ist auch beim AVL-Baum die Wahrscheinlichkeit sehr hoch, dass er besser balanciert herauskommt als seine am schlechtesten balancierte Ausprägung, der Fibonacci-Baum. Strebt beim Fibonacci-Baum die Anzahl n der Knoten gegen unendlich, dann verhält sich seine mittlere Suchtiefe über alle Knoten asymptotisch wie a log2 n mit a := c Φ5 = Φ5 log2 Φ ≈ 1,042298, weicht also nur um 4 Prozent von der idealen eines vollständig balancierten Binärbaums ab. Wird über alle AVL-Bäume einer festen Höhe oder über alle Einfügereihenfolgen zu einer festen Knotenzahl gemittelt, liegt der Mehraufwand gegenüber den jeweils bestmöglichen, den vollständig balancierten Binärbäumen zwischen 0 und 2 Prozent (Zahlen für kleine Bäume im Abschnitt Mittlere Suchtiefe bei AVL-Bäumen).
  3. a b 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 := UG+U ∈ [0,1] der Anteil der unausgewogenen. (Nur die Fibonacci-Bäume und die anderen dünnsten AVL-Bäume erreichen exakt u = 1. Dagegen kommen nur die vollständigen Binärbäume mit Knotenzahl 2h–1 auf exakt u = 0.) Ferner sei angenommen, dass der gespiegelte Baum gleich häufig vorkommt wie das Original.
    Von folgender Situation sei rekursiv ausgegangen: Bei einer Einfügung habe sich ergeben, dass die Höhe des Teilbaums, in dem die Einfügung stattfand, um 1 zugenommen hat. Ferner sei angenommen, dass es sich um einen rechten Kindbaum handelt (dazu passen die Abbildungen 2 und 3; die gespiegelte Alternative linker Kindbaum sei dem Leser überlassen, sie führt zu denselben Werten). Bei der Überprüfung der Lage im Elterknoten dieses Teilbaums sind die folgenden Fälle zu unterscheiden:
    BF
    vor
    Einfügung
      Häufigkeit BF
    nach
    Einfügung
    Rebalan-
    cierung
    erforderlich
    BF
    da-
    nach
    Teilbaum
    wird
    höher um
    Ebene ober-
    halb zu
    überprüfen
    –1 links höher u2 0 Nein 0 Nein
    0 ausgewogen 1–u 1 Nein 1 Ja
    1 rechts höher u2 2 Ja 0 0 Nein
    Tab. 2: Nach dem Einfügen: Die neuen Balance-Faktoren (BF) 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 qn und, dass genau n Ebenen überprüft werden müssen, ist qnqn+1 = (1–q) qn. Somit summiert sich die Anzahl der zu überprüfenden Ebenen 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 bedeutet, dass die mittlere Anzahl der zu überprüfenden Ebenen zwischen 1 und 3 liegt, wenn 0,5 ≥ u ≥ 0,25.

  4. a b Ü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 ohne Beschränkung der Allgemeinheit um einen linken Kindbaum. Bei der Überprüfung der Lage im Elterknoten dieses Teilbaums sind die folgenden Fälle zu unterscheiden:
    BF
    vor
    Löschung
      Häufigkeit BF
    nach
    Löschung
    Rebalan-
    cierung
    erforderlich
    BF
    da-
    nach
    Teilbaum
    wird nied-
    riger um
    Ebene ober-
    halb zu
    überprüfen
    –1 links höher u2 0 Nein 1 Ja
    0 ausgewogen 1–u 1 Nein 0 Nein
    1 rechts höher u2 u2 (1–u) 2 Ja 1 1 Nein
    u2 (u2+u2) 0 2 Ja
    1 Die vorletzte Zeile bezieht sich auf den Fall der Einfachrotation mit gleich hohen Kindern und
    2 die letzte auf Rotationen mit nicht gleich hohen Kindern, das heißt Doppelrotation (linkes Kind höher)
      oder Einfachrotation mit dem rechten Kind höher.
    Tab. 3: Nach dem Löschen: Die neuen Balance-Faktoren (BF) 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. Also summiert sich die mittlere Anzahl der zu überprüfenden Ebenen auf weniger als u1–u, was bei u ≤ 0,5 bedeutet, dass im Mittel weniger als ungefähr eine Ebene eines Niveaus ≥ 2 überprüft werden muss.

  5. a b 1 Bit, wenn bei den Kindern aufgezeichnet. Wird dem Bit die Bedeutung „Höhensprung oberhalb“ gegeben, dann kann die Höhe im Pfad ohne Kenntnis der Kindesrichtung berechnet werden. Dennoch: 2 Balance-Bits nebeneinander sind für die Modifikationsoperationen geschickter.
  6. Als eine Datenstruktur, die im homogenen Arbeitsspeicher (Hauptspeicher) untergebracht ist, ist der AVL-Baum durch dessen Größe beschränkt, also auch die Höhe des Baums und die Längen der Pfade von Blatt zu Wurzel. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten 8-Bit-Byte-Adressen.
    Breite
    eines
    Zeigers
    in Bit
    maximale Anzahl adressierbarer Bytes minimale Knotenlänge
    (2 Zeiger+1 Byte
    +Nutzdaten 1)
    maxi-
    male Anzahl Knoten
    Knotenzahl des nächstgrößeren Fibonacci-Baums … … der Höhe
    32 4294967296 2·4+1+3 = 12 3,6·108 433494436 41
    64 18446744073709551616 2·8+1+7 = 24 7,7·1018 1100087778366101930 86
    1 inklusive Schlüssel. Bei mehr Nutzdaten und weniger Hauptspeicher
      verringert sich die maximale Knotenzahl und Höhe entsprechend.
    Tab. 4: Maximale Höhe in Abhängigkeit von der Adressierungsbreite

    Fazit: Es ist bei AVL-Bäumen vertretbar, Cursor mit Stapeln bereitzustellen, die so groß sind, dass ein Überlauf nicht auftreten kann.

  7. Genau genommen bedarf es einer Kette mit den Gliedern Sperren(Kind) und Entsperren(Elter) 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 potentiellen 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 Parallelität wieder in einer Kind-Elter-Kette.
    Wenn alle nebenläufigen Mitspieler diese Gerichtetheit des Sperrprotokolls einhalten, kann eine zirkuläre Abhängigkeit und damit eine Verklemmung (deadlock) nicht entstehen.
  8. Fügt man n Knoten in einen leeren AVL-Baum ein, so ist (wie beim Rot-Schwarz-Baum) der Aufwand A im Mittel proportional zu n. Es gibt aber auch (seltene) Schlüsselfolgen, bei denen A schneller wächst, und zwar in etwa wie die Anzahl der Vergleiche, die für die Positionierung dieser Einfügungen nötig sind.
Dies ist ein als lesenswert ausgezeichneter Artikel.
Dieser Artikel wurde am 5. Februar 2014 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.