Baeume & Graphen

Arrays und Linked Lists sind linear - eine Zeile von Elementen. Baeume und Graphen sind hierarchisch bzw. vernetzt - und damit ideal fuer viele echte Probleme: Dateisysteme, Stammbaeume, Abhaengigkeiten, soziale Netzwerke, Navigation.

Baum-Grundbegriffe

Ein Baum ist ein Graph ohne Zyklen, mit einer eindeutigen Wurzel:

           Root
          /    \
       A          B
      / \          \
    C     D         E

Wurzel (Root): oberster Knoten
Blatt (Leaf): Knoten ohne Kinder
Tiefe (Depth): Abstand zur Wurzel
Hoehe (Height): laengster Weg von einem Knoten zu einem Blatt

Binary Tree

Jeder Knoten hat maximal zwei Kinder - links und rechts.

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# Baum aufbauen
root = Node(1,
    Node(2, Node(4), Node(5)),
    Node(3, None, Node(6))
)

Traversierung

Drei klassische Weisen, einen Baum zu durchlaufen.

In-Order (links, selbst, rechts)

def inorder(node):
    if node is None: return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

Fuer einen Binary Search Tree liefert das die Elemente sortiert.

Pre-Order (selbst, links, rechts)

def preorder(node):
    if node is None: return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

Post-Order (links, rechts, selbst)

def postorder(node):
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

Nuetzlich beim Zerstoeren eines Baums (Blaetter zuerst freigeben).

Level-Order (BFS)

Level fuer Level mit einer Queue:

from collections import deque

def level_order(root):
    if root is None: return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

Binary Search Tree (BST)

Ein Binary Tree mit der Ordnung: links < Wurzel < rechts.

         5
        / \
       3     8
      / \    / \
     1   4  7   9

Suchen - O(log n) im balancierten Fall

def bst_search(node, target):
    if node is None:
        return None
    if node.value == target:
        return node
    if target < node.value:
        return bst_search(node.left, target)
    return bst_search(node.right, target)

Bei jedem Schritt halbieren wir den Suchraum - wie binaere Suche, aber auf einem Baum.

Einfuegen

def bst_insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = bst_insert(node.left, value)
    else:
        node.right = bst_insert(node.right, value)
    return node

Das Problem: Unbalanciert

Wenn du sortierte Daten einfuegst, entsteht eine entartete Liste:

Suchen wird O(n) - katastrophal.

Loesung: Selbstbalancierende Baeume

In Produktion nutzt man Red-Black Trees oder AVL-Trees - die balancieren sich automatisch. Python’s SortedList und C++‘s std::set nutzen das.

Heap / Priority Queue

Ein Heap ist ein Binary Tree, in dem jeder Knoten kleiner (Min-Heap) oder groesser (Max-Heap) als seine Kinder ist.

Python-Implementation

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

heapq.heappop(heap)    # 1 - immer kleinstes zuerst
heapq.heappop(heap)    # 3
heapq.heappop(heap)    # 5

Operationen: O(log n) fuer push/pop, O(1) fuer peek.

Wann nutzen?

Top-K-Elemente finden: heapq.nlargest(10, liste)
Priority Queues: Task-Scheduling
Dijkstra-Algorithmus (kuerzester Pfad)

Trie - der Wort-Baum

Fuer Prefix-Suche, Autocomplete:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.ist_wort_ende = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, wort):
        node = self.root
        for c in wort:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.ist_wort_ende = True

    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

t = Trie()
t.insert("apfel")
t.insert("april")
t.insert("berlin")

print(t.startsWith("ap"))  # True
print(t.startsWith("xy"))  # False

Tries sind die Basis von Autocomplete-Systemen und Spell-Checkern.

Graphen

Ein Graph ist eine Menge von Knoten (Vertices) mit Kanten (Edges):

A --- B
|     |
C --- D

Ungerichtet: Kante in beide Richtungen
Gerichtet: Pfeile (A → B)
Gewichtet: Kanten haben Kosten (z.B. Entfernung)
Zyklisch / azyklisch: gibt es Zyklen?

Adjazenzliste

Die haeufigste Darstellung:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

Ein Dict von Knoten zu Listen seiner Nachbarn. Platz: O(V + E).

Adjazenzmatrix

2D-Array - matrix[i][j] = 1, wenn Kante:

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]

Platz: O(V²). Nur bei sehr dichten Graphen sinnvoll.

BFS - Breadth-First Search

Level fuer Level erkunden - ideal fuer kuerzeste Wege in ungewichteten Graphen.

from collections import deque

