Ein Speichermodell der Informatik

Der Datentyp "binärer Baum"

Die Programmiersprache PASCAL stellt uns verschiedene Datenstrukturen zu Verfügung (Arrays, Records), d.h. die dazugehörigen Operationen sind in die Sprache schon eingebaut, sie werden vom Compiler direkt in Befehlsfolgen übersetzt oder liegen als fertige Prozeduren in den Sprachbibliotheken (libraries) bereit. Es gibt allerdings noch viele andere denkbare Datenstrukturen, die für gewisse Algorithmen nützlich sind und in denen sich bestimmte algorithmische Vorgehensweisen plastisch darstellen lassen.

Wenn eine solche Datenstruktur hilfreich, in der Programmiersprache aber nicht vorgesehen ist, so lohnt es sich, sich die Mühe zu machen, diese Datenstruktur in der Programmiersprache zu beschreiben - wir sagen auch: implementieren. Bei größeren Programmieraufgaben ist es ein Teil der Aufgabe, sich zuerst die geeigneten Datenstrukturen herzustellen, bevor man mit der eigentlichen Umsetzung des Verfahrens beginnt.

Dieses Vorgehen wollen wir hier am Beispiel einer bestimmten Datenstruktur demonstrieren: dem binären Baum.

Definition Digraph:
Ist Q eine Menge (die Menge der Knoten) und K eine Teilmenge von QxQ (die Menge der Kanten), so heißt die Struktur G = (Q,K) gerichteter Graph oder Digraph (directed graph). Eine Folge benachbarter Kanten heißt Pfad, genauer:
(q₁, q₂) (q₂, q₃)........(q_n, q_n+1) heißt Pfad der Länge n, wenn (q_i, q_i+1) aus K (i=1,...,n).
q₁ ist direkter Vorgänger von q₂ , q₂ ist direkter Nachfolger von q₁, q₁ ist Vorgänger von q_i, q_i ist Nachfolger von q₁ (i >= 1)

Definition Baum:
Ein Baum ist ein gerichteter Graph, der genau einen Knoten ohne direkten Vorgänger hat (die Wurzel) und in dem jeder Knoten von der Wurzel aus durch einen und nur einen Pfad erreicht wird. Die Tiefe eines Knotens ist die Länge des Pfades von der Wurzel zu diesem Knoten, die Höhe des Baums ist die Länge des längsten Pfades. Den direkten Vorgänger eines Knotens nennen wir Vater, einen direkten Nachfolger Sohn. Knoten mit demselben Vater sind Brüder. Knoten ohne Söhne heißen Blätter.
Ein Baum ist binär, wenn jeder Knoten höchstens 2 Söhne hat. Ein binärer Baum der Höhe h heißt vollständig, wenn jeder Knoten einer Tiefe kleiner h genau zwei Söhne hat. Er heißt fast vollständig, wenn alle Knoten einer Tiefe kleiner h-1 genau 2 Söhne haben, während in der Tiefe h-1 ein Knoten (in der Breitennummerierung s.u.) nach einem Knoten mit weniger als 2 Söhnen keine Söhne mehr hat (d.h. die letzte Ebene h ist möglicherweise ab einer bestimmten Stelle nicht mehr gefüllt.)

Sind die Söhne eines Knotens geordnet (durchnummeriert, links-rechts, etc.)., so kann man anhand dieser Ordnung auch die Knoten des ganzen Baumes ordnen (nummerieren):

Breitennummerierung (Breadth first):
Anschaulich: Die Knoten der Tiefe i bilden die Ebene i des Baumes. Hat der Baum die Höhe h, so hat er die h+1 Ebenen 0,...,h. In jeder Ebene nummerieren wir die Knoten von links nach rechts durch. Dabei beginnen wir in Ebene 0. Ein Knoten liegt dann vor einem anderen, wenn er in einer früheren Ebene liegt oder in derselben Ebene früher.
Formal: Sind a, b Knoten, so ist a < b, wenn die Tiefe von a kleiner ist als die von b, oder wenn bei gleicher Tiefe a und b Vorfahren a' und b' haben, so daß a' kleinerer Bruder von b' ist.

Tiefennummerierung (Depth first):
Anschaulich: Wir nummerieren die Knoten beginnend bei der Wurzel und folgen dabei dem Pfad, der durch den jeweils kleinsten Sohn gegeben ist, bis zum Ende. Dann gehen wir zurück bis zu dem Vorfahren, der noch nicht besuchte Söhne hat. Den kleinsten davon suchen wir auf und folgen nun wieder dem linkesten Pfad bis zum Ende, usw.
Algorithmisch beschrieben ist das:

