🔁 Die 4 Rotationen in AVL-Bäumen – einfach erklärt 🌳

Einleitung

AVL-Bäume gehören zu den selbstbalancierenden binären Suchbäumen. Sie sorgen dafür, dass der Baum nie zu schief wird, damit die Suche, das Einfügen und das Löschen stets in logarithmischer Zeit O(log n) möglich sind.

📐 Was ist ein Balance-Faktor?

Jeder Knoten in einem AVL-Baum speichert einen Balance-Faktor, berechnet als:

Balance-Faktor = Höhe(linker Teilbaum) – Höhe(rechter Teilbaum)

Erlaubt sind nur:

• ✅ -1
• ✅ 0
• ✅ +1

Sobald ein Knoten den Balance-Faktor +2 oder -2 erreicht, wird der Baum unausgeglichen – und muss per Rotation wieder ausgeglichen werden. 🌪️

🔁 Die vier AVL-Rotationen

🔁 1. Links Rotation ↙️

🔁 2. Rechts-Rotation ↙️

🔁 2. Doppelrotation Rechts Links ↙️

🔁 2. Doppelrotation Links Rechts ↙️