Was ist ein AVL Tree?

AVL-Trees sind ein spezieller Typ von Binary Search Trees, welche sich ausbalancieren, wenn die Höhendifferenz des linken und rechten Subtree mehr als 1 wird. Wir nutzen Rotationen, um den Ausgleich zu schaffen. Es gibt verschiedene Algorithmen um Trees auszugleichen.

Balancing AVL Trees

BALANCED AND UNBALANCED TREES:
Perfect Tree
Die Knotenstrukur und Leafs des Baumes sind absolut gleichmäßig verteilt

Balanced Tree (O (log n))
Die Differenz zwischen der Höhe des linken und der Höhe des rechten Subtrees ist kleiner gleich 1. FORMEL: height(left) - height(reight) <=1

Unbalanced Tree (O (n))
Die schlechteste Art des Trees (eher eine LinkedList). Besteht, wenn die Höhe des linken und die Höhe des rechten Subtrees größer ist als 1.

SELF-BALANCING-TREES:
Diese Bäume gleichen sich automatisch aus, wenn wir einen Knoten/Wert hinzufügen oder entfernen.

ROTATIONEN:
Es gibt 4 verschiedene Arten von Rotationen. Welche angewandt wird, entscheidet, die Struktur des Baumes (welche Seite schwerer ist).
- LEFT-ROTATION(LL)
- RIGHT-ROTATION (RR)
- LEFT-RIGHT-ROTATION (LR)
- RIGHT-LEFT-ROTATION (RL)

BALANCE FACTOR:
bF= height(L) - height(R)
 Wenn bF= >1 (left-heavy -->RIGHT-ROTATION)
Wenn bF= <-1 (right-heavy -->LEFT-ROTATION)