Datenstrukturen II (Hierarchisch & Vernetzt)

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

Dein Dateisystem ist ein Baum: Das Stammverzeichnis (C:\ oder /) steht ganz oben, Ordner sind innere Knoten, Dateien sind Blätter. Jede Datei hat genau einen übergeordneten Ordner. Es gibt keine Schleifen. Um eine Datei zu finden, navigierst du: Stammverzeichnis, Ordner, Unterordner, Datei — ein einziger eindeutiger Pfad.

Analogie:

Dein Dateisystem ist ein Baum: Das Stammverzeichnis (C:\ oder /) steht ganz oben, Ordner sind innere Knoten, Dateien sind Blätter. Jede Datei hat genau einen übergeordneten Ordner. Es gibt keine Schleifen. Um eine Datei zu finden, navigierst du: Stammverzeichnis, Ordner, Unterordner, Datei — ein einziger eindeutiger Pfad.

Definition:

Ein Baum ist ein zusammenhängender, azyklischer Graph mit einem Wurzelknoten. Terminologie: Wurzel (oberster Knoten), Blatt (Knoten ohne Kinder), Tiefe (Abstand zur Wurzel), Höhe (maximale Tiefe), Teilbaum (beliebiger Knoten + seine Nachkommen). Anzahl der Kanten = n - 1. Zwischen je zwei Knoten existiert genau ein Pfad. Bäume sind inhärent rekursiv: Jeder Teilbaum ist selbst ein Baum.

Echte Dateisysteme haben symbolische Links, die mehrere Pfade zur selben Datei erzeugen — das verletzt die Baum-Eigenschaft und macht die Struktur zum Graphen. Auch der Stammbaum bricht, weil reale Personen zwei biologische Eltern haben.

<html>          (Tiefe 0, Wurzel)
  <head>        (Tiefe 1)
  <body>        (Tiefe 1)
    <div>       (Tiefe 2)
      <p>       (Tiefe 3, Blatt)

Höhe = 3, Kanten = Knoten - 1 = 4

Der Browser durchläuft diesen Baum von <html> abwärts — das ist die Basis für document.querySelector. Jeder Knoten hat genau einen Elternknoten, und es gibt keine Zyklen.

Baum

Keine Zyklen, eine Wurzel, genau ein Pfad zwischen zwei Knoten. Kanten = n - 1. Strenge Hierarchie.

Graph

Zyklen erlaubt, keine Wurzel nötig, mehrere Pfade möglich. Flexible Vernetzung ohne feste Hierarchie.

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

Stell dir ein Telefonbuch vor: Du schlägst in der Mitte auf, prüfst ob dein Name davor oder dahinter steht, und wiederholst das in der passenden Hälfte. Ein BST macht dieses Halbieren zu einer dauerhaften Struktur — jeder Knoten ist ein Entscheidungspunkt, der dich nach links (kleiner) oder rechts (größer) lenkt.

Analogie:

Stell dir ein Telefonbuch vor: Du schlägst in der Mitte auf, prüfst ob dein Name davor oder dahinter steht, und wiederholst das in der passenden Hälfte. Ein BST macht dieses Halbieren zu einer dauerhaften Struktur — jeder Knoten ist ein Entscheidungspunkt, der dich nach links (kleiner) oder rechts (größer) lenkt.

Definition:

Ein BST ist ein Binärbaum (max. 2 Kinder pro Knoten) mit einer Ordnungsinvariante: Alle Schlüssel im linken Teilbaum < Knotenschlüssel < alle Schlüssel im rechten Teilbaum. Die Suche halbiert den Suchraum bei jedem Schritt — O(log n) bei balanciertem Baum (Höhe ≈ log₂ n). Werden Elemente in sortierter Reihenfolge eingefügt, degeneriert der BST zu einer verketteten Liste mit Höhe n und O(n)-Operationen.

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).

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.000 (linear)

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.

Balanciert vs. Degeneriert

Balancierter BST — O(log n) Einfügen von [50, 30, 70, 20, 40, 60, 80]: Höhe ≈ 3 (log₂ 7). Suche: max. 3 Vergleiche für 7 Elemente.

Degenerierter BST — O(n) Einfügen von [10, 20, 30, 40, 50]: Kette nach rechts, Höhe = 4. Suche nach 50: 4 Vergleiche — nicht besser als eine verkettete Liste.

