Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Botanik: Basisalgorithmen für Container Binärbaum Abstrakte Container

3.4 AVL-Baum

Der Binärbaum hat leider den Nachteil, das er zu einer Liste entartet, wenn die Elemente schon in sortierter Reihenfolge eingefügt werden. Wenn die schnelle Suche Priorität hat und dafür das einfügen oder Löschen etwas länger dauern darf, ist der AVL-Baum eine Alternative. Der AVL-Baum ist nach den russischen Mathematikern G. M. Adel'son-Velskii und E. M. Landis benannt. Der AVL-Baum ist ein ausbalancierter Baum und stellt sicher, daß für jeden Konten der Höhenunterschied (Balancefaktor) zwischen seinen beiden Teilbäumen nicht größer als 1 ist.

Wie der Binärbaum hat jeder Knoten zwei Zeiger (subtree[1] bzw. rechter Teilbaum und subtree[0] bzw. linker Teilbaum. Der rechte Teilbaum enthält alle Elemente die größer als das aktuelle Element sind und der linke Teilbaum alle kleineren. Das Suchen in dem AVL-Baum ist damit identisch zu der Suche in dem Binärbaum.


Zusätzlich enthält jeder Knoten einen Wert, der den Höhenunterschied seiner beiden Teilbäume angibt. Der Wert kann 0 sein (beide Teibäumd habe die gleiche Höhe), 1 (Die Höhe von subtree[1] bzw. des rechen Teilbaums ist größeror als die höhe von subtree[0] bzw. des linken Teilbaums) oder -1 (Die Höhet von subtree[0] bzw. des linken Teilbaums ist größer als die Höhe von subtree[1] bzw. des rechten Teilbaums). Für jede Änderung des Baumes (Einfügen oder Löschen von Knoten) muß geprüft werden, ob dadurch der Balancefaktor einen unzulässigen Wert bekommt. Wenn ja, müssen die Teilbäume so umgeordnet werden, daß der Baum wieder ausbalanciert ist. Dazu dienen 3 3 einfache Operationen. Das Kürzel in Klameren findet sich auch in den Beispielen wieder.

Einfache Rotation mit balanciertem r (D11)


Die Wurzel r des zu großen Teilbaums wandert an die Stelle der bisherigen Wurzel s. Wenn r ein größeres Element enthält, ergibt s die neue Wurzel des kleineren Teilbaums von r.

Einfache Rotation mit unbalanciertem r (D12)


Auch hier vertauschen zwei Element ihre Position, der Teilbaum r ist aber nicht ausbalanciert.

Doppelte Rotation (D13)


Bei der doppelten Rotation wandert der Knoten p zwei Ebenen nach oben, wobei die beiden darüebr stehenden Elternknoten r und s die Wurzeln der beiden Teilbäume unter p werden.

Beim Einfügen wird auch ähnlich wie bei einem Binärbaum für jeden Knoten neu entschieden, ob in dem Teilbaum für die kleineren Elemente (A3) oder in dem Teilbaum für die größeren (A4) eingefügt wird. Sind die beiden Teilbäume dieses Knotens unterschiedlich tief, so wird dieser Knoten gemerkt (A3, A4). Nach dem Einfügen ist das am dichtesten über dem eingefügten Element stehende Element mit unterschiedlich hohen Teilbäumen gemerkt. Wenn nun durch das Einfügen der Tiefenunterschied zwischen beiden Teilbäumen auf 2 angestiegen ist, kann durch eine einfache Rotation dies ausgeglichen werden. Da sich dadurch die maximale Tiefe ab diesem Element nicht ändert, müssen die darüber stehenden Knoten nicht angepaßt werden.

Das Löschen eines Knotens ist deutlich aufwendiger. Wenn durch das Entfernen eines Knoten der Höhenunterschied auf 2 steigt, verändert sich durch das Umsorteiren (einfache und doppelte Rotation) die maximale Tiefe dieses Teilbaums. Deshalb kann auch in den darüber befindlichen Knoten ein neues Umsorteiren nötig werden. Deshalb baut der Algorithmus einen Stack auf, in dem er die Knoten und die Richtung speichert, die er bei der Suche nach dem zu löschenden Element durchläuft. In dem Feld pa sind die Knoten gespeichert, in dem Feld a die Richtung. Nachdem der Knoten gelöscht wurde, kann mit diesem Stack der Baum rückwärts bis zur Wurzel durchwandert werden. Für jeden Knoten wird die neue Balance errechnet und falls nötig werden die Knoten mit den oben aufgeführten Operationen (einfache und doppelte Rotation) umsortiert.

Beispielcode
Home Botanik: Basisalgorithmen für Container Binärbaum Abstrakte Container


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum