|
|
|
|
|
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.
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.
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.
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.
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.
