TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 17

Gegeben sei ein AVL-Baum T mit n Knoten, in denen die Schlüssel $S={s_{\text{1}},s_{\text{2}},...,s_{\text{n}}}$ gespeichert sind. Der AVL-Baum sein entstanden, indem die Schlüsselmenge S in einer bestimmten Reihenfolge in einen anfänglich leeren Baum eingefügt wurden. In der Regel müssen hierbei einige Rotationsoperationen durchgeführt werden. Gibt es zu jedem solchen Baum T eine Einfügungsreihenfolge der Schlüsselmenge S, die zum gleichen AVL-Baum T führt, jedoch keine einzige Rotation notwendig macht? Begründen Sie ihre Antwort.

Lösung

Ja.

Begründung: In den man $S={s_{\text{1}},s_{\text{2}},...,s_{\text{n}}}$ so anordnet, das die geordnete Liste der Levelorderdarstellung von T entspricht. Dadurch baut man den Baum zeilenweise (bzw. ebenenweise) auf und keine der AVL-Baum-Regeln ist dabei verletzt.

Lösung von Michael