|
Die bis jetzt behandelten Algorithmen waren recht unkompliziert im Vergleich zum Löschen einzelner Elemente aus einem binären Suchbaum. Hier kommt es nämlich darauf an, wo sich der Knoten befindet bzw. wieviele Nachfolger er hat. Hierzu ein Beispiel:
. Am einfachsten ist das Löschen eines Knotens ohne Nachfolger (C, L, P), weil nur eine Verkettung gelöscht werden muß.
. Beim Löschen von Knoten mit nur einem Nachfolger (A, R, H, M) muß dieser nur ausgekettet, und eine Verkettung zwischen dem Vorgänger und dem Nachfolger erstellt werden.
. Auch das Löschen eines Knotens, von dem einer der Nachfolger keinen Nachfolger hat (N), ist kein Problem, da man den Knoten durch diesen Nachfolger ersetzen kann.
. Das einzige Problem kann es weiter oben im Baum geben, wo jeder Nachfolger weitere Nachfolger besitzt. Das Löschen eines solchen Knotens (E) erfolgt in drei Schritten:
1. Suchen des nächstgrößeren Knotens (H); dieser kann nur einen Nachfolger haben
2. Ausketten dieses Knotens (nach den oben genannten Methoden)
3. Ersetzen des zu löschenden Knotens durch den größeren
Nachteil dieser Funktion ist, daß bei vielen "Löschen - Einfügen" Paaren ein leicht unausgeglichener Baum entsteht. Dieses Problem kann man mittels "lazy deletion" lösen. Hier wird ein Knoten nicht wirklich gelöscht, sondern nur als gelöscht markiert, und dadurch die Baumstruktur erhalten. Das Problem, das dabei entsteht, ist die Vergeudung der Zeit. Dies kann durch regelmäßiges Neuaufbauen des Baumes, mit Weglassen der markierten Knoten, verhindert werden.
|
