Antwort mit KI erzeugt
AVL-Bäume sind selbstbalancierende Binärbäume, bei denen der Höhenunterschied zwischen den beiden Unterbäumen eines jeden Knotens nie mehr als eins beträgt. Einfügungen und Löschungen können zu einer Neubalancierung des Baums führen, um diese Eigenschaft beizubehalten.
Einfügen von 5:
Wir beginnen mit einem leeren Baum und fügen 5 ein. Da der Baum leer ist, wird 5 zur Wurzel des Baums.
5
/ \
ø ø
Einfügen von 4:
Als nächstes fügen wir 4 ein. 4 ist kleiner als 5, also fügen wir ihn als linken Kindknoten von 5 ein. Der Baum bleibt ausgeglichen.
5
/ \
4 ø
/ \
ø ø
Einfügen von 3:
Nun fügen wir 3 ein. Dies wird links von 4 eingefügt. Dieser Schritt führt zu einem Ungleichgewicht, da der linke Teilbaum jetzt eine Höhe von 2 hat und der rechte Teilbaum eine Höhe von 0 hat. Wir müssen eine Rotation durchführen, um den Baum auszugleichen. Eine rechte Rotation bei 5 wird durchgeführt.
Ausgeglichener Baum nach Einfügen von 3 und Rotation:
4
/ \
3 5
/ \ / \
ø ø ø ø
Einfügen von 1:
Als nächstes fügen wir 1 ein, was unten links von 3 eingefügt wird. Der Baum bleibt ausgeglichen.
4
/ \
3 5
/ \ / \
1 ø ø ø
/ \
ø ø
Einfügen von 2:
Schließlich fügen wir 2 ein, was als rechtes Kind von 1 eingefügt wird. Dies führt zu einem Ungleichgewicht im Baum, bei dem der linke Teilbaum (insbesondere der Teilbaum, der 3 als Wurzel hat) einen Höhenunterschied von mehr als eins aufweist. Eine Links-Rechts-Doppeldrehung ist erforderlich, bei 3 eine linke Rotation und dann bei 4 eine rechte Rotation.
Ausgeglichener Baum nach Einfügen von 2 und Doppelrotation:
3
/ \
1 4
\ / \
2 ø 5
/ \ / \
ø ø ø ø
Dies ist der endgültige AVL-Baum nach Einfügen der Schlüssel 5, 4, 3, 1, 2 in den anfangs leeren Baum, einschließlich der notwendigen Rotationen, um den Baum nach dem Einfügen jedes Schlüssels auszugleichen.
