# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/datenstrukturen/README.txt]

BAEUME (TREES)
==============

Stand: 2026-01-28

WAS IST EIN BAUM?
-----------------
Eine hierarchische Datenstruktur. Es gibt eine Wurzel (Root), von der Aeste zu Knoten (Nodes) fuehren. Knoten ohne Kinder heissen Blaetter (Leaves).
Ein Baum ist ein gerichteter Graph ohne Zyklen.

BINAERBAEUME (BINARY TREES)
---------------------------
Jeder Knoten hat maximal 2 Kinder: Links und Rechts.

### Binary Search Tree (BST)
Der Klassiker fuer durchsuchbare Daten.
- Regel: Alles im linken Teilbaum ist KLEINER als der Knoten. Alles im rechten Teilbaum ist GROESSER.
- **Suche:** O(log n) (wie binaere Suche, nur als Struktur).
- **Problem:** Wenn man sortierte Daten einfuegt (1,2,3,4...), entartet der Baum zur Liste (Suche wird O(n)).

BALANCIERTE BAEUME
------------------
Selbst-optimierende Baeume, die verhindern, dass sie schief ("degenerated") werden. Sie garantieren O(log n).
- **AVL-Baseume:** Streng balanciert.
- **Red-Black Trees:** Etwas lockerer, schneller beim Einfuegen. (Basis fuer viele System-Libraries z.B. in C++ map oder Java TreeMap).

HEAPS (HALDEN)
--------------
Ein spezieller binaerer Baum (fuer Priority Queues).
- **Min-Heap:** Der Vater ist immer kleiner als die Kinder. Wurzel ist Minimum.
- **Max-Heap:** Der Vater ist groesser. Wurzel ist Maximum.
- Nicht komplett sortiert, nur "vertikal geordnet".

WEITERE BAUMARTEN
-----------------
- **Tries (Praefixbaeume):** Fuer Texte. Jeder Knoten ist ein Buchstabe. Pfad = Wort. Super fuer Autocomplete.
- **B-Trees:** Baeume mit vielen Kindern. Optimiert fuer Festplatten/Datenbanken (minimiert Disk-Reads).

ANWENDUNGEN
-----------
- Dateisysteme (Ordnerstruktur).
- HTML DOM (Document Object Model).
- Datenbank-Indizes.
- Syntaxbaeume in Compilern (AST).

SIEHE AUCH
----------
wiki/informatik/datenstrukturen/graphen.txt
wiki/informatik/algorithmen/suche.txt
