C-Programmierung
Baumrotation
← Balancierte Bäume | ● | Balancierter Aufwand →
Eine häufige Umstrukturierung ist die Baum-Rotation:
left q -----> p / \ rot / \ p C A q / \ rot / \ A B <----- B C right
AVL Bäume können mit dieser Operation balanciert werden. Wurde ein Knoten eingefügt, so werden alle Elternknoten auf die AVL Eigenschaft hin überprüft. Bei Nichterfüllung werden entsprechende Baum-Rotationen durchgeführt.
Beispiel AVL Baum:
6 8 5 --> 5 --> 5 / \ insert / \ right / \ 3 8 3 8 3 7 / / / \ 7 7 6 8 / 6
← Balancierte Bäume | ● | Balancierter Aufwand →