Wie strukturieren Bäume Daten hierarchisch?
Von der Liste zur Hierarchie: Das Konzept des Baums
Du kennst bereits lineare Datenstrukturen wie Arrays oder verkettete Listen sowie das grundlegende Konzept von Graphen. Ein Baum (Tree) ist im Grunde ein spezieller, kreisfreier Graph, der Daten nicht linear, sondern hierarchisch abbildet. Stell dir die Ordnerstruktur auf deinem Computer vor: Ein Hauptordner enthält Unterordner, die wiederum Dateien enthalten.
Ein Baum besteht aus Knoten (Nodes), die die eigentlichen Daten speichern, und gerichteten Kanten (Edges), die die Verbindungen zwischen ihnen darstellen.
- Wurzel (Root): Der oberste Knoten des Baums. Er ist der einzige Knoten ohne Vorgänger.
- Elternknoten (Parent) & Kindknoten (Child): Ein Knoten, der auf untergeordnete Knoten verweist, ist deren Elternknoten. Die referenzierten Knoten sind die Kinder.
- Blätter (Leaves): Knoten am unteren Ende des Baums, die keine eigenen Kinder mehr haben (vergleichbar mit einzelnen Dateien in einem Ordner).
Der Binärbaum: Struktur mit maximal zwei Kindern
Ein Binärbaum (Binary Tree) ist eine spezielle, in der Informatik extrem wichtige Form des Baums. Seine definierende Eigenschaft ist eine strikte Beschränkung: Jeder Knoten darf höchstens zwei Kindknoten besitzen. Diese werden explizit als linkes Kind und rechtes Kind bezeichnet.
Diese Struktur ist rekursiv aufgebaut. Das bedeutet: Jedes Kind eines Knotens ist selbst wieder die Wurzel eines eigenen, kleineren Teilbaums. Diese Vorhersehbarkeit (maximal zwei Verweise pro Knoten) macht die programmtechnische Umsetzung und Verwaltung im Speicher besonders effizient.
# Beispielhafter Aufbau eines Knotens in einem Binärbaum
class TreeNode:
def __init__(self, wert):
self.wert = wert
self.links = None # Verweis auf das linke Kind
self.rechts = None # Verweis auf das rechte KindWege durch den Baum: Die Traversierung
Da ein Baum nicht linear ist, kannst du ihn nicht einfach von "vorne nach hinten" durchlaufen. Den systematischen Besuch aller Knoten nennt man Traversierung. Bei Binärbäumen gibt es drei Hauptstrategien, die sich danach richten, wann der Elternknoten verarbeitet wird:
- Preorder (Wurzel -> Links -> Rechts): Du verarbeitest zuerst den aktuellen Knoten, steigst dann in den linken und danach in den rechten Teilbaum ab.
- Praxisbeispiel: Ideal, um eine exakte Kopie des Baums zu erstellen.
- Inorder (Links -> Wurzel -> Rechts): Du gehst erst ganz nach links, verarbeitest dann den Knoten und gehst dann nach rechts.
- Praxisbeispiel: Liefert bei Suchbäumen die Werte in aufsteigend sortierter Reihenfolge.
- Postorder (Links -> Rechts -> Wurzel): Du verarbeitest erst beide Kinder komplett, bevor du den Elternknoten anfasst.
- Praxisbeispiel: Perfekt zum Löschen eines Baums aus dem Speicher, da du erst die Blätter entfernst, bevor du die Referenz des Elternknotens löschst.
Wie ermöglicht der binäre Suchbaum (BST) blitzschnelle Suchanfragen?
Die strenge Ordnung des binären Suchbaums
Ein normaler Binärbaum gibt nicht vor, wo bestimmte Werte gespeichert werden. Ein binärer Suchbaum (Binary Search Tree - BST) hingegen etabliert eine strikte Ordnungsregel, die ihn zu einer extrem mächtigen Datenstruktur macht:
- Alle Werte im linken Teilbaum eines Knotens sind kleiner als der Wert des Knotens selbst.
- Alle Werte im rechten Teilbaum eines Knotens sind größer als der Wert des Knotens.
Stell dir vor, die Wurzel deines Baums hat den Wert 50. Wenn du nun die Zahl 20 einfügst, wandert sie nach links. Fügst du die 70 ein, wandert sie nach rechts. Diese Regel gilt rekursiv für jeden einzelnen Knoten im gesamten Baum.
Effiziente Suche: Das Prinzip des halbierten Suchraums
Die Sortierung des BST funktioniert wie das Spiel "Zahlenraten" (Ist die Zahl größer oder kleiner?). Wenn du in unserem Beispielbaum (Wurzel 50) die Zahl 15 suchst, vergleichst du sie mit der Wurzel. Da 15 kleiner als 50 ist, weißt du sofort: Die gesuchte Zahl kann sich nur im linken Teilbaum befinden. Du ignorierst den kompletten rechten Teilbaum.
Mit jedem Schritt nach unten halbiert sich im Idealfall die Menge der verbleibenden Knoten. Während du bei einer verketteten Liste im schlimmsten Fall jedes Element prüfen musst (Zeitkomplexität O(n)), benötigst du im BST nur einen einzigen Pfad von der Wurzel bis zum Ziel. Die durchschnittliche Zeitkomplexität sinkt drastisch auf O(log n). Bei einer Million Einträgen brauchst du so maximal etwa 20 Vergleiche!
def suche_im_bst(knoten, gesuchter_wert):
if knoten is None:
return False # Ende erreicht, Wert nicht gefunden
if gesuchter_wert == knoten.wert:
return True # Volltreffer!
if gesuchter_wert < knoten.wert:
# Wert ist kleiner -> suche links weiter
return suche_im_bst(knoten.links, gesuchter_wert)
else:
# Wert ist größer -> suche rechts weiter
return suche_im_bst(knoten.rechts, gesuchter_wert)Die Schwachstelle: Wenn der Baum zur Linie entartet
Die überragende Geschwindigkeit von O(log n) gilt nur, wenn der Baum balanciert ist – also wenn der linke und rechte Teilbaum ungefähr gleich tief sind.
Es gibt jedoch ein Worst-Case-Szenario: Stell dir vor, du fügst bereits sortierte Daten (z. B. 1, 2, 3, 4, 5) in einen leeren BST ein. Da jeder neue Wert größer ist als der vorherige, wird er immer als rechtes Kind angehängt. Es entsteht keine verzweigte Baumstruktur, sondern eine lange, dünne Linie nach rechts unten.
Diesen Zustand nennt man einen entarteten Baum. Er verhält sich technisch exakt wie eine einfache verkettete Liste. Die Suche nach der 5 erfordert nun wieder den Besuch jedes einzelnen Knotens, die Effizienz bricht auf O(n) ein. Um dies in der Praxis zu verhindern, nutzen moderne Systeme sogenannte selbst-balancierende Bäume, die ihre Struktur beim Einfügen automatisch optimieren.
Teste dein Wissen
Du entwickelst ein Dateisystem für ein neues Betriebssystem. Warum wählst du für die Ordnerstruktur einen Baum statt eines Arrays?