Bäume allgemein
Bäume gehören zu den wichtigsten Datenstrukturen in der Informatik. Unter einem Baum versteht man eine Datenstruktur, bei der jedes Element mindestens zwei Nachfolger hat. Diese Nachfolger können aber - mal wieder typisch für Mathematiker und Informatikerinnen - leer sein.
Hier eine interessante rekursive Definition aus einem alten Fachbuch; leider sind mir Titel und Autor nicht mehr verfügbar:
Baum
Ein Baum ist entweder leer oder besteht aus einem Baum mit mindestens zwei Nachfolgern.
Drei Bäume
Autor: Ulrich Helmich 2022, Lizenz: siehe Seitenende
Der erste Baum (links) ist leer und erfüllt damit die obige Definition. In Java hat man diese Situation direkt nach der Deklaration eines Attributs, das auf einen Baum verweisen (zeigen) soll. Angenommen, Baum sei eine Java-Klasse, welche einen Baum definiert. Dann würde die Anweisung
Baum myTree;
genau einen solchen leeren Baum erzeugen. Ein solcher leerer Baum hat noch nicht einmal eine Wurzel (Fachbegriffe siehe folgende Übersicht).
Der zweite Baum besteht aus genau einem Knoten, der dann auch gleichzeitig die Wurzel des Baums ist. Ob diese Wurzel jetzt Nachfolger hat, ist eine Frage der persönlichen Anschauung.
Eine eher theoretisch denkende Mathematikerin würde vielleicht sagen: "Die Wurzel hat mindestens zwei Nachfolger, aber bei denen handelt es sich um leere Bäume". Eine eher pragmatisch denkende Person würde dagegen vermutlich sagen: "Die Wurzel hat keine Nachfolger". Keine Ahnung, was jetzt eine pragmatisch denkende Mathematikerin sagen würde.
Der dritte Baum besteht aus einer Wurzel mit drei Nachfolgern. Die beiden ersten Nachfolger sind Bäume ohne Nachfolger (bzw. Bäume mit leeren Nachfolgern), und der dritte Nachfolger der Wurzel ist ein Baum mit einem nicht-leeren Baum als Nachfolger und mindestens einem leeren Baum als Nachfolger.
Denken Sie an die Definition: Ein Baum muss mindestens zwei Nachfolger haben, die ihrerseits jeweils mindestens zwei Nachfolger haben müssen. Wären Bäume erlaubt, die nur einen Nachfolger haben dürfen, dann wären das keine Bäume mehr, sondern Listen, also rein lineare, nicht verzweigte Datenstrukturen.
Kommen wir nun zu den wichtigsten Fachbegriffen, die im Zusammenhang mit Bäumen immer wieder auftreten.
Wichtige Fachbegriffe
Wurzel = Das einzige Baum-Element, das keinen Vorgänger hat.
Blatt = Baum-Element, das keine bzw. nur leere Nachfolger hat.
Innerer Knoten = Baum-Element, das einen Vorgänger und mindestens einen nicht-leeren Nachfolger hat.
Höhe / Tiefe = maximale Zahl der Ebenen eines Baumes.
Kante = die Verbindung zwischen einem Vorgänger- und einem Nachfolgerknoten.
Pfad = die Folge der Kanten, die aufeinanderfolgende Knoten verbinden.
Niveau / Level = Länge des Pfades von der Wurzel zu einem Knoten.
Ordnung = maximale Zahl der Nachfolger, die ein Element haben kann.
Erläuterung der Fachbegriffe
Erläuterung der Fachbegriffe
Die Graphik zeigt einen typischen Baum. Die Wurzel ist der rot gefärbte obere Knoten, die Blätter sind grün gefärbt und die inneren Knoten blau.
Die Höhe bzw. Tiefe des Baums beträgt 4, da der Baum aus vier Ebenen besteht.
Eine Kante ist in der Abbildung beschriftet, und ein Pfad ist durch einen dicken roten Pfeil markiert. Dieser Pfad führt von der Wurzel über den linken Nachfolger zu dessen linken (und einzigen) Nachfolger auf der Ebene 3. Das Niveau bzw. der Level dieses Pfades hat dann den Wert 2.
Die Ordnung dieses konkreten Baumes ist 3, denn kein Knoten hat mehr als drei Nachfolger.
Anwendungsbeispiele
Bäume werden auf vielfältige Weise in der Informatik genutzt, zum Beispiel als Stammbaum einer Familie, als Dateistruktur auf einer Festplatte, als Gliederung eines PDF-Dokuments, als Organisationsdiagramm, als Entscheidungsbaum bei einem Computerspiel und so weiter.
Baum-Typen
Geordneter Baum
Bei einem geordneten Baum sind die Nachfolger eines Knotens in einer bestimmten Reihenfolge angeordnet.
Binärbaum
Ein Baum, bei dem jeder Knoten maximal zwei Nachfolger hat.
Binärer Suchbaum
Ein Binärbaum, der gleichzeitig ein geordneter Baum ist. Weitere Einzelheiten siehe Folge 17.2 in dem Java-Kurs.
Ausgeglichener Baum, AVL-Baum
Ein Baum, der möglichst viele Knoten auf einer Ebene enthält und bei dem die Pfade möglichst kurz sind. Weitere Einzelheiten siehe Folge 18.1 in dem Java-Kurs.
B-Baum
Ein Baum, dessen Knoten aus geordneten Listen bestehen, wobei jedes Listenelement auf einen weiteren Nachfolger-Knoten zeigt. Weitere Einzelheiten siehe Folge 18.5 in dem Java-Kurs.