0 Daumen
324 Aufrufe

Aufgabe:

Geben Sie den AVL-Baum an, der durch Einfügen der Schlüssel 5, 4, 3, 1, 2 in den anfangs leeren Baum entsteht. Geben Sie den (neu) ausbalancierten Baum nach jedem Einfügen an.

Achten Sie darauf die (leeren) Blätter mit anzugeben.

Avatar von

1 Antwort

0 Daumen

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.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community