Baum (Datenstruktur)

Grundidee und Definition

Ein Baum ist in der Informatik eine Datenstruktur und ein abstrakter Datentyp zur Darstellung hierarchischer Strukturen. Er besteht aus gleichartigen, miteinander verbundenen Objekten und verzweigt sich von einem Ausgangspunkt, der Wurzel. Bäume sind besonders wichtig, weil sich viele kombinatorische Probleme auf sie zurückführen lassen und weil sie als Spannbäume Ergebnisse von Graphenalgorithmen wie Breiten- oder Tiefensuche sein können.

Formal besteht ein Baum aus einer Menge von Knoten und einer Menge von Kanten. Eine Kante verbindet jeweils zwei Knoten. Ein bestimmter Knoten ist die Wurzel. Jeder andere Knoten ist durch eine Kante mit genau einem Elternteil verbunden, und von der Wurzel führt genau ein eindeutiger Pfad zu jedem Knoten.

Eine gleichwertige rekursive Definition lautet: Ein Baum ist entweder leer oder besteht aus einer Wurzel und null oder mehr Teilbäumen, die selbst wieder Bäume sind. Die Wurzel jedes Teilbaums ist durch eine Kante mit der Wurzel des übergeordneten Baums verbunden. Hat jeder Knoten höchstens zwei Kinder, heißt die Struktur Binärbaum.

Aufbau und Fachbegriffe

Ein Knoten ist ein grundlegender Bestandteil des Baums. Er kann einen Namen besitzen, der Schlüssel genannt wird, und zusätzliche Informationen speichern. Diese zusätzlichen Informationen heißen Nutzdaten. Sie sind für viele allgemeine Baumalgorithmen nicht zentral, können für konkrete Anwendungen aber entscheidend sein.

Die Wurzel ist der einzige Knoten ohne eingehende Kante. Jeder andere Knoten besitzt genau eine eingehende Kante, kann aber mehrere ausgehende Kanten haben. Die direkt untergeordneten Knoten heißen Kinder; der verweisende Knoten ist ihr Elternteil. Knoten mit demselben Elternteil heißen Geschwister. Ein Knoten ohne Kinder wird Blatt genannt.

Ein Pfad ist eine geordnete Liste von Knoten, die durch Kanten verbunden sind. Ein Teilbaum besteht zusammenhängend aus einem übergeordneten Knoten, allen seinen Nachkommen und den verbindenden Kanten; er bildet selbst wieder einen Baum. Die Kinder eines Knotens sind jeweils die Wurzeln solcher Teilbäume.

Bei einem Wurzelbaum ist die Wurzel eindeutig festgelegt. Die Tiefe eines Knotens ist die Anzahl der Kanten zwischen ihm und der Wurzel. Die Wurzel hat die Tiefe 0. Alle Knoten derselben Tiefe bilden eine Ebene beziehungsweise ein Niveau. Die Höhe des gesamten Baums entspricht der maximalen Tiefe eines Knotens. Weitere aus der Graphentheorie übernommene Begriffe sind unter anderem Abstand, Knotengrad und Isomorphie.

Eigenschaften und Speicherung

Gegenüber linearen Strukturen wie Feldern oder Listen ermöglichen Bäume einen effizienten Zugriff. Als Beispiel nennt der Artikel eine Suche in logarithmischer statt linearer Zeit. Diese Aussage bezieht sich auf geeignete Baumstrukturen, wie sie bei der Binärsuche verwendet werden.

Gegenüber allgemeinen Netzwerkstrukturen benötigen Bäume vergleichsweise wenige Kanten. Ein vollständiger Graph Kₙ mit n Knoten besitzt die Dreieckszahl Δₙ₋₁ = {n \choose 2} = n(n−1)/2 Kanten. Ein Baum mit derselben Anzahl n von Knoten hat dagegen nur n−1 Kanten.

Zur Speicherung können wie bei anderen Graphenstrukturen Adjazenzlisten, Adjazenzmatrizen oder Inzidenzmatrizen verwendet werden. Eine Adjazenzliste hält für jeden Knoten seine benachbarten Knoten fest; Matrizen stellen die Verbindungen in Tabellenform dar.

Wichtige Baumarten

Der Binärbaum ist ein wichtiger Spezialfall, bei dem jeder Knoten höchstens zwei Kinder besitzt. In höhen-balancierten Bäumen gilt zusätzlich, dass sich die Höhen des linken und rechten Teilbaums an jedem Knoten nicht zu stark unterscheiden.

Bei geordneten Bäumen, besonders bei Suchbäumen, werden die Elemente entsprechend einer Ordnung in der Baumstruktur abgelegt. Dadurch lassen sich Elemente schnell auffinden. Zu den genannten Formen gehören binäre Suchbäume, ihre balancierte Variante der AVL-Baum sowie B-Bäume und deren Variante B*-Bäume. Spezialisierungen von B-Bäumen sind 2-3-4-Bäume, die häufig als Rot-Schwarz-Bäume implementiert werden.

Fibonacci-Bäume sind ein Spezialfall der AVL-Bäume. Sie dienen bei Effizienzbetrachtungen zu höhen-balancierten Bäumen, besonders zu AVL-Bäumen, als Extremfälle und Vergleichsobjekte.

Geometrische Baumstrukturen wie der R-Baum und seine Varianten sind nicht sortiert, sondern „verschachtelt“. Bei einer räumlichen Anfrage werden nur die Teilbäume durchsucht, die sich mit dem angefragten Bereich überlappen. Allgemein ist der Aufbau eines Baums mehrdimensional, die Verkettung der gespeicherten Objekte aber häufig unidirektional: Sie beginnt an der Wurzel und verläuft von dort zu den übrigen Knoten.

Prüfung eines Graphen im Programm

Das C#-Beispiel stellt einen ungerichteten Graphen mithilfe von Adjazenzlisten dar und prüft, ob dieser Graph ein Baum ist. Die Klasse Node speichert für jeden Knoten einen ganzzahligen Index, einen Wert und eine Menge adjacentNodes mit den benachbarten Knoten. Die Klasse UndirectedGraph verwaltet die Knotenmenge. Ihre Methode ConnectNodes verbindet zwei Knoten in beiden Richtungen.

Die rekursive Methode IsCyclic durchsucht den Graphen und markiert bereits besuchte Knoten. Trifft sie auf einen schon besuchten Nachbarknoten, der nicht der unmittelbare Elternknoten des aktuellen Knotens ist, wurde ein Zyklus gefunden. Ein Zyklus ist ein geschlossener Weg und verhindert, dass der Graph ein Baum ist.

Die Methode IsTree prüft zwei notwendige Bedingungen: Zunächst darf die vom ersten Knoten aus erreichbare Komponente keinen Zyklus enthalten. Danach müssen alle Knoten als besucht markiert sein, der Graph muss also zusammenhängend sein. Ist er zyklusfrei und zusammenhängend, liefert die Methode true.

Im Beispiel werden fünf Knoten mit den Werten A, B, C, D und E erzeugt. Verbunden werden B–A, A–C, A–D und D–E. Alle fünf Knoten sind zusammenhängend, und es entsteht kein Zyklus. Deshalb gibt das Programm „Der Graph ist ein Baum.“ aus.