Suchbäume
Binärer Suchbaum
Baum als Text
Idee
Ein binärer Suchbaum ordnet Schlüssel nach einer Regel: links unter einem Knoten nur kleinere, rechts nur größere. Suchen heißt dann: an jedem Knoten einmal vergleichen und in die passende Hälfte weitergehen, wie beim Zahlenraten mit „größer“ und „kleiner“.
v ← Wurzelsolange v nicht leer:wenn k = v.schlüssel: schon da, fertigwenn k < v.schlüssel: v ← v.linkssonst: v ← v.rechtsneuer Knoten mit k an den leeren Platz
Höhe und Aufwand
- Schlüssel
- 9
- jeder kommt nur einmal vor
- Höhe
- 4 Ebenen
- von der Wurzel bis zum tiefsten Knoten
- Kleinste mögliche Höhe
- 4 Ebenen
- auf 4 Ebenen passen höchstens 15 Schlüssel, auf 3 nur 7
- Höhe höchstens
- 9 Ebenen
- eine Kette, wenn die Schlüssel sortiert ankommen
- Suche höchstens
- 4 Vergleiche
- einer je Ebene auf dem Weg nach unten
- Ersatz beim Löschen
- Nachfolger
- der kleinste Schlüssel im rechten Teilbaum
Wie man darauf kommt
Suchen, Einfügen und Löschen gehen je einen Weg von der Wurzel nach unten: Die Arbeit wächst mit der Höhe h. Im besten Fall ist h etwa log₂ n, bei sortierter Eingabe aber n: Dann ist der Baum eine Kette und nicht schneller als eine Liste.
Die Regel gilt nicht nur für die Kinder, sondern für den ganzen Teilbaum. Liegt der gesuchte Schlüssel irgendwo im Baum, dann in dem Teilbaum, den der Vergleich auswählt; der andere kann ihn gar nicht enthalten. Der Weg endet beim Schlüssel oder an einem leeren Platz, und genau dort gehört ein neuer Schlüssel hin.