Wann Bäume statt Listen

Listen sind linear; Bäume verzweigen. Hierarchien, bereichsbezogene Suche und logarithmische Höhe sprechen für Bäume. Sequenzielle Scans und Enden-Operationen sprechen für Listen oder Deques.

Strukturzeichnung, Traversierungsreihenfolge und Höhenargument kurz erklären können.

Wo gebraucht

Logarithmische Suche und sortierte Iteration schlagen lineare Listen, sobald n wächst und Ordnung oder Bereichsanfragen zählen. Flat Lists bleiben richtig für kleine n und reine Append-Workloads.

Vertiefung

Listen modellieren eine lineare Reihenfolge und sind stark bei sequenziellem Durchlauf sowie lokalen Änderungen. Bäume modellieren Hierarchie oder schaffen durch Ordnung kürzere Suchpfade. Die Struktur sollte aus den dominierenden Operationen folgen.

Ein ungeordneter Baum verbessert die Schlüsselsuche nicht automatisch. Erst zusätzliche Invarianten wie Suchordnung und Balance liefern verlässliche logarithmische Pfadlängen. Dafür werden Einfügen und Löschen komplexer.

Hierarchische Daten wie Dateisysteme oder Syntaxbäume besitzen bereits eine natürliche Eltern-Kind-Struktur. Eine lineare Speicherung ist möglich, würde aber Beziehungen über zusätzliche Indizes rekonstruieren müssen.

Schwierigkeitsstufen

1. Lineare und hierarchische Beziehungen unterscheiden.
2. Operationsprofile für eine Strukturwahl bewerten.
3. Kosten zusätzlicher Ordnungs- und Balanceinvarianten erklären.

Fallstricke

Die blosse Verwendung von Knoten macht Suche nicht schnell. Bei häufigem vollständigem Durchlauf kann eine kompakte lineare Struktur trotz schlechterer asymptotischer Suche günstiger sein.