imported>Serols: Änderungen von ~2026-49189-6 (Diskussion) rückgängig gemacht (HG) (3.4.13)

2026-01-23T09:54:14Z

Änderungen von ~2026-49189-6 (Diskussion) rückgängig gemacht (HG) (3.4.13)

Neue Seite

[[Datei:Allgemeiner-baum.png|alternativtext=|mini|Datenstruktur Baum]]
In der [[Informatik]] ist ein '''Baum''' (engl. {{lang|en|''tree''}}) eine [[Datenstruktur]] und ein [[abstrakter Datentyp]], mit dem sich hierarchische Strukturen abbilden lassen. Dadurch, dass einerseits viele [[Kombinatorische Optimierung|kombinatorische]] Probleme auf [[Baum (Graphentheorie)|Bäume]] zurückgeführt werden können oder (im Fall von [[Spannbaum|Spannbäumen]]) die Ergebnisse von Graphenalgorithmen (wie der [[Breitensuche|Breiten-]] oder [[Tiefensuche]]) sind, spielen Bäume in der Informatik eine besondere Rolle. Dabei können ausgehend von der [[Wurzel (Graphentheorie)|Wurzel]] mehrere gleichartige [[Entität (Informatik)|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.

# Ein Baum besteht aus einer Menge von [[Knoten (Graphentheorie)|Knoten]] und einer Menge von [[Kante (Graphentheorie)|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 (Graphentheorie)|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.
# 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|rekursive]] Definition für Bäume.<ref>Runestone Interactive LLC: [https://runestone.academy/runestone/books/published/pythonds/Trees/VocabularyandDefinitions.html Vocabulary and Definitions]</ref>

== Eigenschaften ==
Der Vorteil von Bäumen gegenüber linearen Strukturen wie [[Feld (Datentyp)|Felder]] oder [[Liste (Datenstruktur)|Listen]] ist der [[Effizienz (Informatik)|effiziente]] Zugriff. So erfolgt beispielsweise eine [[Suchverfahren|Suche]] nur in logarithmischer Zeit gegenüber linearer Zeit bei Feldern (zu Details vergleiche Artikel [[Binäre Suche|Binärsuche]]). Der Vorteil von Bäumen als Datenstruktur gegenüber [[Netzwerkstruktur]]en ist die geringe Anzahl der [[Kante (Graphentheorie)|Kanten]] (Verbindungen), die gespeichert bzw. berücksichtigt werden müssen. Die Anzahl der Kanten des [[Vollständiger Graph|vollständigen Graphen]] <math>K_n</math> entspricht der [[Dreieckszahl]] <math>\Delta_{n-1} = {n \choose 2}=\frac{n(n-1)}{2}</math>. Die Anzahl der Kanten in einem Baum mit der gleichen Anzahl von Knoten (Objekten) ist dagegen lediglich <math>n-1</math>.

Bäume können wie andere Graphenstrukturen über eine [[Adjazenzliste]] oder -[[Adjazenzmatrix|matrix]] bzw. über eine [[Inzidenzmatrix]] gespeichert werden.

== Terminologie ==
[[File:Baum Begriffe.svg|mini|Begriffe eines Baums]]
Allgemein werden alle denkbaren Begriffe der [[Graphentheorie]] entlehnt. Die durch die Hierarchie vorgegebenen Objekte nennt man ''[[Knoten (Graphentheorie)|Knoten]]''. Typischerweise speichert jeder Knoten ausgehend von einem ersten Knoten, der ''[[Wurzel (Graphentheorie)|Wurzel]]'', eine Liste von Verweisen auf die ihnen untergeordneten Knoten. Diese Verweise heißen ''Kanten''. Eine ''[[Kante (Graphentheorie)|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.

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 ''Kinder'' dieses 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 [[Wurzelbaum|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 – ''[[Weg (Graphentheorie)|Abstand]]'', ''[[Teilgraph|Teilbaum]]'', ''[[Grad (Graphentheorie)#Gerichtete Graphen|Knotengrad]]'', ''[[Isomorphie von Graphen|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 (Graphentheorie)|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 (Graphentheorie)|Pfad]]'' ist eine geordnete [[Liste (Datenstruktur)|Liste]] von Knoten, die durch Kanten verbunden sind. Ein ''Teilbaum'' ist eine zusammenhängende [[Menge (Mathematik)|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.

== Binärbaum ==
[[Datei:BinärBaum Suchbaum.jpg|mini|[[Binärer Suchbaum]]]]

Ein wichtiger Spezialfall ist der [[Binärbaum]], in welchem jeder Knoten nur höchstens zwei Kinder haben darf. So beträgt bei [[Binärbaum|Binärbäumen]] die Anzahl der Kinder höchstens zwei und in [[Balancierter Baum#Höhenbalance|höhen-balancierten Bäumen]] gilt zusätzlich, dass sich die [[Höhe (Graphentheorie)|Höhen]] des linken und rechten Teilbaums an jedem [[Knoten (Graphentheorie)|Knoten]] nicht zu sehr unterscheiden.

Bei geordneten Bäumen, insbesondere [[Suchbaum|Suchbäumen]], sind die Elemente in der Baumstruktur [[Ordnungsrelation|geordnet]] abgelegt, sodass man schnell Elemente im Baum finden kann. Man unterscheidet hier weiter in [[Binärer Suchbaum|binäre Suchbäume]] mit [[AVL-Baum|AVL-Bäumen]] als balancierte Version und [[B-Baum|B-Bäumen]] sowie einer Variante, den [[B*-Baum|B*-Bäumen]]. Spezialisierungen von B-Bäumen sind wiederum [[2-3-4-Baum|2-3-4-Bäume]], welche oft als [[Rot-Schwarz-Baum|Rot-Schwarz-Bäume]] implementiert werden.

Ein Spezialfall der AVL-Bäume sind [[Fibonacci-Baum|Fibonacci-Bäume]]. Sie werden vor allem bei Effizienzüberlegungen zu höhen-balancierten Bäumen, insbesondere AVL-Bäumen, als Extremfälle und Vergleichsobjekte herangezogen.

Nicht sortiert, aber „verschachtelt“ sind geometrische Baumstrukturen wie der [[R-Baum]] und seine Varianten. Hier werden nur diejenigen Teilbäume durchsucht, die sich mit dem angefragten Bereich überlappen.

Bäume sind in ihrem Aufbau zwar mehrdimensional jedoch in der Verkettung der Objekte oft unidirektional. Die Verkettung der gespeicherten Objekte beginnt bei der Wurzel des Baums und von dort in Richtung der Knoten des Baums.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung eines ungerichteten Graphen mit [[Adjazenzliste|Adjazenzlisten]]. Der ungerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''UndirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die auf der Konsole ausgibt, ob der Graph ein Baum ist.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/check-given-graph-tree/ Check if a given graph is tree or not]</ref><syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;
using System.Linq;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
public int index;
public string value;
public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten
}

// Deklariert die Klasse für den ungerichteten Graphen
class UndirectedGraph
{
public HashSet<Node> nodes = new HashSet<Node>();

// Diese Methode verbindet die Knoten node1 und node2 miteinander.
public void ConnectNodes(Node node1, Node node2)
{
node1.adjacentNodes.Add(node2);
node2.adjacentNodes.Add(node1);
}

// Diese rekursive Methode prüft, ob der Graph Zyklen enthält
public bool IsCyclic(Node node, Dictionary<Node, bool> areConnected, Node parentNode)
{
areConnected[node] = true; // Setzt den aktuellen Knoten als durchlaufen
foreach (Node nextNode in node.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des aktuellen Knotens durchläuft
{
if (!areConnected[nextNode]) // Wenn der benachbarten Knoten noch nicht durchlaufen wurde
{
if (IsCyclic(nextNode, areConnected, node)) // Rekursiver Aufruf der Methode mit dem benachbarten Knoten als aktuellen Knoten
{
return true; // Wenn der rekursive Aufruf true zurückgibt
}
}
else // Wenn der benachbarten Knoten schon durchlaufen wurde ...
{
if (nextNode != parentNode) // ... und der benachbarte Knoten nicht der Elternknoten ist, bilden die durchlaufenen Knoten einen Zyklus
{
return true;
}
}
}
return false; // Sonst enthält der Graph keinen Zyklus
}

// Diese Methode prüft, ob der Graph ein Baum ist.
public bool IsTree()
{
Dictionary<Node, bool> areConnected = new Dictionary<Node, bool>();
foreach (Node node in nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
{
areConnected.Add(node, false); // Setzt alle Knoten als nicht durchlaufen
}
if (IsCyclic(nodes.ElementAt(0), areConnected, null)) // Wenn die Komponente mit dem ersten Knoten Zyklen enthält, false zurückgeben
{
return false;
}
foreach (Node node in nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
{
if (!areConnected[node]) // Wenn ein Knoten nicht verbunden ist, dann false zurückgeben
{
return false;
}
}
return true; // Sonst ist der Graph ein Baum
}
}

class Program
{
// Hauptmethode, die das Programm ausführt
public static void Main(string[] args)
{
// Deklariert und initialisiert 5 Knoten
Node node1 = new Node{index = 0, value = "A"};
Node node2 = new Node{index = 1, value = "B"};
Node node3 = new Node{index = 2, value = "C"};
Node node4 = new Node{index = 3, value = "D"};
Node node5 = new Node{index = 4, value = "E"};
// Deklariert und initialisiert ein Array mit den Knoten
Node[] nodes = {node1, node2, node3, node4, node5};
// Erzeugt einen ungerichteten Graphen
UndirectedGraph undirectedGraph = new UndirectedGraph();
int numberOfNodes = nodes.Length;
for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
{
undirectedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu
}
// Verbindet Knoten des Graphen miteinander
undirectedGraph.ConnectNodes(node2, node1);
undirectedGraph.ConnectNodes(node1, node3);
undirectedGraph.ConnectNodes(node1, node4);
undirectedGraph.ConnectNodes(node4, node5);
if (undirectedGraph.IsTree()) // Aufruf der Methode, die prüft, ob der Graph ein Baum ist
{
Console.WriteLine("Der Graph ist ein Baum."); // Ausgabe auf der Konsole
}
else
{
Console.WriteLine("Der Graph ist kein Baum."); // Ausgabe auf der Konsole
}

Console.ReadLine();
}
}
</syntaxhighlight>

== Siehe auch ==
* [[Baumdiagramm]]
* [[Feld (Datentyp)]]
* [[Liste (Datenstruktur)]]
* [[Menge (Datenstruktur)]]
* [[Stapelspeicher]]
* [[Warteschlange (Datenstruktur)]]

== Einzelnachweise ==
<references />

== Literatur ==
* Hartmut Ernst, Jochen Schmidt, Gerd Beneken: ''Grundkurs Informatik. Grundlagen und Konzepte für die erfolgreiche IT-Praxis – Eine umfassende, praxisorientierte Einführung'', 5. Auflage, Springer, Wiesbaden 2015, S. 523–596
* Heinz-Peter Gumm, Manfred Sommer: ''Einführung in die Informatik'', 10. Aufl., Oldenbourg, München 2013, S. 372–398

[[Kategorie:Datenstruktur]]

Baum (Datenstruktur) - Versionsgeschichte

imported>Serols: Änderungen von ~2026-49189-6 (Diskussion) rückgängig gemacht (HG) (3.4.13)