Dieselbe Datenstruktur, komplett unterschiedliches Verhalten — nur abhängig von der Einfüge-Reihenfolge. Deshalb wurden selbstbalancierende Bäume erfunden.

Nur bei annähernd balanciertem Baum. Sortiertes Einfügen erzeugt eine Kette mit Höhe n — 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 nach jedem Einfügen oder Löschen, um die Höhe bei ~log₂ n zu halten. Der Entwickler zahlt etwas Overhead pro Operation — gewinnt aber die Garantie, dass die Suche niemals zu O(n) degeneriert. Die meisten Standardbibliotheken (z.B. std::map in C++, TreeMap in Java) verwenden Red-Black-Bäume intern.

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.

Suche: 40

Schritt 1 / 3Wurzel vergleichen

Die Suche beginnt an der Wurzel (50). Der Zielwert 40 ist kleiner als 50 — also geht der Algorithmus nach links.

40 < 50 → left

Graphen — Das allgemeine Netzwerk

Stell dir einen U-Bahn-Plan vor. Stationen sind Knoten, Gleisverbindungen sind Kanten. Manche Linien sind Einbahnstraßen (gerichtet); Fahrzeiten sind Kantengewichte. Zwischen zwei Stationen gibt es oft mehrere Routen mit unterschiedlichen Gesamtfahrzeiten — die schnellste zu finden ist ein Kürzeste-Wege-Problem. Anders als bei einem Baum hat ein U-Bahn-Netz Schleifen und keine einzelne Wurzel-Station.

Analogie:

Stell dir einen U-Bahn-Plan vor. Stationen sind Knoten, Gleisverbindungen sind Kanten. Manche Linien sind Einbahnstraßen (gerichtet); Fahrzeiten sind Kantengewichte. Zwischen zwei Stationen gibt es oft mehrere Routen mit unterschiedlichen Gesamtfahrzeiten — die schnellste zu finden ist ein Kürzeste-Wege-Problem. Anders als bei einem Baum hat ein U-Bahn-Netz Schleifen und keine einzelne Wurzel-Station.

Definition:

Ein Graph besteht aus Knoten (Vertices) und Kanten (Edges), die Knotenpaare verbinden. Anders als Bäume erlauben Graphen Zyklen, mehrere Pfade zwischen Knoten und keine festgelegte Wurzel. Typen: ungerichtet (Kanten sind symmetrisch) vs. gerichtet (Kanten haben eine Richtung); ungewichtet vs. gewichtet (Kanten tragen Kosten wie Entfernung oder Zeit). Historisch: Eulers Königsberger Brückenproblem (1736) — die erste formale Graphenanalyse.

U-Bahn-Netze sind an Geografie, euklidische Distanzen und physische Gesetze gebunden. In abstrakten Graphen gibt es solche Grenzen nicht — ein Knoten in Tokyo kann eine direkte Kante mit Kosten 0 zu einem Knoten in Berlin haben.

Ungerichtet Kanten gehen in beide Richtungen. Beispiel: Freundschaft in Facebook — wenn A mit B befreundet ist, ist B mit A befreundet.

Gerichtet Kanten haben eine Richtung. Beispiel: Twitter-Follow — A folgt B bedeutet nicht, dass B A folgt.

Gewichtet Kanten tragen Kosten (Entfernung, Zeit). Beispiel: Straßennetz mit Kilometerangaben.

Ungewichtet Kanten sind gleich. Beispiel: "Kennt" in einem sozialen Netzwerk — ohne Intensität.

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. Neuronale Netze: Schichten als gerichteter azyklischer Graph (DAG).

Eine gerichtete Kante A→B bedeutet NICHT, dass B→A existiert. Auf 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 das nächste Modul, in dem wir Algorithmen wie die Breitensuche (BFS) schreiben, um den kürzesten Weg durch ein Netzwerk zu 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 ]

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.

Was unterscheidet einen Baum von einem allgemeinen Graphen?

Bäume können Zyklen haben

Ein Baum ist ein zusammenhängender, azyklischer Graph mit einer Wurzel — jeder Baum ist ein Graph, aber nicht jeder Graph ist ein Baum

Bäume haben immer gewichtete Kanten

Bäume haben immer genau zwei Kinder pro Knoten

1. Was unterscheidet einen Baum von einem allgemeinen Graphen?

☐ A) Bäume können Zyklen haben
☐ B) Ein Baum ist ein zusammenhängender, azyklischer Graph mit einer Wurzel — jeder Baum ist ein Graph, aber nicht jeder Graph ist ein Baum
☐ C) Bäume haben immer gewichtete Kanten
☐ D) Bäume haben immer genau zwei Kinder pro Knoten