procedure num(p);
begin
nummeriere p (d.h. gib ihm die kleinste noch nicht vergebene Nummer);
for all Söhne q von p in ihrer Reihenfolge do num(q);
end;

Lemma:
1) Ein vollständiger binärer Baum der Höhe h hat 2^h+1-1 Knoten (2ⁱKnoten der Tiefe i).
2) Ist n die Zahl der Knoten eines binären Baums und h seine Höhe, so gilt: 2^h <= n < 2^h+1, d.h. h = log n (nach unten abgerundet)

Der Datentyp "binärer Baum"
Nun wollen wir mit Hilfe der mathematischen Struktur Baum den Datentyp Baum definieren, so wie wir die Datenstruktur Array definieren.
Beim Array mit n Feldern, die wir mit Integern belegen konnten, hatten wir die Statements:

var A: array[1..n] of integer;
A[i]:= 5
x := A[i]

Der Array besteht aus n Feldern, die vom Typ Integer sind. Hierbei ist A[i] der Name des i-ten Feldes des Arrays A. In das wird der Integer 5 geschrieben. Dann wird der Inhalt von A[i] – also die 5 – in ein Feld mit Namen x geschrieben.

Stellen wir uns einen vollständigen binären Baum B von Integerfeldern der Höhe h vor. Dann könnten wir analoge Statements verwenden wollen:

var B: tree[h] of integer; {stellt uns einen vollständigen binären Baum von
                             Feldern vom Typ Integer der Höhe h zur Verfügung}
B[w]:= 5                    {schreibt in Feld B[w] des Baums B den Integer 5}
x   := B[w]                 {schreibt den Inhalt von Feld B[w] in ein Feld mit Namen x}

Was ist das Feldes B[w] des Baums B? In einem binären Baum, in dem es immer nur zwei Söhne gibt, können wir vom linken und vom rechten Sohn sprechen. Wenn wir die Kante zum linken Sohn mit "li" und die zum rechten Sohn mit "re" beschriften, wo führt uns ein Wort w aus den Buchstaben "li" und "re" von der Wurzel einen Pfad entlang bis zu einem Knoten. Wir wollen diesem Knoten die Adresse w geben. B[w] ist also gerade das Feld, das wir von der Wurzel aus erreichen, wenn wir dem durch w bezeichneten Pfad folgen.

Array-Repräsentation
Der Datentyp "Baum" wird uns nicht wie der Datentyp "Array" von der Sprache Delphi fertig geliefert. Wir müssen diesen Datentyp mit den von Delphi bereitgestellten Typen modellieren. Dabei müssen wir sagen können, wie wir das Feld B[w] finden, d.h. wie wir den Pfad w entlanggehen, bzw. die Operationen "gehe zum Vater, gehe zum linken (rechten) Sohn ausführen:
Sei B ein binärer, vollständiger Baum. Wir repräsentieren B durch einen Array A, indem wir das i-te Feld des Baum in der Breitennummerierung mit dem i-ten Feld des Arrays A identifizieren. Das Angenehme an dieser Repräsentation ist die Tatsache, daß die Operation von einem Feld zum Vaterfeld bzw. zu den Sohnfeldern zu gelangen so überaus einfach ist. Es gilt:

Vater (A[i]) = A[i div 2]
linker Sohn (A[i]) = A[2i]
rechter Sohn (A[i]) = A[2i+1].

Die Operationen "div 2" und "*2" (d.h. in der Binärdarstellung die letzte Stelle streichen bzw. eine 0 anhängen) gehören zu den einfachsten Rechenoperationen.
Hat der Baum B die Höhe h, so hat der Array A hat die Länge 2^h+1-1.

Ist B nicht vollständig, so repräsentieren wir ihn ebenso durch den Array A, indem wir uns B durch dummy-Knoten vervollständigt denken, und die entsprechenden Array-Felder mit einem dummy-Symbol # belegen. Wir definieren dies induktiv

A[1] = Wurzel
A[2i] = linker Sohn(A[i]), falls es einen Sohn gibt und A[i] nicht #, sonst = #,
A[2i+1] = rechter Sohn(A[i]), falls es 2 Söhne gibt und A[i] nicht #, sonst = #.

Beispiel:        Baum      Array
                   A     ( A B # C # # # D # # # # # # # )
                   |
                   B
                   |
                   C
                   |
                   D

Beispiel:         Baum      Array
                   A      ( A B C D # E # # # # # F G # # )
                  / \
                 B   C
                 |   |
                 D   E
                    / \
                   F   G

Allerdings sieht man, der Array wird nicht kürzer, auch wenn der Baum kaum mehr Knoten hat, wenn nur seine Höhe gleich bleibt. Das bedeutet, daß die Arrayrepresentation bei sehr unvollständigen Bäumen recht speicheraufwendig ist.