Zurück zum Lernbereich

Datenstrukturen II (Hierarchisch & Vernetzt)

Bäume, Suchbäume und Graphen — Datenstrukturen mit Familienverhältnissen.

  • Grundlagen
  • 15 min
  • Fortgeschritten

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Bäume und Graphen verstehen

Was ist ein Baum?

Ein Baum ist wie ein Ordner-System. Oben ist die Wurzel. Unten sind die Blätter. Zwischen ihnen gibt es Äste. Jeder Punkt hat genau einen Oberpunkt.

Binäre Suchbäume

Ein Suchbaum ist ein Baum mit Ordnung. Binär heißt: jeder Punkt hat links und rechts. Links stehen kleinere Zahlen. Rechts stehen größere Zahlen. So findet man Zahlen sehr schnell.

Graphen überall

Ein Graph ist ein Netzwerk. Er hat Punkte und Verbindungen. Ein Straßennetz ist ein Graph. Das Internet ist ein Graph. Auch soziale Netzwerke sind Graphen.

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

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.

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 = 4

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

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.

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

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.

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. 1. Suche 40: Vergleiche mit Wurzel 50 → 40 < 50, gehe links
  2. 2. Vergleiche mit 30 → 40 > 30, gehe rechts
  3. 3. Vergleiche mit 40 → gefunden! Nur 3 Vergleiche
  4. 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

Balancierter BST — O(log n) Einfügen von [50, 30, 70, 20, 40, 60, 80]: Höhe = 2, also 3 Ebenen (log₂(7 + 1) = 3). 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: 5 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.

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.

50 30 70 20 40 60 80
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
Steuerung
Schritte

Graphen — Das allgemeine Netzwerk

Definition

Graph

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.

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.

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: Follow auf X (früher Twitter) — 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.

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

  1. 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.
  2. 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.
  3. 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

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

Prüfen

Checkpoint: Verstehst du hierarchische Datenstrukturen?

Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.

0 von 3 sitzen