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 ...
Get Programmierung, Algorithmen und Datenstrukturen now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
