binärer Suchbaum
Bedeutung
Ein markierter Binärbaum B ist ein natürlicher binärer Suchbaum (kurz: binärer Suchbaum), wenn die Suchbaum-Eigenschaft gilt, d.h. wenn für jeden Knoten K in B gilt:
Bemerkungen
„Natürlich“ bezieht sich auf das Entstehen der Bäume in Abhängigkeit von der Reihenfolge der Einfüge-Operationen (Abgrenzung zu balancierten Bäumen).
In einem binären Suchbaum gibt es zu einem Schlüssel maximal einen Knoten mit entsprechender Markierung.