Baum (Datenstruktur)
Ein Baum ist eine Datenstruktur, in der auch größere Datenmengen so abgelegt werden können, dass besonders schnell auf sie zugegriffen werden kann; schneller, als dies etwa bei einer verketteten Liste möglich wäre.
Bäume allgemein
Allgemein besteht ein Baum aus Knoten und Kanten. Diese Kanten haben eine Richtung und zeigen vom so genannten Vaterknoten zu seinem Kind. Es darf nie einen Kreis aus Kanten geben. Hat ein Knoten keine Kinder, wird er als Blatt bezeichnet. Ein Knoten ohne Vater heißt Wurzel.
Wenn man einen Baum grafisch darstellt, zeichnet man unintuitiverweise die Wurzel nach oben und die Blätter nach unten.
Mathematisch ist ein Baum nichts weiter als ein gerichteter kreisfreier zusammenhängender Graph.
Die folgende Abbildung zeigt beispielhaft einen Baum, der einige Staaten, Bundesländer und Städte Europas darstellt. Jede Kante entspricht dabei einer X liegt in Y-Beziehung: Kufstein gehört zu Tirol, Tirol gehört zu Österreich, Österreich gehört zu Europa.
Binäre Bäume
Ein binärer Baum ist ein Baum, in dem jeder Knoten höchstens zwei Kinder haben darf.
Ein binärer Baum kann sehr effizient als Array gespeichert werden, weil sich für jeden Knoten die Indizes seiner Kinder leicht berechnen lassen:
Der Knoten hat dabei immer genau die Kinder und .
In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:
Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.
