5. Löschen in einen Bayer-Baum

Allgemeines

Beim Löschen wird ebenfalls zuerst der Baum durchsucht, bis der Knoten gefunden wurde, in dem sich das zu löschende Element befindet.
+ -

Beispiel

Das Element mit dem Schlüssel 14 soll gelöscht werden.
Der Knoten aus den das Element 14 gelöscht werden soll ist

Danach befindet sich in dem Knoten nur noch ein Element. Damit der Baum weiterhin ausgeglichen bleibt (Anzahl Element im Knoten < n), müssen zwei Knoten zusammengefügt werden.

Wenn ein Element aus einem Knoten gelöscht wird, müssen zwei Situationen unterschieden werden:

Das zu löschende Element befindet sich in einem Blatt. Das Löschen wird dann dadurch realisiert, daß alle Elemente, die sich rechts von dem zu löschenden Element befinden, um eine Position nach links geschoben werden.

Knoten vor dem Löschen:

13 14 15 16

Knoten nach dem Löschen:

13 15 16
Das zu löschende Element befindet sich nicht in einem Blatt. Das zu löschende Element muß dann durch ein geeignetes Element aus einem nachfolgenden Knoten ersetzt werden.

In beiden Fällen muß überprüft werden, ob die Anzahl der Elemente im Knoten nach dem Löschen kleiner n wird (s.o.). Wenn der Baum nicht mehr ausgeglichen ist (Anzahl Element im Knoten < n), wird mit Hilfe des rechten oder linken Nachbarn des Knoten der Baum wieder ausgeglichen.

Dabei werden wieder zwei Situationen unterschieden:

Der Nachbar kann mindestens ein Element abgeben (Anzahl Element im Knoten > n) ohne das der Nachbar unausgeglichen wird. Die Elemente beider Knoten werden dann so verteilt, daß beide Knoten die gleiche Anzahl an Elementen haben.
Der Nachbar enthät nur n Elemente. Der Knoten, in dem sich das zu löschende Element befand (bei dem gilt: Anzahl Element im Knoten < n) wird mit dem Nachbarn zu einem Knoten verbunden. Zusammen mit einem Element aus dem Knoten eine Ebene höher, ergibt sich ein Knoten mit 2n Elementen. Dabei kann in dem nächst höheren Knoten wieder ein Defiziet entstehen wodurch sich das Löschen bis zur Wurzel fortsetzten kann.

Wie beim Einfügen können beim Löschen wieder 4 Fälle auftreten:

1. Mit Hilfe des linken Nachbarn, für den vor dem Ausgleich gilt: Anzahl Element im Knoten > n

2. Mit Hilfe des linken Nachbarn, für den vor dem Ausgleich gilt: Anzahl Element im Knoten = n

3. Mit Hilfe des rechten Nachbarn, für den vor dem Ausgleich gilt: Anzahl Element im Knoten > n

4. Mit Hilfe des rechten Nachbarn, für den vor dem Ausgleich gilt: Anzahl Element im Knoten = n

+ -

Der Löschenalgorithmus



Procedure Delete(Element: TElement);

 Procedure Del(Var PageLink: Longint; Neighbour: Longint; left: Boolean; 
               Var Change: Boolean;
               Var sink: Boolean; Var DownElement: TElement);

 Begin
      Implementierung
 End;

Var RootChanged: Boolean;
    RootElm: TElement;
    RootSink: Boolean;
    Page: PPage;

Begin
     RootChanged:=False;
     Del(RootLink,0,True,RootChanged,RootSink,RootElm);
     { Wurzel wurde geändert -> speichern }
     If RootChanged Then
      SavePage(RootLink,RootPage);
     { Wurzel wurde geleert }
     If RootPage^.Anzahl<=0 Then
     Begin
          { alte Wurzel löschen }
          DisposeBackPage(RootLink);
          { neue Wurzel wird untergeordnete Knoten von alter Wurzel }
          RootLink:=RootPage^.Elemente[0].Link;
          Dispose(RootPage);
          RootPage:=Nil;
          RootPage:=LoadPage(RootLink);
     End;
End;

Prozedurschnittstelle:


Procedure Delete(Element: TElement);

Löscht das "Element" aus dem Bayer-Baum.

+ -

