Binary Search Tree (BST)

Datenbanken nutzen Bäume (B-Trees, Index), um Daten schnell zu finden. Dateisysteme nutzen Bäume. Der Vorteil gegenüber Hash Maps: Ein Baum ist sortiert. Du kannst fragen: "Gib mir alle User zwischen ID 50 und 100". Das geht im Baum extrem effizient. In einer Hash Map müsstest du alles durchsuchen.

1. Degenerierung (Die Linie)

Das Problem: Wenn du die Zahlen 1, 2, 3, 4, 5 nacheinander einfügst... Die 2 kommt rechts von der 1. Die 3 rechts von der 2. Der Baum wird zur Linie (Linked List). Die Suche dauert dann O(n) (langsam) statt O(log n) (schnell). Ein Baum muss "balanciert" sein (dick und flach, nicht dünn und hoch).

2. Traversierung(en)

Wie läuft man durch den Baum?

• In-Order: Links, Ich, Rechts. (Ergibt die sortierte Liste: 1, 2, 3...).
• Pre-Order: Ich, Links, Rechts. (Gut zum Kopieren des Baums).
• Post-Order: Links, Rechts, Ich. (Gut zum Löschen des Baums).

1. Threaded Binary Trees

Bei einer traditionellen Traversierung (wie "In-Order") verwendet man meist einen Stack oder Rekursion. Beides schlingt $O(\log n)$ bzw. bei völlig schiefen Bäumen $O(n)$ Memory-Ausschläge. Eine Variante in der Systemprogrammierung sind Threaded Binary Trees. In klassischen Blättern ("Leaves") zeigen die linken und rechten Pointer ins pure Nichts (null/nil). Im Threaded-Baum zweckentfremdet man diese Verschwendung: Man nutzt sie als "Faden" (Thread), der back-links auf den unmittelbaren In-Order Nachfolger oder Vorgänger verweist. Vorteil: Du kannst ganz ohne Rekursion, reinen Iterations-Loops und exakt mit $O(1)$ Extra-RAM durch den Tree laufen.

2. Splay Trees und Temporal Locality

Oft sucht ein System auf einer Suchstruktur immer dieselben Elemente. Wenn User A einliest, fordert er ein Profil an, was in den nächsten fünf Sekunden nochmal verlangt wird. Ein Splay-Tree verzichtet auf das harte Ausbalancierungsmaß des AVL-Baums. Er integriert ein selbstlernendes Prinzip: Finde ich einen Knoten, mache eine Reihe harter Rotations-Operationen (das Splaying) und hieve genau diesen Knoten gnadenlos zur Tree-Wurzel. Diese Temporale Lokalität führt in Systemen – wie Caches oder Netzwerk-Routing-Tabellen – zur Reduzierung der effektiven, amortisierten Suchzeit, da extrem heiße Daten immer im Level-$0$ und Level-$1$ verweilen.

3. Succinct Trees und Speicheroptimierung (Bit-Manipulation)

Möchte man einen riesigen Graph oder Dokumenten-Baum in speicherbegrenzten Controllern laden, verliert man enorme Datenmengen an Pointer. In der Kompressionstheorie gibt es den Succinct Tree representations Level: Mithilfe der "Parenthesis Representation" kodiert man jeden Baum in rohe Folgen von Klammern (( ) ( ( ) ) ) und speichert diese schlicht als Bits: 1s als (, 0s als ). Man benötigt dann exakt $2n$ harte Bits und rank/select Dictionary Algorithmen in C, um in theoretischer $O(1)$ Latenz Kinder, Root oder Leaf zu finden, ohne einen einzigen Adresspointer auf den Heap zu schütten.