Bäume sind azyklische gerichtete Graphen . Ein vertrautes Beispiel ist ein Stammbaum.

Bäume bestehen aus Knoten und gerichteten Kanten (Knotenverbindungen). Knoten sind Informationsspeicher, die einen Wert speichern können. Im Beispiel des Stammbaums speichern sie einen Namen. Eine Kante zwischen zwei Knoten drückt eine gerichtete Beziehung aus von Vorfahr nach Nachfolger/Nachfahr (auch Kind, child, descendent). Zwischen den Nachfolgeknoten eines Knotens besteht eine Geschwisterbeziehung (sibling). Diese Begriffsbildung geht offensichtlich auf das Beispiel des Stammbaums zurück.

Bäume werden in der Informatik zu zweierlei Zwecken eingesetzt:

1. zur Modellierung einer logischen Beziehung durch eine entsprechende Datenstruktur: Begriffshierarchie, Dateihierarchie, Stücklisten (Teil-Einzelteil-Beziehung), Stammbaum, Operatorbaum.
2. als Datenstruktur zum Suchen und Sortieren: Suchbaum.

Neben der Graphendarstellung ist auch die Darstellug durch hierarchisches Einrücken verbreitet, wie es bspw. Windows-Explorer oder Konqueror in KDE in der Navigationsleiste verwenden.

Einen Knoten ohne Nachfolger nennt man ein Blatt. Die anderen Knoten sind innere Knoten. Im Beispiel des Dateiverzeichnissen sind die Dateien die Blätter, die Verzeichnisse die inneren Knoten (typischerweise enthält jedes Dateiverzeichnis mindestens zwei Einträge: . und ..).

Beispiel Operatorbaum:

 

Obiger Operatorbaum stellt den arithmetischen Ausdruck 5 * (2 + 3) dar.

Formale Definition eines Baums

Ein Baum ist entweder leer, oder er besteht aus einer nichtleeren Menge von Knoten eines Grundtyps T mit einer gerichteten Nachfolger-Beziehung zwischen den Knoten mit folgenden Eigenschaften:

• Es gibt genau einen Anfangsknoten, der keinen Vorgänger hat. Dieser wird Wurzel des Baums genannt.
• Jeder andere Knoten kann von der Wurzel aus über Nachfolger erreicht werden.
• Jeder Knoten mit Ausnahme der Wurzel hat genau einen Vorgänger.

 

Teilbaum

Die Nachfolger des Wurzelknoten eines Baums B sind ihrerseits Wurzelknoten des Teilbaums ihrer Nachfolger (der Operatorbaum oben hat 2 Teilbäume). Damit wird deutlich, daß ein Baum eine rekursive Datenstruktur ist. Man kann einen Baum auch rekursiv so definieren:

Ein Baum ist entweder leer oder er besteht aus einem Knoten, der mit einer endlichen Anzahl verschiedener Bäume (Teilbäume) über die sogenannte Nachfolgerbeziehung verknüpft ist. Insbesondere kann ein Baum aus nur einem Knoten bestehen.

Bezeichnungen im Zusammenhang mit Bäumen

• Nachfahr oder direkter Nachfahr (descendent)
• Vorfahr oder direkter Vorfahr (ancestor)
• Geschwisterknoten (sibling)
• Blatt: ein Knoten ohne Nachfolger
• innerer Knoten: ein Knoten mit Nachfolger

Ein geordneter Baum ist ein Baum, in dem eine Ordnungsbeziehung ( < ) zwischen den Nachfolgern besteht, z.B. 1. Kind, 2. Kind usw.

Der Grad eines Knoten ist die Anzahl seiner direkten Nachfolger. Der Grad eines Baumes ist die Maximalzahl aller Grade aller Knoten.

Binärbäume sind Bäume des Grades 2. Jeder Knoten hat maximal 2 Nachfolger.

Die Stufe (Level) eines Knoten: der Wurzelknoten hat Stufe 1, der (direkte) Nachfolger eines Knoten hat eine um 1 höhere Stufe als sein Vorgänger.

