Wörterbuchoperationen
Annahme (Suchbaumbedingung):
Für einen beliebigen Knoten k mit Schlüssel S(k) des Binärbaumes gilt: Alle im linken Teilbaum von k gespeicherten Schlüssel sind kleiner als S(k) und S(k) wiederum ist kleiner als alle Schlüssel im rechten
Die Suche nach einem Schlüssel x in einem Baum (Teilbaum) läuft nach folgendem rekursiven Schema ab:
Man inspiziere den Wurzelknoten des Baumes.
Falls x = Schlüssel des inspizierten Knotens: Suche beendet. Sonst:
Falls x < Schlüssel des inspizierten Knotens: Setze Suche im linken Teilbaum fort.
Falls x > Schlüssel des inspizierten Knotens: Setze Suche im rechten Teilbaum fort.
Die Suche endet erfolglos sobald auf diese Weise ein Blattknoten erreicht wird.
Maximale Anzahl inspizierter Knoten: Tiefe des Baumes.
Suche innerhalb der Knoten etwa durch lineares oder binäres Suchen zu realisieren. Da l? m, ist Aufwand dafür konstant.