Baum (Datenstruktur)

Datenstruktur Baum

In der Informatik ist ein Baum (engl. tree) eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen. Dadurch, dass einerseits viele kombinatorische Probleme auf Bäume zurückgeführt werden können oder (im Fall von Spannbäumen) die Ergebnisse von Graphenalgorithmen (wie der Breiten- oder Tiefensuche) sind, spielen Bäume in der Informatik eine besondere Rolle. Dabei können ausgehend von der Wurzelmehrere gleichartige Objekte miteinander verkettet werden, sodass die lineare Struktur der Liste aufgebrochen wird und eine Verzweigung stattfindet. Da Bäume zu den meist verwendeten Datenstrukturen in der Informatik gehören, gibt es viele Spezialisierungen.

Definitionen

Bäume können auf verschiedene Weise definiert werden, z. B.

1. Ein Baum besteht aus einer Menge von Knoten und einer Menge von Kanten, die jeweils zwei Knoten verbinden. Ein bestimmter Knoten des Baums wird als Wurzel bezeichnet. Jeder Knoten mit Ausnahme der Wurzel ist durch eine Kante mit genau einem anderen Knoten verbunden, wobei dieser Knoten der Elternteil von n ist. Ein eindeutiger Pfad verläuft von der Wurzel zu jedem Knoten. Wenn jeder Knoten im Baum maximal zwei untergeordnete Knoten (Kinder) hat, wird der Baum Binärbaum genannt.
2. Ein Baum ist entweder leer oder besteht aus einer Wurzel und 0 oder mehr Teilbäumen, von denen jeder auch ein Baum ist. Die Wurzel jedes Teilbaums ist durch eine Kante mit der Wurzel des übergeordneten Baums verbunden. Dies ist eine rekursive Definition für Bäume.

Eigenschaften

Der Vorteil von Bäumen gegenüber linearen Strukturen wie Felder oder Listen ist der effiziente Zugriff. So erfolgt beispielsweise eine Suche nur in logarithmischer Zeit gegenüber linearer Zeit bei Feldern (zu Details vergleiche Artikel Binärsuche). Der Vorteil von Bäumen als Datenstruktur gegenüber Netzwerkstrukturen ist die geringe Anzahl der Kanten (Verbindungen), die gespeichert bzw. berücksichtigt werden müssen. Die Anzahl der Kanten des vollständigen Graphen 𝐾𝑛 entspricht der Dreieckszahl

. Die Anzahl der Kanten in einem Baum mit der gleichen Anzahl von Knoten (Objekten) ist dagegen lediglich 𝑛 – 1.

Terminologie

Allgemein werden alle denkbaren Begriffe der Graphentheorie entlehnt. Die durch die Hierarchie vorgegebenen Objekte nennt man Knoten. Typischerweise speichert jeder Knoten ausgehend von einem ersten Knoten, der Wurzel, eine Liste von Verweisen auf die ihnen untergeordneten Knoten. Diese Verweise heißen Kanten. Eine Kante verbindet zwei Knoten, um anzuzeigen, dass zwischen ihnen eine Beziehung besteht. Jeder Knoten außer der Wurzel ist durch genau eine eingehende Kante von einem anderen Knoten verbunden. Die Wurzel des Baums ist der einzige Knoten im Baum, der keine eingehenden Kanten hat. Jeder Knoten kann mehrere ausgehende Kanten haben.

Begriffe eines Baums

Es ist üblich, bei den untergeordneten Knoten von Kindern und bei dem verweisenden Knoten von einem Elternteil zu sprechen. Die Menge der Knoten, die eingehende Kanten von demselben Knoten haben, werden als Kinderdieses Knotens bezeichnet. Ein Knoten ist das Elternteil aller Knoten, mit denen er mit ausgehenden Kanten verbunden ist. Knoten im Baum, die Kinder desselben Elternteils sind, werden als Geschwister bezeichnet. Auch andere der Genealogie entlehnten Bezeichnungen werden verwendet. Hat ein Knoten selbst keine Kinder, nennt man ihn ein Blatt.

Insbesondere sind die Begriffe der Wurzelbäume relevant: Bei diesen Bäumen ist die Wurzel eindeutig bestimmt. Hat man eine Wurzel festgehalten, lassen sich zusätzlich zu den Begriffen, die man bei graphentheoretischen Bäumen schon hat – Abstand, Teilbaum, Knotengrad, Isomorphie –, noch Folgendes definieren: Die Tiefe eines Knotens gibt an, wie viele Kanten er von der Wurzel entfernt ist. Die Wurzel hat die Tiefe 0. Die Knoten mit derselben Tiefe bilden zusammen eine Ebene oder ein Niveau. Die Höhe eines Baumes ist dann die maximale Tiefe eines Knotens.

Ein Knoten ist ein grundlegender Bestandteil eines Baumes. Er kann einen Namen haben, der Schlüssel genannt wird. Ein Knoten kann auch zusätzliche Informationen enthalten. Diese zusätzlichen Informationen werden Nutzdaten genannt. Während die Nutzdateninformationen für viele Baumalgorithmen nicht von zentraler Bedeutung sind, sind sie in Anwendungen, die Bäume verwenden, häufig von entscheidender Bedeutung.

Ein Pfad ist eine geordnete Liste von Knoten, die durch Kanten verbunden sind. Ein Teilbaum ist eine zusammenhängende Menge von Knoten und Kanten, die aus einem übergeordneten Knoten und allen Nachkommen dieses übergeordneten Knotens bestehen und selbst einen Baum bildet. Die Kinder jedes Knotens sind die Wurzeln eines Teilbaums.