Die Höhe (Tiefe, height, depth) ist das Maximum der Stufen aller Knoten. Operationen auf Bäumen

 

• Suchen eines Knoten mit einem bestimmten Wert (in Suchbäumen)
• Suchen eines Knoten anhand seines Platzes in der "Hierarchie" (z.B. Pfad im Dateisystem)
• Traversieren:

Durchlauf durch alleKnoten eines Baumes, z.B. um alle Knotenwerte auszugeben, oder um eine Operation auf allen Knotenwerten durchzuführen. Häufig ist eine bestimmte Durchlaufreihenfolge einzuhalten.

• Einfügen eines Knoten, eines Teilbaums
• Löschen eines Knoten, eines Teilbaums

Implementation von Bäumen

 

Typisch sind Implementationen der Baumverknüpfungen mittels Pointern bzw. Referenzen. Ein Knoten eines Binärbaums (maximal 2 Nachfolger je Knoten) sieht typisch so aus:

class BinaryTreeNode {
    Object value;                // Die Information des Knoten
    BinaryTreeNode left;    // Referenz auf den linken Nachfolger
    BinaryTreeNode right;  // Referenz auf den rechten Nachfolger
}

Ein Knoten eines allgemeinen Baumes (mit beliebig vielen Nachfolgern) kann eine Collection (Liste, Vector) seiner Nachfolger speichern oder effizienter auch mit nur zwei Referenzen auskommen: firstDescendent (statt left) und nextSibling (statt right), vgl. die entsprechende Übungsaufgabe.

Alternativ kann man einen Baum auf einem Array speichern. Dann werden die Verknüpfungen über Indexwerte anstelle von Referenzen implementiert, oder es wird ein Nummerierungsschema der Knoten auf Indexwerte abgebildet. Standardreihenfolgen beim Traversieren

Es gibt drei Standardreihenfolgen beim Traversieren, deren Motivation und Bezeichnung sich am besten am Beispiel eines binären Operatorbaums klarmacht.

1. Preorder: bearbeite Wurzel bzw. Knoten vor linkem und rechtem Teilbaum
2. Inorder: bearbeite zuerst der linken Teilbaum, dann die Wurzel bzw. den Knoten, dann den rechten Teilbaum
3. Postorder: bearbeite zuerst den linken Teilbaum, dann den rechten Teilbaum, dann die Wurzel bzw. den Knoten

Bei einem binären Operatorbaum führen die Ausgabe der Knotenwerte beim Traversieren nach obigen Standardreihenfolgen zu folgenden Ergebnissen:

1. Preorder: Prefix-Notation des arithmetischen Ausdrucks: + 2 3
2. Inorder: Infix-Notation: 2 + 3
3. Postorder: Postfix-Notation: 2 3 +

Binäre Suchbäume

 
Wenn für den Werttyp, den ein Knoten speichert, eine Ordnungsbeziehung < existiert, kann man Binärbäume in der Manier des binären Suchens auf einem sortierten Array einsetzen. Für int-Knoten ist die <-Beziehung durch den int-Operator < gegeben, für String-Knoten ist es der lexikographische Vergleich zweier Strings, der in erster Näherung durch die Methode String.compareTo( ) vorgenommen werden kann.

Man ordne die Knoten im Baum so an, daß jeweils der linke Nachfahr einen kleineren Wert als der Vorfahr speichert und der rechte einen größeren (ggf. auch >=). Dann ergibt sich rekursiv, daß sich kleinere Werte alle im linken Teilbaum befinden, größere alle im rechten Teilbaum. Wenn man nach einem bestimmten Wert sucht, z.B. nach dem Wert 28 in dem folgenden Binärbaum, dann braucht man nur beim Wurzelknoten anfangend jeweils Knotenwert und Suchwert miteinander zu vergleichen und im Falle der Verschiedenheit entsprechend der <-Beziehung zu verzweigen. Der sich ergebende Suchweg ist unten rot gekennzeichnet.

 

Für ein praxisrelevantes Beispiel denke man an ein Namensverzeichnis, in der man schnell nach einem bestimmten Namen suchen will. Eine solches Namensverzeichnis kann man im Arbeitsspeicher als Binärbaum organisieren.

