Einen Baum als Datenstruktur ist die Weiterentwicklung einer Liste, die im vorherigen Kapitel beschreiben wurde. Einige Bäume kennen wir aus dem Alltag wie das Verzeichnis unseres C Laufwerkes bei Windows oder der Stammbaum unserer Familie. Der Artikel definiert einen was ein Baum in der Welt der Datenstrukturen ist, was die wichtigsten Begriffe sind und erklären dann, wie mit einem Baum gearbeitet werden kann. Zum Ende gibt es ein kleines Java Beispiel um das Gelernte zu verdeutlichen.

Definition

Der Baum ist ein abstrakter Datentyp, der Daten in einer „umgedrehten“ Baumform strukturiert. Die Begriffe aus denen ein Baum besteht, lauten: Wurzel (root), Verzweigung (branch), Knoten (knot), Blatt (leaf), Pfad (path) und Ebene (level).
Die Begriffe werden zu sinnvollen Gruppen zusammengefasst. Die Wurzel, Knoten und Blätter sind alles Elemente / Gegenstände (Items) eines Baumes. Verzweigungen und Ebenen zeigen die Hierarchiestruktur in einem Baum an und der Pfad zeigt immer genau einen und den einzigen Weg zu einem Item.
Die Wurzel ist in dem Baum ein ganz besonderer Knoten. Er ist das einzige und oberste Element des Baumes, auf der 0-ten Ebene. Auf die Wurzel folgen nun nur noch Blätter und Knoten. Ein Knoten ist ein Punkt in dem Baum, auf den mindestens ein weiteres Element folgt. Ein Blatt dagegen hat keine Nachfolger.

Es ist eigentlich egal wie viele Elemente auf einen Knoten oder die Root folgen, dieser Artikel wird sich aber ausschließlich mit Bäumen befassen, die maximal 2 nachfolgende Elemente haben. Diese Bäume werden auch binäre Bäume genannt und haben im Bezug auf das Durchsuchen und sortieren einige Vorteile.

Zum Abschluss noch eine Skizze, welche die Daten grafisch verarbeitet:

Darstellung aller wichtiger Bestandteile eines Baum.

Begriffe

Die wichtigsten Begriffe bei Bäumen sind binär und balanciert, sowie ihre Gegenteile eigenartig und lückenhaft. Binäre Bäume sind Bäume die maximal 2 Verzweigungen auf jeden Knoten haben, während die eigenartigen Bäume eine unregelmäßige Anzahl (1 bis ) von Verzweigungen haben kann. So kann eine Form des eigenartigen Baumes die verkettete Liste sein, wenn auf jeden Knoten nur eine weitere Verzweigung folgt. Der Begriff der Balance bezieht sich auf Bäume, bei denen eine maximale Anzahl von Verzweigungen pro Knoten festgelegt wurde (siehe binäre Bäume). Jeder Knoten auf der höchsten Ebene muss alle Verzweigungen eingegangen sein, bevor die nächste Ebene begonnen werden darf. Wird gegen diese Regel verstoßen, so kommt es zu „Lücken“, was lückenhaften Bäume erklären sollte.
Außerdem kann ein binärer Baum die Eigenschaft eines Suchbaumes erfüllen, welches die Anordnung seiner Elemente folgendermaßen voraussetzen würde:

Die Sinnhaftigkeit dieser Aufbauregel, wird in dem folgenden Abschnitt erkenntlich werden.

Anwendung

Um mit einem Baum arbeiten zu können, muss er einige Funktionen haben. Dieser Artikel beschäftigt sich ausschließlich mit binären Suchbäumen, außerdem darf es keine Duplikate in dem Baum geben, da die Bäume sonst zu komplex sind.

Um die Strukturierung von Daten in Bäumen zu realisieren, müssen Datensäte als Knoten und Blätter erstellt und gelöscht werden können. Dabei sind die Operationen für Blätter recht einfach, da der Datensatz bloß an der richtigen Stelle gelöscht oder erstellt werden muss. Das Finden des Datensatzes ist über die Aufbauregel ein leichtes. Werden dagegen Knoten gelöscht oder eingefügt, so ist die Verschiebung auf alle nachfolgenden Items zu berücksichtigen, was die Verwendung eines rekursiven Prüfalgorithmus und Korrigieralgorithmus nahelegt. Der die nachfolgenden Items prüft und neu anordnet, ohne gegen die Aufbauregel verstößt.

Bäume können dabei auf 4 verschiedene Arten traversiert werden, was so viel wie durchlaufen oder gelesen heißt. Das Traversieren gibt an, wie die Knoten nacheinander abgearbeitet werden. Die umgekehrte polnische Notation ist dabei eine der bekanntesten Varianten binäre Rechenbäume zu durchlaufen, während die Möglichkeiten preorder, postorder, inorder und levelorder haben das Ziel haben einen Baum auf eine andere Weise dazustellen. Wir erklären die Möglichkeiten anhand eines kleinen Beispiels. Folgender unbalancierter, binärer Suchbaum ist gegeben:

