Stefan Röttger

← 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 →