home  |  suche  |  kontakt/johner  |  institut 
studierende  |  tech-docs  |  mindmailer 

Löschen von Elementen in einem B-Baum

Man unterscheidet folgende Fälle:

1. Löschen eines Elementes aus einem Blatt

    a) Genügend Elemente vorhanden (nach Löschen gültiger B-Baum)

    b) Nicht genügend Elemente vorhanden => Unterlaufbehandlung

        i) Unterlaufbehandlung durch Reorganisation

        ii) Unterlaufbehandlung durch Zusammenlegung von Seiten 

2. Löschen von Elementen aus einen Knoten, der kein Blatt ist

    Man ersetzt das Element entweder durch

    a) das kleinste Element des rechten Teilbaums oder

    b) das größte Element des linken Teilbaums

 

Beispiel für Fall 1.a)

Die 31 kann ohne Unterlaufbehandlung gelöscht werden.

Beispiel für Fall 1.b) i)

Durch das Löschen der 22 befinden sich im rechten Blatt weniger als die Mindestanzahl von 2 Elementen (nur die 24 verbleibt). Allerdings befinden sich im Nachbarblatt mehr als die Mindestanzahl, so dass ein Ausgleich vorgenommen werden kann. Die Elemente beider Blätter (13, 14, 17, 18 und 24) einschließlich des eingeschlossenen Elternelements (20) werden neu verteilt und ein mittleres Element, das neue Elternelement, nämlich hier die 18 gewählt.

Beispiel für Fall 1.b) ii)

Wird in diesem Fall die 22 gelöscht, so verbleiben im rechten Blatt nicht genügen Elemente (nur die 24). Auch die Nachbarseite (13, 14) kann dies nicht ausgleichen, weshalb die beiden Seiten einschließlich des Elternelements (20) zusammen gelegt werden.