Stefan Röttger

← Baumknoten Einfügen | ● | Traversierung des Gesamtbaums →

Um einen existierenden Knoten x zu löschen, traversiert man den Baum bis zum Vorgängerknoten.

• Hat der Knoten keine Kinder, so wird die Verknüpfung mit dem Vorgängerknoten gelöscht.
• Andernfalls wird der zu löschende Knoten durch seien linken (oder rechten) Teilbaum ersetzt und der übrig bleibende Teilbaum wird rechtsseitig (bzw. linksseitig) eingehängt.

Beispiel (linksseitig):

             5
     5      -->      .      -->        8
    / \     del                       / \
   3   8           3   8             7   9
  /   / \         /   / \           .
 1   7   9       1   7   9         3
                                  /
                                 1

Beispiel (rechtsseitig):

             5
     5      -->      .      -->    3
    / \     del                   / .
   3   8           3   8         1   8
  /   / \         /   / \           / \
 1   7   9       1   7   9         7   9

Die erstere Variante ist die bessere, da sie eine symmetrischere Baumstruktur erzeugt, und im Extremfall eine Degeneration des Baums zur Liste vermeidet.

Methoden zur Balancierung sind im Normalfall notwendig um die Effizienz des Baums auf Dauer zu gewährleisten.
In manchen Fällen ist die Balancierung auch implizit sichergestellt, wie zum Beispiel in BSP-Trees.

← Baumknoten Einfügen | ● | Traversierung des Gesamtbaums →