Baum (Datenstruktur)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
BinärBaum Beschriftung.jpg

In der Informatik ist ein Baum eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen. 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.

Typischerweise wird gefordert, dass in Bäumen bis auf die Wurzel, die keine Eltern hat, jeder Knoten nur genau ein Elternteil haben darf.

Ein wichtiger Spezialfall ist der Binärbaum, in welchem jeder Knoten nur höchstens zwei Kinder haben darf.

Terminologie[Bearbeiten | Quelltext bearbeiten]

Allgemein werden alle denkbaren Begriffe der Graphentheorie entlehnt. Der Unterschied zu Bäumen in der Graphentheorie besteht darin, dass für Datenstrukturen typischerweise den Kanten eine Richtung vorgegeben ist und in diesen Bäumen die Wurzel somit eindeutig bestimmt ist. 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.

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