~~~~~~~~~~~~~~~~~~~~~ { Listing 4a)

Datentypen der B-Baeume

Reservierte Woerter : key_type, data_type, b_tree, b_element, file_type

programmiert : Juni 87 von : Dirk Brockhaus mit : PASCAL+ (CCD) }

key_type = integer;

data_type = integer;

b_tree = ^b_element;

b_element = RECORD key : key_type; data : data_type; left , right , next : b_tree; END;

file_type = RECORD key : key_type; data : data_type; END;

</div>

Die Elemente (b_element) haben, entsprechend obigen Vorüberlegungen, folgendes Aussehen: Zunächst bestehen sie aus Schlüssel und Restdaten (key & data). Weiterhin muß ein Zeiger auf den rechten und auf den linken Elementnachfolger weisen (right & left). Zusätzlich muß noch ein Zeiger auf den Listennachfolger für gleiche Schlüssel weisen (next). Das dieser ebenfalls ein b_tree ist, sei eine mir gestattete programmtechnische Schludrigkeit, die, bis auf minimale Speichervergeudung für zwei Zeiger, keine tiefergehenden Nachteile besitzt.

Zur Unterhaltung dieser Struktur benötige ich nun einige Operationen, die äußerlich eine gewisse Ähnlichkeit, mit denen der letzten Folge, nicht leugnen können:

1. <i>create</i>(tree) zum Initialisieren eines Binärbaumes.
2. <i>insert</i>(tree,key,data) fügt einen, durch key und data, vollständig, beschriebenen Datensatz in einen Binärbaum tree ein.
3. <i>remove</i>(tree,key) löscht sämtliche Datensätze mit durch key bezeichnetem Schlüssel in tree und teilt den Erfolg dieser    Aktion über den Funktionsreturn mit.
4. <i>search_first</i>(tree,key,data) sucht in tree nach dem ersten, durch key bezeichnetem, Datensatz data. Der Erfolg, der Suche,    steht ebenfalls im Funktionsreturn.
5. <i>search_next</i>(data) sucht den nächsten Datensatz mit Schlüsselkey in tree. Zu beachten ist hierbei, daß ein Aufruf von    <i>search_next</i>, an einen vorhergehenden Aufruf von <i>search_first</i>    gekoppelt ist. Andernfalls geschieht Unsinn, oder fachgerech   ter formuliert: 'Der Wert von data wird undefiniert'.
6. save(tree,filename) speichert den durch tree bezeichneten Baum    in der Datei filename.
7. load(tree,filename) lädt die durch filename bezeichnete Datei    nach tree.

Für eine genaue Liste der Funktionalitäten bemühen Sie bitte den Programmkopf von Listing 4b.

![ ](/stc1988/images/pascal_04b.gif "")
Zusätzlich zu diesen sieben Operationen, ist es nun noch möglich die Baumelemente in einer gewissen Reihenfolge auszugeben. Anders als bei den Listen, wo nur eine bestimmte Ausgabereihenfolge (Auflisten der Elemente) möglich war, sind hier unter-schiedliche Strategien möglich und nötig. Dazu wird der Binärbaum auf drei Arten durchlaufen:


8.1. Der inorder-Durchlauf besucht zunächst den linken Teilbaum, dann wird das Schlüsselelement ausgegeben, dann erst wird der rechte Teilbaum besucht.  
8.2. Der präorder-Durchlauf gibt zunächst das Schlüsselelement aus und besucht darauf die beiden Teilbäume (zunächst      links).  
8.3. Der postorder-Durchlauf besucht zuerst die beiden Teilbäume (ebenfalls zunächst links) und gibt dann das Schlüsselelement aus.  

Wie Sie sehen werden, finden zwei dieser Durchläufe bei der Implementierung der Binärbäume und der späteren Nutzung der Struktur eine direkte Anwendung.

Die Implementierung der Operationen im einzelnen (Listing 4b):

 1. <i>create</i>(tree)

Die Prozedur <i>create</i>(tree) erledigt die Initialisierung des Baumes tree, indem tree mit nil belegt wird. War tree zuvor besetzt, so werden dessen Elemente ausgehängt und sind nicht mehr zugänglich.

 2. <i>insert</i>(tree,new_key,new_data)

Die Prozedur <i>insert</i> erzeugt zunächst Speicherplatz für ein neues Element (element). Hierauf erfolgt die Initialisierung des Elementes und der Aufruf einer Hilfsfunktion <i>put_in</i>, die das Einfügen eines Elementes in den Baum tree realisiert.

<i>put_in</i> ist nun rekursiv formuliert:

