Vorlesung Informatik 2 - Teil B: Theorie

4.10 AVL Bäume - Knoten löschen

Wir schauen uns noch an, wie man einen Knoten in einem AVL Baum löscht. Dabei sind drei Fälle zu unterscheiden:

  1. Der zu löschende Knoten ist ein Blatt
    der Knoten wird entfernt und für den Vaterknoten die Balance geprüft um ggf. zu rotieren.
  2. Der zu löschende Knoten hat ein Kind:
    das Kind ersetzt den gelöschten Knotens.
  3. Der zu löschende Knoten hat zwei Kinder:
    der gelöschte Knoten wird durch einen symmetrischen Nachbarn ersetzt. Die Symmetrischen Nachbarn eines Knotens im Suchbaum sind sein Vorgänger bzw. Nachfolger in der in-Order, also die Knoten vor bzw. nach ihm in der natürlichen Reihenfolge.
    Der Nachfolger eines Knotens ist der kleinste Knoten im rechten Teilbaum, sein Vorgänger ist der größte Knoten im linken Teilbaum.
In jedem der drei Fälle muss nach dem Löschen die Balance entlang des absoluten Pfades des gelöschten Knotens geprüft und ggf. rotiert werden. 

Beispiele für Fall 1 - Löschen des Knotens N:

                M
                 /  \
                L    P
            /     /  \
            B     N  T
                      /  \
                     S   W

Nach dem Löschen von N muss P nach links rotiert werden:


                  M
                 /  \
                L    T
            /     /  \
            B     P  W
                   \  
                     S   

Beispiele für Fall 2 - Löschen des Knotens L:

                   M
                 /  \
                L    P
            /     /  \
            B     N  T
                      /  \
                     S   W

Nach dem Löschen von L muss M nach links rotiert werden:

                   P
                 /  \
               M     T
            /  \   /  \
            B    N  S W
                     
Beispiele für Fall 3 - Löschen des Knotens M:

                   M
                 /  \
                L    P
            /     /  \
            B     N  T
                      /  \
                     S   W

Nach dem Löschen wird der symmetrische Nachfolger N an die Stelle von M platziert. Dabei wird von der bisherigen Position des Knotens N aufwärts die Balance geprüft und P nach links rotiert:

                   N
                 /  \
               L     T
            /     /  \
            B      P W \ S
                     

Der AVL Baum ist die einfachste Implementierung eines ausgeglichenen Suchbaums und gut geeignet um das Prinzip zu studieren. In der tatsächlichen Anwendung findet man AVL Bäume eher selten, statt dessen werden Rot-Schwarz Bäume bzw. B-Bäume verwendet, die in den nächsten Kapiteln behandelt werden. 

Lehrvideo (Youtube)