2. Ein balancierter BST hat 1.000.000 Elemente. Wie viele Vergleiche braucht eine Suche ungefähr?

☐ A) 500.000
☐ B) ~20
☐ C) 1.000.000
☐ D) 100

3. Ein soziales Netzwerk hat Freundschaften (gegenseitig) und Follows (einseitig). Welche Graphtypen brauchst du?

☐ A) Beides ungerichtet
☐ B) Beides gerichtet
☐ C) Freundschaften: ungerichtet. Follows: gerichtet
☐ D) Freundschaften: gewichtet. Follows: ungewichtet

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?

☐ A) BSTs können nicht mehr als 4 Elemente speichern
☐ B) Die sortierte Einfüge-Reihenfolge erzeugt eine Kette nach rechts (Höhe = n), und die Suche wird O(n) statt O(log n)
☐ C) BSTs können keine ganzen Zahlen speichern
☐ D) Der Baum hat keine Wurzel

Auflösung: 1) B · 2) B · 3) C · 4) B

Checkpoint: Verstehst du hierarchische Datenstrukturen?

Ich kann einen Baum durch seine Regeln definieren (Wurzel, Eltern, Kinder, Blätter, keine Zyklen) und erklären, warum jeder Baum ein Graph ist, aber nicht jeder Graph ein Baum.
Ich kann eine Suche in einem BST nachverfolgen und erklären, wann sie O(log n) ist und wann sie zu O(n) degeneriert.
Ich kann gerichtete von ungerichteten und gewichtete von ungewichteten Graphen unterscheiden und je ein Beispiel aus der echten Welt nennen.

Datenstrukturen II (Hierarchisch & Vernetzt)

Bäume — Hierarchie mit Regeln

Baum (Tree)

Analogie:

Definition:

Beispiel: Der DOM-Baum

Irrtum: Bäume und Graphen sind völlig verschieden

Binäre Suchbäume — Geordnet für Geschwindigkeit

Binärer Suchbaum (BST)

Analogie:

Definition:

BST-Suche: Schritt für Schritt

Balance entscheidet

Balanciert vs. Degeneriert

Irrtum: BST-Suche ist immer O(log n)

Deep Dive: Selbstbalancierende Bäume

Interaktiv: BST-Suche Schritt für Schritt

Graphen — Das allgemeine Netzwerk

Graph

Analogie:

Definition:

Graphen in der echten Welt

Irrtum: Bei gerichteten Graphen kann man immer in beide Richtungen

Deep Dive: Wie speichert man Graphen?

Das Wichtigste

Quiz: Hierarchische Datenstrukturen

Was unterscheidet einen Baum von einem allgemeinen Graphen?

Checkpoint: Verstehst du hierarchische Datenstrukturen?

Bäume — Hierarchie mit Regeln

Baum (Tree)

Analogie:

Definition:

Beispiel: Der DOM-Baum

Irrtum: Bäume und Graphen sind völlig verschieden

Binäre Suchbäume — Geordnet für Geschwindigkeit

Binärer Suchbaum (BST)

Analogie:

Definition:

BST-Suche: Schritt für Schritt

Balance entscheidet

Balanciert vs. Degeneriert

Irrtum: BST-Suche ist immer O(log n)

Deep Dive: Selbstbalancierende Bäume

Interaktiv: BST-Suche Schritt für Schritt

Graphen — Das allgemeine Netzwerk

Graph

Analogie:

Definition:

Graphen in der echten Welt

Irrtum: Bei gerichteten Graphen kann man immer in beide Richtungen

Deep Dive: Wie speichert man Graphen?

Das Wichtigste

Quiz: Hierarchische Datenstrukturen

Was unterscheidet einen Baum von einem allgemeinen Graphen?

Checkpoint: Verstehst du hierarchische Datenstrukturen?

Verwandte Inhalte

Artikel

Datenstrukturen I (Linear)

Datenstrukturen III (Schlüsselbasiert)

Was ist ein Algorithmus?

Algorithmische Komplexität

Suche im Graphen — Die Anfänge

Heuristiken & Pfadsuche: Von Dijkstra zu A*

MinMax & Pruning

Rekursion

Demo

MinMax (Spieltheorie)

Pathfinding (Graphsuche)

Glossar

Timeline