Das Verfahren entspricht dem binären Suchen auf einem sortierten Array, was obige Grafik veranschaulichen soll. Der Unterschied liegt darin, daß ein Binärbaum wie eine Liste eine dynamische Datenstruktur ist. Der direkte Konkurrent wäre ein sortierter Vector, auf den neue Elemente sukzessive einsortiert werden.

Suchen geht mit O(log(N))-Schritten, wenn der Suchbaum ausgewogen ist.

Binäre Suchbäume können entarten

Betrachten wir das Einfügen am Fall des Erstellen einer Liste aller verschiedenen Wörter eines Textes. Naiv wird man die Wörter sukzessive in den Baum einfügen, beim ersten Wort anfangend. Wenn dabei das einzufügende Wort bereits gefunden wird, wird es nicht eingefügt. Dabei landet das erste Wort im Wurzelknoten, alle folgenden Wörter werden links oder rechts bezüglich des ersten Wortes untergeordnet. Wenn die Wörter im Text bereits aufsteigend sortiert sind, werden also alle Wörter nach rechts eingeordnet. Der Binärbaum entartet zu einer linearen Liste mit einer Such- bzw. Einfügekomplexität O(N) (N/2 Vergleiche im Durchschnitt).

Eine Strategie, das Entarten zu vermeiden,überprüft, ob der Baum beim naiven Einfügen entarten würde und den Baum entsprechend zu reorganisieren. Wir verweisen hierzu auf die Literatur, Stichwort >> AVL-Bäume oder >> Rot-Schwarz-Bäume . Das Erkennen und Beheben einer Unausgewogenheit kostet relativ viel Rechenzeit, so daß es nur in Betracht zu ziehen ist, wenn erheblich mehr Suchoperationen als Einfügeoperationen auszuführen sind. Im Beispiel der Liste verschiedener Wörter müßten also im Text in erheblichem Umfang Wörter mehrfach vorkommen. Beim Erstellen einer Konkordanz ist das eher weniger der Fall, weil normalerweise die hochfrequenten Wörter (ein, einer, eine, der, die das etc.) mit einer sogenannten Stopwortliste herausgefiltert werden und gar nicht in die Liste verschiedener Wörter aufgenommen werden.

 

Binäre Suchbäume sortieren

 
Wenn man einen binären Suchbaum mit der Durchlaufstrategie Inorder traversiert, gibt man die Knoten in aufsteigender Sortierfolge aus. Wo also sowohl Suchen als auch Sortieren gefragt ist, kann ein Binärbaum günstiger sein als der Einsatz zweier separater Datenstrukturen. Implementation allgemeiner Bäume mittels binärer Knoten Beispiel Stammbaum:

ein Baum mit mehreren Nachfolgerknoten.

Der Baum wird durch Binärknoten implementiert:

• links: erstes Kind
• rechts: nächstes Geschwister

Die Klassen TreeMap und TreeSet

Seit der Einführung des Collection Framework in der Java-Version 1.2 enthält das JDK/SDK bereits vorgefertigte Baum-Klassen im Packet java.util. Es handelt sich hierbei um die Klassen TreeSet und TreeMap , die entsprechend der Set bzw. Map-Vorgaben entworfen sind.

Die in einer Tree-Collection enthaltenen Daten sind in einen Binärbaum sortiert. Die Klasse stellt neben Methoden zum Füttern/Auslesen der Collections im Konstruktor die Möglichkeit, einen selbstdefinierten Comparator zu übergeben, anhand dessen Vergleichen die Daten im Baum sortiert werden. Vorteil gegenüber HashSets/HashMaps: Daten werden sortiert (nach "natürlicher" Reihenfolge oder einem selbstdefinierten und im Konstruktor übergebenen Comparator) und können demnach auch sortiert ausgegeben werden. Nachteil: Suchoperationen dauern etwas länger.

Zum weiteren Studium schaue man sich die Quelltexte der entsprechenden Klasse oder (besser: und) ihre Dokumentation an.