Baum
aus www.iwiki.de, der freien Wissensdatenbank
Bäume sind für die Informatik zentrale Datenstrukturen, die ähnlich den Listen aus Knoten gebildet werden. Jeder Knoten mit Ausnahme des Startknotens besitzt genau einen Vorgängerknoten. Im Unterschied zu Listen kann jeder Knoten nicht nur einen, sondern mehrere Nachfolger besitzen. Der Anfangsknoten eines Baumes wird Wurzel genannt. Die Endknoten eines Baumes heißen Sie finden zahlreiche unterschiedliche Anwendungsgebiete,Z.B. als Suchbäume zum Finden von Elementen auf geordneten Datenstrukturen, als Entscheidungsbäume zur Organisation von Entscheidungen, als Strukturbäume zur Repräsentation der Struktur von Programmen oder Bäume als Datenmodelle.
Inhaltsverzeichnis |
Eigenschaften eines Baumes
- ein n-Baum (n-tree) ist entweder leer oder besteht aus einem Wurzelknoten und n gerichteten Kanten. Jede Kante stellt einen Verweis auf einen (Teil-)Baum dar.
- die von einem Knoten (node) über eine Kante (edge) direkt erreichbaren Knoten heißen Kinder, der Knoten selbst Elternknoten.
- Ein Knoten, der nur Verweise auf leere Teilbäume enthält, wird als Blatt (leave) bezeichnet.
- Ein Weg besteht aus einer Folge benachbarter Kanten. Zwei Kanten sind benachbart, wenn der Endknoten der ersten Kante der Anfangsknoten der zweiten Kante ist.
- Jeder Knoten ist auf genau einem Weg von der Wurzel aus erreichbar. Das Niveau eines Knotens ist die Länge des Weges (= Anzahl der benachbarten Kanten) von der Wurzel an.
- Die Tiefe eines Baumes ist durch das maximale Niveau eines Blattes definiert.
- Hat ein Baum nur Knoten vom Grad 1, 2 oder 3, so heisst er Binärbaum.
- Ein Baum heißt ausgeglichen, wenn für jeden Knoten gilt, dass sich die Anzahl der Knoten seiner Teilbäume maximal um eins unterscheidet.
Einsatzgebiet
Bäume werden in der Informatik zu folgenden Zwecken eingesetzt:
- zur Modellierung einer logischen Beziehung durch eine entsprechende Datenstruktur: Begriffshierarchie, Dateihierarchie, Stücklisten (Teil-Einzelteil-Beziehung), Stammbaum, Operatorbaum.
- als Datenstruktur zum Suchen und Sortieren: Suchbaum
Beispiel eines Baums
Beispiel eines Baumes
Links
Literatur
- Bernd Breutmann: data and algorithms. Carl-Hanser-Verl., Leipzig 2001, ISBN 3-446-21591-3
- Michael Goodrich, Roberto Tamassia: Data Structures and Algorithms in Java 2nd Edition. John Wiley and Sons, New York 2001, ISBN 0-471-38367-8