Die Möglichkeiten preorder, inorder und postorder den Baum zu durchlaufen sind rekursiv!
Wird der Baum preorder traversiert kann folgendes Schema befolgt werden:

  1. Überprüfe ob der gegebene Knoten überhaupt existiert.
    1. Ja, gehe zu 2.
    1. Nein à Ende
  2. Ausgabe des Elements, auf dem man sich gerade befindet
  3. Überprüfe, ob es Links von diesem Knoten einen Nachfolger gibt
    1. Ja, gehe zu 1.
    1. Nein, gehe zu 3.
  4. Überprüfe, ob es rechts von diesem Knoten einen Nachfolger gibt
    1. Ja, gehe zu 1.
    1. Nein, gehe zu 3. (Da es eine rekursive Methode ist, ist die Verarbeitung wie bei einem Stack, sonst würde es nach einem Pfad enden)

Sobald es keine Nachfolger mehr hat, ist die Methode beendet. Das Ergebnis der preorder Traversierung ist folgendes: 10 à 5 à 3 à 2 à 9 à 7 à 9,5 à 23 à 17 à 35 à 43

Bei der inorder Traversierung ist folgendes Schema zu beachten:

  1. Überprüfe ob der gegebene Knoten überhaupt existiert.
    1. Ja, gehe zu 2.
    1. Nein à Ende
  2. Überprüfe, ob es Links von diesem Knoten einen Nachfolger gibt
    1. Ja, gehe zu 1.
    1. Nein, gehe zu 3.
  3. Ausgabe des Elements, auf dem man sich aktuell befindet
  4. Überprüfe, ob es rechts von diesem Knoten einen Nachfolger gibt
    1. Ja, gehe zu 1.
    1. Nein, gehe zu 3.

Bei der inorder Traversierung ist das Ergebnis, die richtige Reihenfolge der Items. Das Ergebnis ist daher:
2 -> 3 -> 5 -> 7 -> 9 -> 9,5 -> 10 -> 17 -> 23 -> 35 -> 43

Wird der Baum postorder traversiert, so ergibt sich folgendes Schema:

  1. Überprüfung ob der Knoten existiert
    1. Ja, gehe zu 2.
    1. Nein à Ende
  2. Überprüfe, ob es Links von diesem Knoten einen Nachfolger gibt
    1. Ja, gehe zu 1.
    1. Nein, gehe zu 3.
  3. Überprüfe, ob es rechts von diesem Knoten einen Nachfolger gibt
    1. Ja, gehe zu 1.
    1. Nein, gehe zu 4.
  4. Ausgabe des Elements, auf dem man sich gerade befindet

Das Ergebnis ist daher: 2 -> 3 -> 7 -> 9,5 -> 9 -> 5 -> 17 -> 43 -> 35 -> 23 -> 10

Die levelorder Traversierung geht von der 0-ten Ebene zur letzten Ebene immer von links nach rechts durch und gibt die Werte aus. In dem Beispiel ergibt das:
10 -> 5 -> 23 -> 3 -> 9 -> 17 -> 35 -> 2 -> 7 -> 9,5 -> 43

Das Suchen in einem binären Suchbaum dauert maximal  bis

herausgefunden wurde, ob der Wert in dem Baum existiert. Um zu suchen, wird wie beim Einfügen vorgegangen. Das Verfahren wird binäres Suchen genannt.

Einen Baum auszubalancieren ist extrem komplex, wer eine Fields Medaille gewinnen will hat hier gute Chancen! Ziel ist es aus einem lückenhaften Baum einen balancierten Baum zu erstellen ohne dabei gegen die Aufbauregel zu verstoßen und nicht ressourcenverschwenderisch zu sein. Sonst könnte man alle Einträge als Liste aufreihen und einen neuen Baum bauen, was sich auch so nicht als einfache erweisen würde.

Anwendungsbeispiel

Als Anwendung haben wir einen Java Baum erstellt mit 3 relevanten Klassen. Die erste Klasse stellt einen Knoten dar, dieser hat einen zwingend 3 Variablen. Zum einen eine Variable für den Inhalt des Knoten zum anderen 2 Variablen für die Referenzen auf den Nachfolgeknoten rechts und links. Die zweite Klasse ist die, in der wir die gesamten Funktionen für den Baum bereitstellen. Hier finden sich die gesamten Funktionen, die wir in dem Abschnitt Anwendung beschrieben haben. Die letzte Klasse ist die Klasse, die die Steuerung der Baum Klasse übernimmt.

Ladet sie euch herunter und spielt ein bisschen herum!

Tipps für die Arbeit mit Bäumen

Zum Erstellen von Baumdiagrammen empfehlen wir die kostenfreie Testversion von yWorks, die ihr euch unter folgendem Link herunterladen könnt httpss://www.yworks.com/products/yed. Das Programm heißt yEd Graph Editor und lässt sich nach 10 Minuten einarbeiten sehr gut bedienen.
Zum anderen möchten wir euch folgende (leider englischen) Seite empfehlen, von dem wir viel unseres Java Codes haben httpss://www.baeldung.com/java-binary-tree. Viel Erfolg!