IA-Seminar: Bayer-Bäume

4. Einfügen in einen Bayer-Baum

+ -

Allgemeines

Beim Einfügen eines Elementes in einen Bayer-Baum wird der Baum zunächst von der Wurzel an nach dem einzufügenden Element durchsucht. Wird das Element dabei nicht gefunden, muß es in das Blatt, bei dem die Suche beendet wurde eingefügt werden.

dabei gibt es zwei Möglichkeiten:

das neue Element soll in einen Knoten eingefügt werden, in dem weniger als 2n Elemente enthalten sind (m < 2n)
das neue Element soll in einen Konten eingefügt werden, in dem sich 2n Elemente befinden (m = 2n)

Nur im zweiten Fall hat das Einfügen Einfluss aud die Seitenstruktur und kann die Zuteilung neuer Seiten veranlassen.

+ -

Beispiel

Das Element mit dem Schlüssel 14 soll eingefügt werden
Knoten in den das Element 14 eingefügt werden soll ist

zwischen den Elementen 13 und 15. Der Knoten ist aber schon mit der maximalen Anzahl (2n = 4) an Elementen belegt!
Damit der Baum ausgeglichen bleibt muß der Knoten in zwei Knoten aufgeteilt werden:

Das Element 15 wird in den nächst höheren Knoten eingefügt:

Problem:

Beim Einfügen eines Elementes in den nächst höheren Knoten kann dieser ebenfalls zum Überlaufen gebracht werden. Im schlimmsten Fall würde sich das bis zur Wurzel fortsetzten.

Ein Bayer-Baum wächst also von den Blättern bis zur Wurzel!

+ -

4 Fälle, die beim Einfügen auftreten können

Wenn ein Knoten keine Elemente mehr aufnehmen kann und er deshalb geteilt werden muß, kann man vier Situationen unterscheiden:

1. Vor dem Einfügen ist die Anzahl der Elemente in einem Knoten < 2n

2. Vor dem Einfügen ist die Anzahl der Elemente in einem Knoten = 2n und das Element ist in der linken Hälfte einzufügen

Das Element y wird an den nächst höheren Knoten weitergereicht.

3. Vor dem Einfügen ist die Anzahl der Elemente in einem Knoten = 2n und das Element ist in der rechten Hälfte einzufügen

Das Element y wird an den nächst höheren Knoten weitergereicht.

4. Vor dem Einfügen ist die Anzahl der Elemente in einem Knoten = 2n und es gilt: der Schlüssel des n. Elementes ist < neues Element < Schlüssel des n+1. Elementes. Das einzufügende Element wird nicht in den Knoten eingefügt sondern gleich nach oben weitergereicht.

+ -

Der Einfügenalgorithmus



Procedure Insert(Element: TElement);

 Procedure Update(link: Longint; Var rise: Boolean; Var riseElm: TElement);

 Begin
      Implementierung 
 End;

Var RootSplit: Boolean;
    { Element, welches ggf. von einem Blatt in die Wurzel hochgereicht wird }
    RootElm: TElement; 
    I: Integer;

Begin
     { Element "Element" in Page "RootLink" einfuegen }
     RootSplit:=False;
     Update(RootLink,RootSplit,RootElm);
     { wurde die Wurzel geteilt ? }
     If RootSplit Then
     Begin
          { alte Wurzel löschen }
          Dispose(RootPage);
          { neue Wurzel erstellen }
	  New(RootPage);
	  { einziges Element ist das hochgereichte Element }
          RootPage^.Anzahl:=1;
          RootPage^.Elemente[0].link:=RootLink;
          RootPage^.Elemente[1]:=RootElm;
          { Speicherplatz auf dem Hintergrundspeicher fuer neue 
            Wurzel anfodern }
          RootLink:=NewBackPage;
          { Link der Wurzel aendern }
          SavePage(RootLink,RootPage);
     End;
End;

Prozedurschnittstelle:


Procedure Insert(Element: TElement);

Fügt das Element "Element" in einen Baum ein.

Implementierung der Prozedur "Update":

Die Prozedur ruft sich solange auf, bis die Page gefunden wurde, in die das Element eingefügt werden soll. Wenn die Page dabei geteilt wurde, wird das hochgereichte Element an die aufrufende Prozedur über den Parameter "riseElm" übergeben.