Implementierung der Prozedur "Del":

Die Prozedur "Del" übernimmt das eigentliche Löschen eines Elementes. Sie wird solange rekursiv aufgerufen wobei immer eine neue Page eingelesen wird, bis das zu löschende Element gefunden wurde.
Wenn die einzulesende Page die Position "Null" im Hintergrundspeicher hat, ergibt sich daraus, daß sich das zu löschende Element gar nicht im Baum befindet.

Ist die Position der einzulensenden Page nicht "Null", wird in der Page nach dem zu löschenden Element durchsucht.

Wurde das Element nicht gefunden, wird die Prozedur "Del" rekursiv aufgerufen, um in einem Unterbaum weiterzusuchen.

Wenn das Element gefunden wurde, muß es gelöscht werden. Beim Löschen muß unterschieden werden, ob die Page ein Knoten oder ein Blatt ist.

Dannach kann es passieren, daß die Anzahl der Elemente in der Page unter n fällt. In dem Fall wird die Page mit einem Nachbarn verbunden.

+ -


Procedure Del(Var PageLink: Longint; Neighbour: Longint; left: Boolean; 
              Var Change: Boolean;
              Var sink: Boolean; Var DownElement: TElement);

Var Page: PPage;
    Pos: Integer;
    Changed, sunk: Boolean; 
   { sunk gibt an, ob ein Element aus der Page entfernt wurde }
    l,r,I: Longint;

Begin
     { das Element wurde nicht im Baum gefunden }
     If PageLink=Null Then
      Sink:=False
     Else
     Begin
	  { Page einlesen }
          Page:=LoadPage(PageLink);
          Changed:=False;
          sunk:=False;
	  { Element in Page suchen }
          If SucheInPage(Page,Element,Pos) Then
          Begin
               l:=Page^.Elemente[Pos-1].Link;
               r:=Page^.Elemente[Pos].Link;
               If l=Null Then { Page ist ein Blatt }
                sunk:=True { Element entfernen }
               Else
               Begin
	            { Page ist ein Knoten und Element wird durch das
		      groeßte Element des linken Unterbaumes
		      ersetzt }
                    Greatest(l,Page^.Elemente[Pos],r,false,Changed,
                                    sunk,Page^.Elemente[Pos]);
                    Changed:=True;
               End;
          End
          Else { Element wurde nicht gefunden }
              If Pos=0 Then	      
              Begin
		   { fuer einen eventuellen Ausgleich in einem rekursiven
		     Aufruf, kann nur ein rechter Nachbar verwendet
		     werden, weil die Position 0 ist }		     
                   Del(Page^.Elemente[0].Link,Page^.Elemente[1].Link,
                       False,Changed,sunk,Page^.Elemente[1]);
                   Pos:=1;
              End
              Else 
                  Del(Page^.Elemente[Pos].Link,Page^.Elemente[Pos-1].Link,
                      True,Changed,sunk,Page^.Elemente[Pos]);
          { aus der Page wurde ein Element entfernt,
            das entfernte Element befand sich an der 
	    Position "Pos" }
          If sunk Then
          Begin
               { Anzahl der Elemente der Page um eins verringern }
               Dec(Page^.Anzahl);
	       { alle Elemente um eine Position nach links verschieben }
               For I:=Pos to Page^.Anzahl do
                Page^.Elemente[I]:=Page^.Elemente[I+1];
 	       { ist ein Defizit aufgetreten 
                 (in der Wurzel erlaubt) }
               If (Page^.Anzahl<n) and (PageLink<>RootLink) Then
               Begin
		    { Ausgleich mit dem linken Nachbarn }
                    If left Then
                     CompensateLeft(Page,PageLink,neighbour,sink,DownElement)
                    Else
		    { Ausgleich mit dem rechten Nachbarn }
                        CompensateRight(Page,PageLink,neighbour,sink,DownElement);
                    Change:=True;
               End;
               Changed:=True;
          End;
          { Page wurde geändert -> Page speichern }
          If Changed Then SavePage(PageLink,Page);
     End;
End;

Prozedurschnittstelle:


Procedure Del(Var PageLink: Longint; Neighbour: Longint; left: Boolean; 
              Var Change: Boolean;
              Var sink: Boolean; Var DownElement: TElement);

