Einfügen in AVL - Bäumen
Sobald ein BF ( x ) durch eine Einfügung verletzt wird, muss eine Rebalancierung des Baumes durch sogenannte Rotationen durchgeführt werden.
Ausgangspunkt der Rotation ist der nächste Vater des neu eingefügten Knotens mit BF = ? 2 . Dieser Knoten dient zur Bestimmung des Rotationstyps. Er wird durch die von diesem Knoten ausgehende Kantenfolge auf dem Pfad zum neu eingefügten Knoten festgelegt.
Es treten vier verschiedene Rotationstypen auf . Der neu einzufügende Knoten sei X. Y sei der bezüglich der Rotation kritische Knoten - der nächste Vater von X mit