Procedure Update(link: Longint; Var rise: Boolean; Var riseElm: TElement);

Var Page: PPage;
    Pos,I: Integer;
    gefunden, risen: Boolean;

Begin
     { Ende des Baums erreicht ? }
     If link=Null Then
     Begin
          { Einfuegen beenden }
          rise:=True;
          riseElm:=Element;
     End
     Else
     Begin
          { Page einladen }
          Page:=LoadPage(link);
	  { ist einzufuegendes Element bereits vorhanden ? }
          If SucheInPage(Page,Element,Pos) Then
          Begin
               Dispose(Page);
          End
          Else
          Begin
               { Element wurde nicht in Page gefunden 
                 -> Element in Unterbaum einfuegen }
               risen:=False;
               Update(Page^.Elemente[Pos].link,risen,riseElm);
               { wurde der Unterbaum geteilt ? }
               If risen Then
               Begin
		    { passt hochgereichtes Element in geladene Page ? }
                    If Page^.Anzahl<maxElemente Then
                    Begin
          	         { Element an richtige Position in Page einfuegen }}
                         Inc(Page^.Anzahl);
                         For I:=Page^.Anzahl-1 downto Pos+1 do
                          Page^.Elemente[I+1]:=Page^.Elemente[I];
                         Page^.Elemente[Pos+1]:=riseElm;
			 { geladene Page wurde nicht geteilt }
                         rise:=False;
                    End
                    Else
                    Begin
			 { Element passt nicht mehr in Page 
			   -> Page aufteilen }	
			 Split(Page,riseElm,Pos);
                         rise:=True;
                    End;
                    SavePage(link,Page);
               End;
               Dispose(Page);
          End;
     End;
End;

Prozedurschnittstelle:


Procedure Update(link: Longint; Var rise: Boolean; Var riseElm: TElement);

Fügt das Element in die Page "Link" ein.

wenn "rise" true ist, wurde die Page geteilt und ein Element hochgereicht
"riseElm" ist in dem Fall das hochgereichte Element

+ -

Das Teilen einer Page



Procedure Split(Page: PPage; Var Element: TElement; Pos: Integer);

Var SplitPage: PPage;
    Splitlink: Longint;
    riseElm: TElement;
    I: Integer;

Begin
     { neue Page erstellen }
     New(SplitPage);
     { neue Page im Hintergrundspeicher erstellen }
     SplitLink:=NewBackPage;
     { neues Element in die linke der beiden Pages einfuegen
       (die alte und die neue Page) }
     If Pos<n Then
     Begin
          riseElm:=Page^.Elemente[n];
          For I:=n-1 downto Pos+1 do
           Page^.Elemente[I+1]:=Page^.Elemente[I];
          Page^.Elemente[Pos+1]:=Element;
     End
     Else
     { neues Element in die rechte der beiden Pages einfuegen }
     If Pos>n Then
     Begin
          riseElm:=Page^.Elemente[n+1];
          For I:=n+2 to Pos do
           Page^.Elemente[I-1]:=Page^.Elemente[I];
          Page^.Elemente[Pos]:=Element;
     End
     Else
     { neues Element in keine der beiden Pages einfuegen
       sondern gleich nach oben weiterreichen }
         riseElm:=Element;
     SplitPage^.Elemente[0].link:=riseElm.link;
     { hochgereichtes Element muß auf neue Page zeigen }
     riseElm.link:=Splitlink;
     Element:=riseElm;
     { Hälfte der Elemente der alten Page in die neue Page kopieren }
     For I:=n+1 to maxElemente do
      SplitPage^.Elemente[I-n]:=Page^.Elemente[I];
     Page^.Anzahl:=n;
     SplitPage^.Anzahl:=maxElemente-n;
     { neue Page speichern }
     SavePage(Splitlink,SplitPage);
End;

Prozedurschnittstelle:


Procedure Split(Page: PPage; Var Element: TElement; Pos: Integer);

Teilt die Page "Page" um ein "Element" an der Position "Pos" einzufügen. Dabei wird das hochzureichende "Element" zurückgegeben.

Seitenanfang

zurück weiter