def bfs(graph, start):
    besucht = {start}
    queue = deque([start])

    while queue:
        knoten = queue.popleft()
        print(knoten)

        for nachbar in graph[knoten]:
            if nachbar not in besucht:
                besucht.add(nachbar)
                queue.append(nachbar)

bfs(graph, "A")
# A, B, C, D (oder aehnlich, je nach Reihenfolge)

Komplexitaet: O(V + E).

DFS - Depth-First Search

Tief in einen Zweig rein, dann zurueck - ideal fuer Pfadsuche, Zyklen-Erkennung.

def dfs(graph, start, besucht=None):
    if besucht is None:
        besucht = set()
    besucht.add(start)
    print(start)

    for nachbar in graph[start]:
        if nachbar not in besucht:
            dfs(graph, nachbar, besucht)

dfs(graph, "A")

Rekursive Version ist elegant, kann aber Stack-Overflow bei sehr tiefen Graphen haben. Iterative Version mit Stack:

def dfs_iter(graph, start):
    besucht = set()
    stack = [start]

    while stack:
        knoten = stack.pop()
        if knoten in besucht:
            continue
        besucht.add(knoten)
        print(knoten)
        stack.extend(graph[knoten])

Kuerzester Weg: Dijkstra

Fuer gewichtete Graphen - klassischer Algorithmus:

import heapq

def dijkstra(graph, start):
    # graph[knoten] = [(nachbar, kosten), ...]
    distanzen = {knoten: float("inf") for knoten in graph}
    distanzen[start] = 0
    pq = [(0, start)]

    while pq:
        dist, knoten = heapq.heappop(pq)

        if dist > distanzen[knoten]:
            continue

        for nachbar, kosten in graph[knoten]:
            neue_dist = dist + kosten
            if neue_dist < distanzen[nachbar]:
                distanzen[nachbar] = neue_dist
                heapq.heappush(pq, (neue_dist, nachbar))

    return distanzen

graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("A", 1), ("C", 2), ("D", 5)],
    "C": [("A", 4), ("B", 2), ("D", 1)],
    "D": [("B", 5), ("C", 1)],
}

print(dijkstra(graph, "A"))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Komplexitaet: O((V + E) log V) mit Heap.

Topologische Sortierung

Fuer gerichtete azyklische Graphen (DAGs) - z.B. Task-Abhaengigkeiten:

def topological_sort(graph):
    in_degree = {k: 0 for k in graph}
    for neighbors in graph.values():
        for n in neighbors:
            in_degree[n] += 1

    queue = deque([k for k, v in in_degree.items() if v == 0])
    result = []

    while queue:
        k = queue.popleft()
        result.append(k)
        for n in graph[k]:
            in_degree[n] -= 1
            if in_degree[n] == 0:
                queue.append(n)

    return result

Beispiel: Build-Reihenfolge, Kurs-Voraussetzungen, Makefile-Dependencies.

Zyklen erkennen

Wichtig fuer Dependency-Systeme - Zyklen sind oft Fehler.

def hat_zyklus(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    farbe = {k: WHITE for k in graph}

    def dfs(k):
        farbe[k] = GRAY
        for n in graph[k]:
            if farbe[n] == GRAY:
                return True    # Back-Edge
            if farbe[n] == WHITE and dfs(n):
                return True
        farbe[k] = BLACK
        return False

    for k in graph:
        if farbe[k] == WHITE:
            if dfs(k):
                return True
    return False

Praktisches Beispiel

Problem: Finde den kuerzesten Weg durch ein Labyrinth (als Grid).

from collections import deque

def kuerzester_weg(grid, start, ziel):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, 0)])
    besucht = {start}

    richtungen = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        (r, c), schritte = queue.popleft()
        if (r, c) == ziel:
            return schritte

        for dr, dc in richtungen:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                and grid[nr][nc] == 0
                and (nr, nc) not in besucht):
                besucht.add((nr, nc))
                queue.append(((nr, nc), schritte + 1))

    return -1

labyrinth = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]
print(kuerzester_weg(labyrinth, (0,0), (3,3)))  # 6

Grid als Graph interpretiert, BFS findet den kuerzesten Pfad.

Zusammenfassung

Binary Tree: maximal 2 Kinder, 4 Traversierungen (In/Pre/Post/Level)
BST: sortiert, O(log n) Suche (balanciert)
Heap: Priority Queue, heapq in Python
Trie: Prefix-Suche
Graphen: als Adjazenzliste (Dict), besser als Matrix
BFS: Queue, kuerzester Weg in ungewichteten Graphen
DFS: Stack/Rekursion, Pfadsuche, Zyklen
Dijkstra: kuerzester Weg in gewichteten Graphen

Im naechsten Kapitel: Sortier-Algorithmen - der Klassiker der Algorithmik.