Die Abbruchbedingung für die Rekursion ist, daß der im Moment betrachtete Teilbaum p den Wert nil hat. In diesem Fall wird das element genau an dieser Stelle eingefügt.

Ist dies noch nicht der Fall, hat man zwischen drei Möglichkeiten zu wählen:

2.1 Für den Fall, das unser neuer Schlüssel, new_key, kleiner als     das im Moment betrachtete Baumelement ist, wird im linken Teilbaum nach der Einfügestelle gesucht.

2.2 Für den Fall, das er größer als das im Moment betrachtete     Element ist, im Rechten.

2.3 Im dritten Fall, also bei doppelten Schlüsseln, ist die Nachfolgerliste zu durchlaufen. Angefügt wird in diesem Fall am Ende der Nachfolgerliste.

 3. <i>remove</i>(tree,key)

Das Entfernen sämtlicher, gleicher Schlüssel aus einem Baum, gestaltet sich nicht ganz so einfach, wie das Einfügen. Zunächst ist allerdings ein gleichartiges Problem, wie bei <i>insert</i> zu lösen:

Es wird mit einem rekursiven Aufruf von <i>remove</i> mit seinem Rechts bzw. Linksnachfolger die Stelle gesucht, an der Elemente ausgefügt werden sollen. Gerät man dabei an einen nil-Zeiger, so ist die Suche beendet und das Element ist nicht gefunden worden.

<div class="textkasten bgyellow" markdown=1>

{ Listing 4b)

Operationen auf B-Baeumen

Funktionalitaet der Operationen:

• create : () --> b_tree
• insert : b_tree x key x data --> b_tree
• remove : b_tree x key --> b_tree x boolean (- search_ptr : b_tree x key --> b_tree x boolean)
• search_first : b_tree x key --> data x boolean
• search_next : b_tree x key --> data x boolean
• save : b_tree x string --> file
• load : file x string --> b_tree

Lokale Variablen : present_ptr

Reservierte Woerter : create, insert, remove, search_ptr, search_first, search_next, save, load, present_ptr

programmiert : Juni 87 von : Dirk Brockhaus mit : PASCAL+ (CCD) }

present_ptr : b_tree;

PROCEDURE create(VAR tree : b_tree);

BEGIN {create} tree:=nil; END; {create}

PROCEDURE insert(VAR tree : b_tree; new_key : key_type; new_data : data_type);

VAR element : b_tree;

PROCEDURE put_in( element : b_tree; VAR p : b_tree);

BEGIN {put_in}
   IF p=nil THEN
     p:=element
   ELSE
     IF new_key<p^.key THEN
       put_in(element,p^.left)
     ELSE
       IF new_key>p^.key THEN
         put_in(element,p^.right)
       ELSE
         put_in(element,p^.next);
END;  {put_in}

BEGIN {insert} new(element); WITH element^ DO BEGIN key:=new_key; data:=new_data; right:=nil; left:=nil; next:=nil; END; put_in(element,tree); END; {insert}

FUNCTION remove(VAR tree : b_tree; key : key_type) : boolean;

PROCEDURE put_out(VAR old : b_tree);

VAR copy_old       ,
    daddy_max_left ,
    max_left       : b_tree;

BEGIN {put_out}
  copy_old:=old;
  IF copy_old^.right=nil THEN
    old:=copy_old^.left
  ELSE
    IF copy_old^.left=nil THEN
      old:=copy_old^.right
    ELSE
      BEGIN
        daddy_max_left:=copy_old^.right;
        IF daddy_max_left^.left=nil THEN
          BEGIN
            daddy_max_left^.left:=copy_old^.left;
            old:=daddy_max_left;
          END
        ELSE
          BEGIN
            max_left:=daddy_max_left^.left;
            WHILE max_left^.left<>nil DO
              BEGIN
                daddy_max_left:=max_left;
                max_left:=daddy_max_left^.left;
              END;
            max_left^.left:=copy_old^.left;
            daddy_max_left^.left:=max_left^.right;
            max_left^.right:=copy_old^.right;
            old:=max_left;
          END;
      END;
END;  {put_out}

BEGIN {remove} IF tree<>nil THEN IF key<tree^.key THEN remove:=remove(tree^.left,key) ELSE IF key>tree^.key THEN remove:=remove(tree^.right,key) ELSE BEGIN remove:=true; put_out(tree); END ELSE remove:=FALSE; END; {remove}

FUNCTION search_ptr( tree : b_tree; key : key_type; VAR list : b_tree) : boolean;

