Rekursive Baumsuche

Suche in einem Binärbaum: vergleiche den Schlüssel mit dem aktuellen Knoten und steige links oder rechts ab. Ohne Suchbauminvariante bleibt nur vollständige Traversierung.

Aufgabe: zähle die Knoten eines Binärbaums rekursiv.

$$x \lt k \Rightarrow \mathrm{left}$$

Wo gebraucht

BST-Lookup ist das Modell hinter TreeMap und vielen Indexen. Dieselbe Idee skaliert zu B-Bäumen auf Platte und zu Raumpartitionsbäumen (k-d, Quadtree) in Spielen und GIS.

Vertiefung

Eine allgemeine Baumsuche prüft den aktuellen Knoten und durchsucht nötigenfalls beide Teilbäume. In einem Suchbaum erlaubt die Ordnungsinvariante dagegen, anhand eines Vergleichs genau einen Teilbaum auszuschliessen.

Die Laufzeit ist proportional zur besuchten Struktur. Bei guter Form entspricht die Suchpfadlänge der Höhe; bei einseitiger Form kann fast jeder Knoten geprüft werden. Balance ist daher eine Laufzeiteigenschaft der Form, nicht der rekursiven Syntax.

Für Objektschlüssel muss die Vergleichsrelation konsistent sein. Ein Vergleichswert von null legt fest, wann die Suche einen Treffer betrachtet, und beeinflusst damit die Behandlung fachlich gleicher Schlüssel.

Schwierigkeitsstufen

1. Allgemeine und geordnete Suche unterscheiden.
2. Einen Suchpfad anhand von Vergleichen verfolgen.
3. Formabhängige Worst-Case-Kosten erklären.

Fallstricke

Ohne nachgewiesene Ordnungsinvariante darf kein Teilbaum ausgelassen werden. Auch eine falsche Behandlung des Vergleichsvorzeichens kann vorhandene Schlüssel unsichtbar machen.