Wähle einen vorhandenen Schlüssel und beobachte, wie sein
Inorder-Vorgänger oder
Inorder-Nachfolger gefunden wird.
Die zwei Suchverfahren stehen rechts getrennt im Pseudocode.
Binärer Suchbaum
Gelb markiert den gewählten Knoten, Lila den gerade
betrachteten Knoten und Grün das Ergebnis.
Die Baumansicht kann horizontal gescrollt werden.
ms
gewählter Knoten
gerade betrachtet
Vorgänger / Nachfolger
anderer Knoten
Vorgänger: der größte Schlüssel, der kleiner
als der gewählte Schlüssel ist. Nachfolger: der kleinste Schlüssel, der größer
als der gewählte Schlüssel ist.
Falls ein linker beziehungsweise rechter Teilbaum vorhanden ist,
findet man das Ergebnis dort. Andernfalls steigt man über
Elternknoten auf. Die Laufzeit beträgt
O(h) bei Baumhöhe h.