BEGIN {search_ptr} IF tree<>nil THEN IF key<tree^.key THEN search_ptr:=search_ptr(tree^.left,key,list) ELSE IF key>tree^.key THEN search_ptr:=search_ptr(tree^.right,key,list) ELSE BEGIN search_ptr:=true; list:=tree; END ELSE search_ptr:=false; END; {search_ptr}

FUNCTION search_first( tree : b_tree; key : key_type; VAR data : data_type) : boolean;

VAR found : boolean;

BEGIN {search_first} found:=search_ptr(tree,key,present_ptr); IF found THEN data:=present_ptr^.data; search_first:=found; END; {search_first}

FUNCTION search_next(VAR data : data_type) : boolean;

VAR found : boolean;

BEGIN {search_next} present_ptr:=present_ptr^.next; found:=present_ptr<>nil; IF found THEN data:=present_ptr^.data; search_next:=found; END; {search_next}

PROCEDURE save(tree : b_tree; filename : string);

VAR t : FILE OF file_type;

PROCEDURE put_praeorder(tree : b_tree);

VAR help : b_tree;

BEGIN {put_praeorder}
  IF tree<>nil THEN
    BEGIN
      help:=tree;
      REPEAT
        t^.key:=help^.key;
        t^.data:=help^.data;
        help:=help^.next;
        put(t);
      UNTIL help=nil;
      put_praeorder(tree^.left);
      put_praeorder(tree^.right);
    END;
END;  {put_praeorder}

BEGIN {save} rewrite(t,filename); put_praeorder(tree); END; {save}

PROCEDURE load(VAR tree : b_tree; filename : string);

VAR t : FILE OF file_type;

BEGIN {load} create(tree); reset(t,filename); WHILE NOT eof(t) DO BEGIN insert(tree,t^.key,t^.data); get(t); END; END; {load}

</div>


Im anderen Fall, also beim Auffinden eines Schlüssels, wird mit der Prozedur put_out(old) der Zeiger old aus dem Baum entfernt. Dazu wird zunächst eine Kopie des Zeigers old angelegt, mit Namen copy_old. Hierauf sind drei Fälle zu unterscheiden:

3.1 Ist der Rechtsnachfolger von copy_old, copy_old^.right=nil,     dann wird old ersetzt durch seinen Linksnachfolger.

3.2 Im anderen Fall, also copy_old^.right&lt;&gt;nil besteht noch die     Möglichkeit, daß der Linksnachfolger,copy_old^.right=nil ist. In diesem Fall wird old durch seinen Rechtsnachfolger ersetzt.

3.3 Der letzte und (all)gemeinste Fall, des Ausfügens eines Knotens Q mit zwei Nachfolgern <>nil, ist ungleich komplizierter.

Deshalb betrachten Sie bitte zunächst Abb.4b.

Q stellt den Knoten dar, der ausgefügt werden soll. In diesem Fall ist Q durch den maximalen Linksnachfolger (S) seines rechten Sohnes (P) zu ersetzen. Eine recht imposante Formulierung, die man sich anhand der Abbildung zunächst verdeutlichen sollte. Für die Ersetzbarkeit von Q durch S ist es notwendig einzusehen, daß S die Funktion von Q vollständig übernehmen kann, daß S also größer als alle Elemente im rechten Teilbaum von Q und kleiner als alle Elemente im linken Teilbaum von Q (ohne S) ist.

Im else-Zweig der zweiten Abfrage von put_out findet man nun genau die algorithmische Beschreibung dieses Vorgangs wieder. Zunächst ist allerdings noch ein Spezialfall abzuhandeln, nämlich, daß P nur einen Linksnachfolger hat. Ist dies nicht der Fall, kommen wir sofort zur oben beschriebenen Gegebenheit. Zunächst wird dazu der Linksnachfolger, genannt max_left, und sein Vater, genannt daddy_max_left, ermittelt (WHILE-Schleife). Hierauf bekommt max_left als Nachfolger die beiden Söhne von old zugewiesen, gleichzeitig muß aber der Vater von max_left den rechten Sohn von max_left (S), N adoptieren. 'Last but not least', wird old durch max_left ersetzt.

Wie Sie sicher zugeben werden, recht verzwickte Familienverhältnisse.

 4. <i>search_first</i>(tree,key,data)

Die Funktion <i>search_first</i> greift zurück auf eine globale Vari-able, present_ptr, und eine Hilfsfunktion, search_ptr, deren Funktion ich zuerst erläutern möchte.