"PageLink" ist die Position der einzulesenden Page im Hintergrundspeicher
"Neighbour" ist die Position des Nachbarn, der für einen möglichen Ausgleich verwendet werden soll
"left" gibt an ob sich der Nachbar links oder rechts befindet
"Change" gibt an, daß eine eingelesene Page verädert wurde
"sink" gibt an, das der "Page" bei einem rekursiven Aufruf ein Elemnt ("DownElement") entnommen wurde
"DownElement" ist das Element, welches bei einem Defizitausgleich verwendet wird (das Elemt aus der näscht höheren Ebene)

+ -

Implementierung der Prozedur "Greatest":

Die Prozedur "Greatest" liest aus einem Teilbaum das größte Element um es in einen Knoten an die Stelle des zu löschenden Elementes zu setzen.

"Greatest" wird solange rekursiv aufgerufen, bis ein Blatt erreicht wurde. Dann wird das größte Element dieses Blattes aus dem Blatt gelöscht und in den Knoten eine Ebene höher eingefügt. Dies wird fortgesetzt, bis der Ursprungsknoten wieder erreicht wurde.

Beim hochreichen des größten Elementes kann es zu einem Defiziet kommen, d.h. es muß wieder ein Ausgleich mit einem Nachbarn stattfinden.


Procedure Greatest(PageLink: Longint; Replace: TElement;
                   Neighbour: Longint; Left: Boolean; Var Change: Boolean;
                   Var sink: Boolean; Var X: TElement);

Var Page: PPage;
    changed: Boolean;
    sunk: Boolean;

Begin     
     Page:=LoadPage(PageLink);
     changed:=False;
     sunk:=False;
     { ist Page ein Blatt ? }
     If Page^.Elemente[0].Link=Null Then
     Begin
          { das zu loeschende Element wird durch das 
             groeßte Element der Page ersetzt }
          Replace.Key:=Page^.Elemente[Page^.Anzahl].Key;
          Replace.Info:=Page^.Elemente[Page^.Anzahl].Info;
          { Pagegroeße hat sich veraendert }
          sunk:=True;
     End
     Else
         { Page ist ein Knoten }
         Greatest(Page^.Elemente[Page^.Anzahl].Link,Replace,
                  Page^.Elemente[Page^.Anzahl-1].Link,True,changed,sunk,
                  Page^.Elemente[Page^.Anzahl]);
     { hat sich die Groeße der Page verkleinert ? }
     If sunk Then
     Begin
          Dec(Page^.Anzahl);
          { wenn Anzahl der Elemente < n -> Page und Nachbarn zusammenvuegen }
          If Page^.Anzahl<n Then
          Begin
               If left Then CompensateLeft(Page,PageLink,neighbour,sink,X)
                       Else CompensateRight(Page,PageLink,neighbour,sink,X);
               change:=True;
          End;
          changed:=True;
     End;
     If changed Then
      SavePage(PageLink,Page);
End;

Prozedurschnittstelle:


Procedure Greatest(PageLink: Longint; Replace: TElement;
                   Neighbour: Longint; Left: Boolean; Var Change: Boolean;
                   Var sink: Boolean; Var X: TElement);

"Pagelink" ist die Position der Page im Hintergrundspeicher, in der das grösste Element eingefügt werden soll
"Replace" ist das Element, welches ersetzt werden soll
"Neighbour" ist der Nachbar, mit dem gg.f ein Ausgleich stattfinden soll
"left" gibt an ob sich der Nachbar rechts oder links befindet
"Change" gibt an, das sich der Knoten verändert hat
"sink" gibt an, das sich der Knoten verkleinert hat, da das gr&oouml;sste Element aus dem Knoten entfernt wurde
"X" ist das Element, welches zum Ausgleich verwendet werden kann

+ -

Implementierung der Prozedur "CompensateLeft":

Die Prozedur bearbeitet die Fälle 1-2 (siehe Bilder) bei denen zwei Knoten zu einem Knoten zusammengefasst werden.


Procedure CompensateLeft(Page: PPage; PageLink: Longint;
                         LeftLink: Longint; Var sink: Boolean; 
                         Var X: TElement);

Var LeftPage: PPage;
    I, available: Integer;
    Y: TElement;

