i

Einen Knoten aus einem Binärbaum löschen

Neues Klassendiagramm

Analog zum Einfügealgorithmus, ist natürlich auch unser Löschalgorithmus etwas, was unserem Binärbaum im Allgemeinen gut zu Gesicht steht:

Klassendiagramm des Binärbaums mit delete-Prozedur

Wie auch bei der Einfügeprozedur, kannst Du dir zunächst selbst versuchen, einen Algorithmus zu überlegen. Dieser ist zwar etwas komplizierter, als add, aber wenn Du zumindest siehst, wo das Problem liegt, verstehst Du den unten vorgestellten delete besser. Und vielleicht gelingt es dir ja trotzdem.

Problem

Um ein Element aus einem Binärbaum zu löschen, müssen wir es zunächst finden. Wenn wir den Schlüssel nun gefunden haben, können wir ihn natürlich löschen, aber was passiert dann? Dann haben wir entweder die Wurzel gelöscht, und somit keinen Baum mehr:

Problem beim löschen der Wurzel

Löschen wir einen inneren Knoten, haben wir plötzlich Knoten, die keinen Vaterknoten mehr haben und somit praktisch nicht mehr Teil unseres Baums sind. Schließlich gibt es keine Möglichkeit, sie mithilfe der existierenden Zeiger von der Wurzel zu erreichen:

Problem beim löschen eines inneren Knotens

Löschen wir ein Blatt, haben wir kaum ein Problem. Das einzige, was hier stört ist, dass wir einen überflüssigen Zeiger rumfliegen haben:

Problem beim löschen eines Blattes

Idee der Lösung

Um unsere Löschung jetzt korrekt durchzuführen, müssen wir die Fälle einzeln abhandeln:

Bei der Löschung unseres Blatts, können wir natürlich einfach auch den Zeiger löschen:

Lösungsidee beim löschen eines Blattes

Wollen wir einen inneren Knoten löschen, können wir zwischen zwei Sonderfällen unterscheiden, nämlich einmal dem simplen, in dem unser Knoten nur ein Kind hat:

Knoten mit nur einem Kind

In dem Fall können wir einfach das eine Kind des zu löschenden Knoten an die Stelle des zu löschenden Knoten setzen. Die Position der Kinder und Kindeskinder des entsprechenden Knotens ist natürlich weiterhin korrekt und so wie wir unsere Binärbäume aufbauen passt auch die Position des verschobenen Knotens.

Lösungsidee beim Löschen eines inneren Knotens mit einem Kind

Das selbe funktioniert auch, wenn die Wurzel nur ein Kind hat:

Löschen der Wurzel mit nur einem Kind
Lösungsidee beim Löschen der Wurzel mit nur einem Kind

Hat ein Knoten zwei Kinder, können wir ihn am besten durch einen direkten Nachbarn innerhalb des Unterbaums des zu löschenden Knotens ersetzen. Mit direktem Nachbarn ist der Knoten innerhalb der genannten Knotengruppe gemeint, der entweder der nächstgrößte oder nächstkleinste (das ist egal) gemeint. Man nennt diesen Nachbarn in-order Nachbar.

Löschen eines Knoten mit zwei Kindern
In-order Nachbar
Lösungsidee beim Löschen eines Knoten mit zwei Kindern

Hat der in-order Nachbar unseres zu löschenden Knoten selbst Kinder, kann er höchstens ein Kind haben (sonst wäre eines der Kinder der in-order Nachbar).

Wenn wir diesen also verschieben, löschen wir unten im Prizip wieder entweder ein Blatt oder einen Knoten mit nur einem Kind und können uns auf unsere Ideen von zuvor zurückziehen.

Aufgabe 13

(a) Nutze die Idee des Algorithmus, um von Hand die Knoten 3, 7 und 35(in dieser Reihenfolge) zu löschen.

(b) Wie viele Vergleiche werden benötigt, um ein Blatt zu löschen? Wie viele andere Schritte?

(c) Wie viele Vergleiche werden benötigt, um einen inneren Knoten zu löschen? Wie viele andere Schritte?

Der Algorithmus

Wenn Du nicht bereits selbst einen Algorithmus entworfen und implementiert hast, solltest Du versuchen, den gerade vorgestellten Algorithmus selbst zu implementieren. Damit Du den Algorithmus aber auf jeden Fall einmal gesehen hast, siehst Du im folgenden eine mögliche Implementation:

class Knoten(object):
    def __init__(self, wert):
        self.wert = wert
        self.linkesKind = None
        self.rechtesKind = None

    def add(self, wert):
        if wert < self.wert:
            if self.linkesKind == None:
                self.linkesKind = Knoten(wert)
            else:
                self.linkesKind.add(wert)
        else:
            if self.rechtesKind == None:
                self.rechtesKind = Knoten(wert)
            else:
                self.rechtesKind.add(wert)

    def delete(self, key):
        if key < self.wert:
            if self.linkesKind != None:
                neuesLinkes = self.linkesKind.delete(key)
                self.linkesKind = neuesLinkes
                return self
            else:
                return None
        elif key > self.wert:
            if self.rechtesKind != None:
                neuesRechtes = self.rechtesKind.delete(key)
                self.rechtesKind = neuesRechtes
                return self
            else:
                return None
        else:
            if self.linkesKind == None:
                return self.rechtesKind
            elif self.rechtesKind == None:
                return self.linkesKind
            else:
                nachbar = self.nachbar()
                self.wert = nachbar.wert
                self.rechtesKind = self.rechtesKind.delete(self.wert)
                return self

    def nachbar(self):
        if self.rechtesKind.linkesKind == None:
            return self.rechtesKind
        else:
            return self.rechtesKind.kleinstesKind()

    def kleinstesKind(self):
        if self.linkesKind.linkesKind == None:
            return self.linkesKind
        else:
            return self.linkesKind.kleinstesKind()


class Baum(object):
    def __init__(self):
        self.wurzel = None

    def add(self, wert):
        if self.wurzel == None:
            self.wurzel = Knoten(wert)
        else:
            self.wurzel.add(wert)

    def delete(self, key):
        if self.wurzel == None:
            return
        self.wurzel = self.wurzel.delete(key)

Da wir zum implementieren der delete Prozedur einige Hilfsprozeduren einführen mussten, sollten wir diese nun auch in unser Klassendiagramm aufnehmen:

Klassendiagramm des Binärbaums mit Hilfsprozeduren

Suche

v
4.4.3.4.2
inf-schule.de/algorithmen/suchbaeume/binaerbaum/andere/loeschen

Rückmeldung geben