EinfügeFolge für AVL-Baum mit vielen/wenigen Rotationen

[Nikolas]

Moin

Ich schreibe am Montag meine Info-Klausur und bin auf eine schöne Frage gestoßen, die ich gerne an euch weiterleiten würde :)

Besser gesagt soll eine allgemeine Beschreibung gegeben werden, wie man n Elemente einfüllt, dass möglichst viele oder keine Rotationen auftauchen.

Keine Rotation sollte eigentlich auftreten, wenn man immer aufpasst, dass man die AVL-Bedingung nie verletzt, also erst n/2, dann n/4, 3*n/4 usw. Also im Endeffekt so eine Art Reihenfolge wie bei einem Divide&Conquer. (Nur weiss ich noch nicht, wie ich so was geschlossen darstellen soll.

Viele Rotationen erwarte ich bei einer sortieren Reihenfolge, damit alles schön denaturiert.

Nur weiss ich nicht, ob das stimmt und wie man zeigt, dass es so die Extremen darstellungen sind. (Bei der ersten Version ists eigentlich klar, dass da keine Rotationen auftauchen)