Die Funktion search_ptr(tree,key,list) berechnet den Zeiger auf den Baumrepresentanten der Nachfolgerliste von key. Dieser Zeiger wird dem aufrufenden Programmteil über die Variable list mitgeteilt. Der generelle Erfolg, der Suche, wird über den Funktionsreturn von search_ptr mitgeteilt. Die Arbeitsweise von search_ptr dürfte Ihrem, durch <i>insert</i> und <i>remove</i> geschultem, Auge sofort klar sein: Es ist die übliche rekursive Suche in Bäumen, nur das hier am Ende der Suche keine Datenausgabe, sondern eine Zeigerrückgabe erfolgt.

Mit dieser Hilfsfunktion gestaltet sich nun die Formulierung von <i>search_first</i> sehr einfach. Nach einmaligem Aufruf der Hilfsfunktion, steht der Zeiger present_ptr, soweit vorhanden, auf dem entsprechenden Baumelement. Die bool'sche Variable found beinhaltet den Erfolg/Mißerfolg der Suche. Ist sie true, so kann auf present_ptr^.data zugegriffen werden und unser erster Datensatz ist gefunden.

 5. <i>search_next</i>(data)

Die Weiterführung der Suche nach neuen Elementen, mit durch <i>search_first</i> bezeichnetem Schlüssel, besteht nun einfach aus dem durchgehen der Nachfolgerliste, des mit present_ptr bezeichneten Elementes.

 6. save(tree,filename)

Nach der schreibenden Eröffnung der Datei filename, werden nun die Baumelemente, durch die Hilfsprozedur put_praeorder, in ihrer Präorderabfolge in die Datei geschrieben. Für die Gründe dieser speziellen Elementabfolge, verweise ich auf die Beschreibung der X-order-Durchläufe (siehe unten).

Eingeschachtelt im Präorderdurchlauf, findet noch ein Durchlaufen der Elementnachfolgerlisten statt, um die Daten mehrfach belegter Schlüssel zu speichern.

 7. load(tree,filename)

Nach der Initialisierung des durch tree bezeichneten Baumes, mit <i>create</i>(tree), wird die Datei filename, mit lesendem Zugriff, eröffnet. Die Elemente werden bis zum Dateiende (eof) in den Baum tree eingefügt.

 8. X-order-Durchläufe

Wie schon unter save erwähnt, kommt den X-order-Durchläufen unter bestimmten Bedingungen eine besondere Funktion zu. Allen voran ist hier der inorder-Durchlauf zu erwähnen, welcher eine sortierte Liste der Baumelemente erstellt.

Auch der präorder-Durchlauf hat bei der Implementierung der Prozedur save eine große Bedeutung gespielt. Es läßt sich nämlich feststellen, daß aus der Präorderreihenfolge der zugrunde liegende Baum wiedergewonnen werden kann.

Um ein Beispiel für die Baumstruktur, welche aus einer gewissen Eingabesequenz entsteht und den daraus resultierenden X-order-Durchläufen zu geben, habe ich die Abb.4c angefertigt. Hier sehen Sie den, aus einer Eingabesequenz, entstehenden Binärbaum und die zugehörigen X-order-Sequenzen.

<figure>
  <img src="/stc1988/images/pascal_04c.gif">
  <figcaption></figcaption>
</figure>

<div class="textkasten bgyellow" markdown=1>

{ Listing 4c)

Programm test_b_trees liefert eine Testumgebung zu den b_tree Modulen. Es wird ein Baum verwaltet, in dem

• eingefuegt und geloescht werden kann
• eine Suche nach Daten gleichen Schluessels durchgefuehrt werden kann
• dateioperationen moeglich sind

Weiterhin koennen, zusaetzlich zu den Modulfunktionen prae-, post-, und inorder Durchlaeufe gemacht werden.

programmiert : Juni 87 von : Dirk Brockhaus mit : PASCAL+ (CCD) }

PROGRAM test_b_trees (input,output);

TYPE {$i baum_typ.pas}

VAR tree : b_tree; key : key_type; data : data_type; str : string; question : char;

{$i baum.pas}

PROCEDURE drucke_daten(liste : b_tree);

BEGIN {drucke_daten} WHILE liste<>nil DO BEGIN write(' ',liste^.data); liste:=liste^.next; END; END; {drucke_daten}

PROCEDURE inorder(tree : b_tree);

BEGIN {inorder} IF tree<>nil THEN BEGIN inorder(tree^.left); write(' Schluessel: ',tree^.key,' Daten: '); drucke_daten(tree); writeln; inorder(tree^.right); END; END; {inorder}

PROCEDURE praeorder(tree : b_tree);

