Ein Baum ist eine hierarchische Datenstruktur, in der Elemente (Knoten) über Kanten verbunden sind und genau eine Wurzel den Ausgangspunkt bildet. Anders als bei einer verketteten Liste oder einer Hash-Tabelle entsteht so eine verzweigte Struktur, die sich hervorragend für verschachtelte und sortierte Daten eignet.
Aufbau eines Baums
Die wichtigsten Begriffe: Der oberste Knoten heißt Wurzel (root). Jeder Knoten kann beliebig viele Kindknoten haben; der Vorgänger eines Knotens ist sein Elternknoten. Knoten ohne Kinder nennt man Blätter (leaves). Ein Baum mit n Knoten hat immer genau n-1 Kanten, und zwischen zwei beliebigen Knoten existiert genau ein Pfad. Die Tiefe eines Knotens misst die Anzahl der Kanten bis zur Wurzel, die Höhe des Baums die maximale Tiefe.
Arten von Bäumen
- Binärbaum: Jeder Knoten hat höchstens zwei Kinder (links und rechts).
- Binärer Suchbaum: Sortierte Binärbäume, bei denen alle Werte im linken Teilbaum kleiner und im rechten Teilbaum größer als der Elternknoten sind — dadurch sind Suchen in O(log n) möglich.
- Balancierte Bäume: Sie halten die Höhe automatisch klein (etwa AVL- oder Rot-Schwarz-Bäume) und verhindern so entartete, lineare Strukturen.
- B-Bäume: Mehrwegbäume, die in Datenbanken als Index verwendet werden — sie minimieren die Anzahl der Plattenzugriffe.
Traversierung und Anwendungen
Beim Durchlaufen (Traversieren) unterscheidet man Pre-Order (Wurzel, dann links, dann rechts), In-Order (links, Wurzel, rechts — liefert bei Suchbäumen die sortierte Reihenfolge) und Post-Order (links, rechts, Wurzel). Eine Ebene nach der anderen durchläuft die Level-Order, die mit einer Queue arbeitet. Rekursive Traversierung ist ein klassisches Beispiel für Rekursion.
Bäume stecken überall dahinter: Dateisysteme, die DOM-Struktur von Webseiten, Entscheidungsbäume im maschinellen Lernen, Suchindizes und der Heap als besondere Baumform. Eng verwandt ist der Graph: Ein Baum ist ein spezieller, kreisfreier Graph. Grundlegend für alle Varianten sind Algorithmen und der passende Datentyp. Bei der Umsetzung in Programmiersprachen kommen häufig Stack und Queue zum Einsatz.