Begin
     LeftPage:=LoadPage(LeftLink);
     If LeftPage^.Anzahl>n Then
     Begin
          { der linke Nachbar kann einige Elemente abgeben (Fall 1) }
          available:=(LeftPage^.Anzahl-n) div 2;
          If available=0 Then available:=1;
          Y:=LeftPage^.Elemente[LeftPage^.Anzahl-available+1];
          X.Link:=Page^.Elemente[0].Link;
          Page^.Elemente[0].Link:=Y.Link;
          Y.Link:=PageLink;
          { Elemente gleichmaeßig auf beide Knoten berteilen }
          For I:=n-1 downto 1 do
           Page^.Elemente[I+available]:=Page^.Elemente[I];
          Page^.Elemente[available]:=X;
          For I:=1 to available-1 do
           Page^.Elemente[I]:=LeftPage^.Elemente[LeftPage^.Anzahl-available+I+1];
          X:=Y;
          LeftPage^.Anzahl:=LeftPage^.Anzahl-available;
          Page^.Anzahl:=Page^.Anzahl+available;
          { aus hoeheren Knoten wurde kein Element entnommen }
          sink:=False;
     End
     Else
     Begin
          { der linke Nachbar kann alle Elemente aufnehmen (Fall 2) }
          X.Link:=Page^.Elemente[0].Link;
          LeftPage^.Elemente[n+1]:=X;
          { Elemente in linken Nachbarn kopieren }
          For I:=1 to n-1 do
          LeftPage^.Elemente[n+I+1]:=Page^.Elemente[I];
          LeftPage^.Anzahl:=LeftPage^.Anzahl+n;
          { Element aus hoeheren Knoten wurde genommen }
          sink:=True; 
          DisposeBackPage(PageLink);
     End;
     SavePage(LeftLink,LeftPage);
End;

Prozedurschnittstelle:


Procedure CompensateLeft(Page: PPage; PageLink: Longint;
                         LeftLink: Longint; Var sink: Boolean; 
                         Var X: TElement);

"Page" ist die Page, aus dem das Element entfernt wurde
"Pagelink" ist die Position dieser Page
"Leftlink" ist der linke Nachbar der Page
"sink" gibt an, daß dem darüberliegenden Knoten ein Element Zwecks Ausgleich entnommen wurde
"X" ist das Element, welches zum Ausgleich verwendet werden kann

Implementierung der Prozedur "CompensateRight":

Die Prozedur "CompensateRight" bearbeitet die Fälle 3-4 (siehe Bilder) und ist im wesentlichen identisch mit der Prozedur "CompensateLeft".


Procedure CompensateRight(Page: PPage; PageLink: Longint;
          RightLink: Longint; Var sink: Boolean; Var X: TElement);

Var RightPage: PPage;
    I, available: Integer;
    Y: TElement;

Begin
     RightPage:=LoadPage(RightLink);
     If RightPage^.Anzahl>n Then
     Begin
          { Fall 2 }
          available:=(RightPage^.Anzahl-n) div 2;
          If available=0 Then available:=1;
          Y:=RightPage^.Elemente[available];
          X.Link:=RightPage^.Elemente[0].Link;
          RightPage^.Elemente[available+1].Link:=Y.Link;
          Y.Link:=RightLink;
          Page^.Elemente[n]:=X;
          For I:=1 to available-1 do
           Page^.Elemente[n+I]:=RightPage^.Elemente[I];
          For I:=0 to available do
           RightPage^.Elemente[I]:=RightPage^.Elemente[available+I];
          X:=Y;
          RightPage^.Anzahl:=RightPage^.Anzahl-available;
          Page^.Anzahl:=Page^.Anzahl+available;
          sink:=False;
          SavePage(RightLink,RightPage);
     End
     Else
     Begin
          { Fall 4 }
          X.Link:=RightPage^.Elemente[0].Link;
          Page^.Elemente[Page^.Anzahl+1]:=X;
          For I:=1 to RightPage^.Anzahl do
           Page^.Elemente[I+n]:=RightPage^.Elemente[I];
          Inc(Page^.Anzahl,n);
          Sink:=True;
          DisposeBackPage(RightLink);
          SavePage(PageLink,Page);
     End;
End;

Seitenanfang

zurück