Programmierung, Algorithmen und Datenstrukturen

Abb. 5.60. Eine einfache Rotation.

Durch Umhängen des Unterbaumes B – dazu müssen lediglich zwei Referenzen verändert werden – wird die AVL-Eigenschaft wiederhergestellt. Man kann sich vorstellen, dass man den tieferen Knoten y fasst und ihn hochhebt, um ihn zur neuen Wurzel zu machen. Dazu muss man die Verbindung zu B trennen und B dafür als rechten Sohn von x einhängen. Vorher wie nachher befinden sich alle Elemente des Unterbaumes B zwischen x und y, daher ist der neue Baum immer noch ein binärer Suchbaum. An den „Höhenlinien“ der Figur kann man ablesen, dass nach dem Umhängen sowohl x als auch y den d-Wert 0 haben.

AVL-Bäume sind nach ihren ...