rhino didactics Logo

mit Google im Archiv der rhino didactics

Ausgabe 29 vom 1. Juni 2009 (als PDF):

20. Mai 2009 – Johannes Pieper

Beispiele für AVL-Bäume

Nach dem Artikel über Beispiele für binäre Suchbäume (rhino didactics Nr. 28, Seite 2, linke Spalte – rhinodidactics.de/Ausgaben/ausgabe-28.pdf) erscheint nun die Fortsetzung für AVL-Bäume.

AVL-Baum – Monatsnamen
Abbildung 1: AVL-Baum – Januar bis Juni ==> einfache Rotation

Die Besonderheit beim Aufbau von AVL-Bäumen besteht im Einsatz der Rotation und der Doppelrotation in den Fällen, dass der AVL-Baum durch einen neuen Knoten nicht mehr ausbalanciert ist. Um dies beispielhaft zu verdeutlichen, werden Daten benötigt, die diese Effekte beim Aufbau des AVL-Baums bereits beim Einfügen weniger Elemente hervorrufen.

AVL-Baum – Monatsnamen
Abbildung 2: AVL-Baum – Januar bis Juni – gekippte Knoten verdeutlichen die Balancierung

Ein bekanntes Beispiel stellt das Einfügen der Monatsnamen in ihrer zeitlichen Abfolge (also Januar, Februar, März, etc.) in einen Baum dar, der lexikographisch sortiert sein soll.

AVL-Baum – Monatsnamen
Abbildung 3: AVL-Baum – Januar bis Juni – Pfeile verdeutlichen die Balancierung

Das Beispiel hat Ralf Hartmut Güting in seinem Buch Datenstrukturen und Algorithmen (S. 126f, Teubner, Stuttgart, 1992) beschrieben. Werden die Monatsnamen im Baum lexikographisch geordnet, so tritt beim Einfügen der Elemente Juni und November eine einfache Rotation und beim Einfügen der Elemente August und Oktober eine Doppelrotation auf.

AVL-Baum – Monatsnamen
Abbildung 4: AVL-Baum – Januar bis August – Einfügen »August« ==> Doppelrotation
AVL-Baum – Monatsnamen
Abbildung 5: AVL-Baum – Januar bis August – Doppelrotation ==> gekippte Knoten verdeutlichen die Balancierung

Ein weiteres Beispiel bemüht deutsche Staatsmänner und -frauen als Grundlage, wie im Beispiel für binäre Suchbäume (siehe rhinodidactics.de/Artikel/2009-03-02_beispiele_binaere_suchbaeume-pieper.html) dokumentiert. Für die – wiederum lexikographisch geordneten – AVL-Bäume wählt man die Bundeskanzler aus, die in ihrer zeitlichen Reihenfolge eingefügt werden sollen. Hier gibt es eine Doppelrotation beim Einfügen von Kohl und eine einfache Rotation bei Kiesinger. Fügt man daran noch die Bundespräsidenten an, so muss beim Einfügen von Lübke, Heinemann und Carstens jeweils eine einfache Rotation durchgeführt werden.

AVL-Baum – Monatsnamen
Abbildung 6: AVL-Baum – Januar bis August – Doppelrotation ==> Pfeile verdeutlichen die Balancierung
© Redaktion rhino didactics