Baum (Datenstruktur)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Die Artikel Baum_(Datenstruktur) und Gewurzelter Baum überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. Wizard in Training (Diskussion) 12:48, 25. Sep. 2019 (CEST)
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 Wurzel mehrere 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.

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 Anahl 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 .

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

Terminologie[Bearbeiten | Quelltext bearbeiten]

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. Es ist dann üblich, bei den untergeordneten Knoten von Kindern und bei dem verweisenden Knoten von einem Elternteil zu sprechen. 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 ein Niveau. Die Höhe eines Baumes ist dann die maximale Tiefe eines Knotens.

Binärbaum[Bearbeiten | Quelltext bearbeiten]

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

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

Ein Spezialfall der AVL-Bäume sind Fibonaci-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.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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