BEGIN {praeorder} IF tree<>nil THEN BEGIN write(' Schluessel: ',tree^.key,' Daten: '); drucke_daten(tree); writeln; praeorder(tree^.left); praeorder(tree^.right); END; END; {praeorder}

PROCEDURE postorder(tree : b_tree);

BEGIN {postorder} IF tree<>nil THEN BEGIN postorder(tree^.left); postorder(tree^.right); write(' Schluessel: ',tree^.key,' Daten: '); drucke_daten(tree); writeln; END; END; {postorder}

BEGIN {main} writeln('Test der B-B„ume'); writeln; create(tree); REPEAT writeln('<1> Einfgen'); writeln('<2> L”schen eines Schlssels'); writeln('<3> Suchen nach Schlsselkriterium'); writeln('<4> Inorder Baumdurchlauf'); writeln('<5> Pr„order Baumdurchlauf'); writeln('<6> Postorder Baumdurchlauf'); writeln('<7> Baum speichern'); writeln('<8> Baum laden'); writeln('<9> Baum initialisieren'); writeln('<0> Beenden'); write(' > '); read(question); writeln; CASE question OF '1' : BEGIN write(' Schlssel > '); readln(key); write(' Daten > '); readln(data); insert(tree,key,data); END; '2' : BEGIN write(' Schlssel > '); readln(key); IF NOT remove(tree,key) THEN BEGIN writeln(' Dieser Schlssel existierte nicht.'); readln; END; END; '3' : BEGIN write(' Schlssel > '); readln(key); IF search_first(tree,key,data) THEN BEGIN writeln(' Schlsselliste : ',key); writeln; writeln(' Daten: '); writeln(' ',data); WHILE search_next(data) DO writeln(' ',data); END ELSE writeln(' Schlssel nicht gefunden!'); END; '4' : BEGIN writeln(' inorder-Durchlauf:'); inorder(tree); readln; END; '5' : BEGIN writeln(' pr„order-Durchlauf:'); praeorder(tree); readln; END; '6' : BEGIN writeln(' postorder-Durchlauf:'); postorder(tree); readln; END; '7' : BEGIN write(' Dateiname > '); readln(str); save(tree,str); END; '8' : BEGIN write(' Dateiname > '); readln(str); load(tree,str); END; '9' : create(tree); END; UNTIL question='0'; END. {main}

</div>

Anwendung & Testumgebung
========================
Die Testumgebung für die Module 4a & 4b macht auch gleich die Anwendung plausibel:

-  Zunächst sind die Typen als Header- Datei zu deklarieren<br>{$i baum_typ.pas}
-  Ein Baum wird nun, im Variablendeklarationsteil einfach als   b_tree bezeichnet.<br>VAR tree : b_tree;<br>(Daten und Schlüssel werden völlig analog behandelt!)
-  Hierauf erfolgt sofort die Deklaration der Baumoperationen.<br>{$i baum.pas}<br>Dies wird sofort auf den Variablendeklarationsteil notwendig,   weil baum.pas zusätzlich zu den Operationen noch eine globale   Variable beinhaltet.
-  Die hierauf formulierten X-order-Durchläufe folgen wortwörtlich   den entsprechenden Definitionen. Zur Ausgabe der Daten der Elementnachfolgerlisten greifen sie   jedoch zusätzlich auf eine kleine Hilfsprozedur, drucke_daten,   zu, welche die Liste durchläuft und dabei die Daten ausgibt.
-  Vor der Benutzung des Baumes, ist es nun noch notwendig, ihn   durch <i>create</i> zu initialisieren.
-  Das weitere Hauptprogramm, beschränkt sich nun auf die Ausgabe   eines Benutzerdialoges und den Aufruf der Baumoperationen, bzw. den Aufruf der X-order-Durchläufe, anschließend an die Dateneingabe.
Wie Sie sehen ist in der Anwendung alles sehr unkompliziert.

Vorausschau
===========
In der nächsten Folge von Algorithmen & Datenstrukturen, werde ich die obige Struktur etwas verfeinern. Ein Stichwort, in diesem Zusammenhang, ist der Begriff des AVL-Baumes.

Demjenigen, dem dies etwas sagt, der hat sicher auch bereits gemerkt, daß ich heute an einer Stelle ein wenig gemogelt habe. Wer also ernsthaft mit den Binärbäumen Daten verarbeiten möchte, der sollte noch bis zum nächsten Monat warten.

Für heute bleibt mir nur noch, mich an dieser Stelle für Ihre Aufmerksamkeit zu bedanken.

Dirk Brockhaus

---

---