Datenstrukturen II (Hierarchisch & Vernetzt)
Bäume, Suchbäume und Graphen — Datenstrukturen mit Familienverhältnissen.
Nach Arrays und Linked Lists denkst du vielleicht, Daten sitzen immer in einer Reihe. Aber die meisten Beziehungen in der echten Welt sind hierarchisch (Ordner, Organigramme) oder vernetzt (Straßen, soziale Netzwerke). Bäume und Graphen erfassen diese Formen — und die Algorithmen, die sie durchlaufen, treiben alles an, von Webbrowsern bis zu Navigations-Apps.
Dieser Artikel stellt die drei Strukturen vor, die lineare Daten und Suchalgorithmen verbinden: Bäume, binäre Suchbäume und Graphen.
Bäume — Hierarchie mit Regeln
Definition
Baum (Tree)
Analogie
Definition
Echte Dateisysteme haben symbolische Links, die mehrere Pfade zur selben Datei erzeugen — das verletzt die Baum-Eigenschaft und macht die Struktur zum Graphen. Auch ein Familienstammbaum ist streng genommen kein Baum, weil reale Personen zwei biologische Eltern haben.
Beispiel: Der DOM-Baum
<html> (Tiefe 0, Wurzel)
<head> (Tiefe 1, Blatt)
<body> (Tiefe 1)
<div> (Tiefe 2)
<p> (Tiefe 3, Blatt)
Höhe = 3, Kanten = Knoten - 1 = 4Der Browser durchläuft diesen Baum von <html> abwärts — das ist die Basis für document.querySelector. Jeder Knoten außer der Wurzel hat genau einen Elternknoten, und es gibt keine Zyklen.
Keine Zyklen, eine Wurzel, genau ein Pfad zwischen zwei Knoten. Kanten = n - 1. Strenge Hierarchie.
Zyklen erlaubt, keine Wurzel nötig, mehrere Pfade möglich. Flexible Vernetzung ohne feste Hierarchie.
Achtung
Irrtum: Bäume und Graphen sind völlig verschieden
Jeder Baum IST ein Graph — genauer gesagt ein zusammenhängender, azyklischer Graph. Die Beziehung ist Teilmenge, nicht getrennte Kategorie. Das zu verstehen verhindert, dass du Bäume und Graphen als unverwandte Themen behandelst.
Binäre Suchbäume — Geordnet für Geschwindigkeit
Definition
Binärer Suchbaum (BST)
Analogie
Definition
Ein Telefonbuch ist flach und sequentiell; ein BST ist hierarchisch. Außerdem hängt die logarithmische Garantie von der Balance ab — sortiertes Einfügen erzeugt ein "einseitiges Telefonbuch" (verkettete Liste).
Merke
BST-Suche: Schritt für Schritt
- 1. Suche 40: Vergleiche mit Wurzel 50 → 40 < 50, gehe links
- 2. Vergleiche mit 30 → 40 > 30, gehe rechts
- 3. Vergleiche mit 40 → gefunden! Nur 3 Vergleiche
- 4. Bei 1.000.000 Elementen: ~20 Vergleiche statt ~500.000linear
Bei jedem Schritt wird die Hälfte der verbleibenden Daten verworfen. Deshalb ist die Suche logarithmisch — genau wie die binäre Suche in einem sortierten Array, aber mit dynamischem Einfügen und Löschen.
Merke
Balance entscheidet
Balanciert vs. Degeneriert
Dieselbe Datenstruktur, komplett unterschiedliches Verhalten — nur abhängig von der Einfüge-Reihenfolge. Deshalb wurden selbstbalancierende Bäume erfunden.
Achtung
Irrtum: BST-Suche ist immer O(log n)
Nur bei annähernd balanciertem Baum. Sortiertes Einfügen erzeugt eine Kette mit Höhe n − 1 — nicht besser als lineare Suche. Genau deshalb gibt es selbstbalancierende Varianten wie AVL- und Red-Black-Bäume.
AVL-Bäume und Red-Black-Bäume rotieren Knoten bei Bedarf nach dem Einfügen oder Löschen, um die Höhe in der Größenordnung log₂ n zu halten (AVL höchstens etwa 1,44 · log₂ n, Red-Black höchstens etwa 2 · log₂ n). Der Entwickler zahlt etwas Overhead pro Operation — gewinnt aber die Garantie, dass die Suche niemals zu O(n) degeneriert. Viele Standardbibliotheken verwenden Red-Black-Bäume intern, etwa TreeMap in Java und üblicherweise std::map in C++.
Interaktiv: BST-Suche Schritt für Schritt
Du hast gelernt, dass ein BST bei jedem Vergleich den Suchraum halbiert. Klicke dich durch die Schritte einer echten Suche und beobachte, wie der Algorithmus den Baum durchläuft — Knoten für Knoten, Vergleich für Vergleich.
Die Suche beginnt an der Wurzel (50). Der Zielwert 40 ist kleiner als 50 — also geht der Algorithmus nach links.
Graphen — Das allgemeine Netzwerk
Definition
Graph
Analogie
Definition
U-Bahn-Netze sind an Geografie, euklidische Distanzen und physische Gesetze gebunden. In abstrakten Graphen gibt es solche Grenzen nicht — ein Knoten in Tokio kann eine direkte Kante mit Kosten 0 zu einem Knoten in Berlin haben.
Merke
Graphen in der echten Welt
Straßennetz: Städte als Knoten, Straßen als gewichtete Kanten — Dijkstras Algorithmus (1959) findet den kürzesten Weg. Das Web: Seiten als Knoten, Links als gerichtete Kanten — Googles PageRank bewertet Seiten nach eingehenden Links. Soziale Netzwerke: Nutzer als Knoten, Beziehungen als Kanten. Vorwärtsgerichtete neuronale Netze: Neuronen als Knoten, gewichtete Verbindungen als gerichtete Kanten — ein gerichteter azyklischer Graph (DAG).
Achtung
Irrtum: Bei gerichteten Graphen kann man immer in beide Richtungen
Eine gerichtete Kante A→B bedeutet NICHT, dass B→A existiert. Auf X (früher Twitter): Wenn du jemandem folgst, folgt er dir nicht automatisch zurück. Jede Richtung braucht eine eigene explizite Kante.
Zwei gängige Darstellungen: Adjazenzliste (Liste der Nachbarn pro Knoten — speichereffizient bei wenigen Kanten) und Adjazenzmatrix (n×n-Tabelle — schnelle Kantenlookups, aber speicherhungrig bei großen, dünn besetzten Graphen). Diese Darstellung als Python-Dictionary (Adjazenzliste) ist das Fundament für den Artikel „Suche im Graphen“, in dem Algorithmen wie die Breitensuche (BFS) den kürzesten Weg durch ein Netzwerk finden.
# Adjazenzliste (Python dict)
graph = {
"A": ["B", "C"],
"B": ["C"],
"C": ["A"]
}
# Adjazenzmatrix
# A B C
# A [ 0, 1, 1 ]
# B [ 0, 0, 1 ]
# C [ 1, 0, 0 ]Merke
Das Wichtigste
- Ein Baum ist ein zusammenhängender, azyklischer Graph mit einer Wurzel. Seine Strenge (keine Zyklen, ein Elternknoten pro Knoten) ermöglicht rekursive Algorithmen und effiziente Suche.
- Ein BST fügt einem Binärbaum eine Ordnungsregel hinzu und erreicht O(log n)-Suche bei Balance — degeneriert aber zu O(n) ohne Balance. Balance ist der entscheidende Qualitätsfaktor.
- Graphen sind die allgemeinste Beziehungsstruktur: gerichtet oder ungerichtet, gewichtet oder ungewichtet, mit oder ohne Zyklen — und jeder Baum ist nur ein sehr disziplinierter Graph.
Prüfen
Quiz: Hierarchische Datenstrukturen
Was unterscheidet einen Baum von einem allgemeinen Graphen?
Wähle eine Antwort
1. Was unterscheidet einen Baum von einem allgemeinen Graphen?
2. Ein balancierter BST hat 1.000.000 Elemente. Wie viele Vergleiche braucht eine Suche ungefähr?
3. Ein soziales Netzwerk hat Freundschaften (gegenseitig) und Follows (einseitig). Welche Graphtypen brauchst du?
4. Du fügst die Elemente [10, 20, 30, 40, 50] in dieser Reihenfolge in einen BST ein. Warum ist die Suche im Ergebnis langsam?
Prüfen
Checkpoint: Verstehst du hierarchische Datenstrukturen?
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen