Trees (Bäume)

Hierarchische Struktur. Jeder Knoten hat Kinder, aber genau einen Eltern (außer Wurzel).

Anwendungen

• Dateisystem (Verzeichnis-Hierarchie)
• HTML/XML/JSON-Strukturen (DOM)
• Datenbank-Indizes (B-Tree)
• Routing-Tabellen

Binary Search Tree (BST)

Linkes Kind < Knoten < rechtes Kind. Balanciert: O(log n) Suche.

        7
      /   \
     3     11
    / \   /  \
   1   5 9    13

Unbalanciert (z.B. sortiert eingefügt) → degeneriert zu Linked List → O(n).

Selbstbalancierende Trees

• AVL Tree — strenge Balance, schnell für Lookup
• Red-Black Tree — weniger streng, schneller fürs Einfügen. In Java TreeMap, C++ std::map.
• B-Tree / B+Tree — viele Kinder pro Knoten, optimal für DB-Indizes

Trie (Präfix-Baum)

Spezial-Tree für Strings. Jeder Pfad von Wurzel = ein Präfix.

• Autovervollständigung ("Tippst du 'ber'? Vorschläge: berlin, berater, berge")
• Wörterbücher
• IP-Routing

Heap (binärer Heap)

Tree-Struktur, aber als Array implementiert. Min-Heap: jeder Eltern ≤ Kinder.

Basis für Priority Queues.

Tree-Traversierung

• DFS — Pre-Order: Knoten → links → rechts
• DFS — In-Order: links → Knoten → rechts (sortiert bei BST)
• DFS — Post-Order: links → rechts → Knoten
• BFS — Level-Order: Wurzel → Ebene 1 → Ebene 2 → ...