Baum Knoten Baumes hohe Knotens

AVL-Baum löschen eines Knotens: Balancierungen

Von: , Frage gestellt am So, 1. Jul 2007

Moin zusammen.

Soweit ich das mit den AVL-Bäumen verstanden habe, kann es ja sein, dass wenn ich ein Knoten lösche, dass dann manchmal sogar mehr als eine Rebalancierung nach sich zieht.
Das ganze kann ich mir aber nicht anschaulich begründen, sondern ich finde das nur logisch, weil sich die Höhe des Baumes ja um eins verringert.
Ich bin also auf der Suche nach einem Beispiel, kann mir jemand von euch so einen Baum beschreiben, bei dem ich einen Knoten lösche und mehr als eine Balancierung nach sich zieht?

Es dankt:
Disap

1 Antworten zu dieser Frage

1. Antwort von nach 5 Tagen 1 hilfreich

   Re: AVL-Baum löschen eines Knotens: Balancierungen

   Hallo,
   
   an dem folgenden, rekursiv-definierten Baum ist es zu sehen:
   
   A_1=Genau eine Wurzel
   A_2=Eine Wurzel, links A_1
   A_3=Eine Würzel, links A_2, rechts A_1
   A_n=Eine Würzel, links A_n-1, rechts A_n-2
   
   Wenn Du Dir z.B. den Baum A_7 mal aufzeichnest und das rechteste Blatt löscht,
   dann muss an jedem Knoten auf dem Pfad zur Wurzel rotiert werden.
   
   Viele Grüße
   Thorsten Moin zusammen.
   
   ... AVL-Bäumen ... kann mir
   jemand von euch so einen Baum beschreiben, bei dem ich einen
   Knoten lösche und mehr als eine Balancierung nach sich zieht?
   
   Es dankt:
   Disap
   

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!