PPT-Folie
Binäre Suchbäume (natürliche Binärbäume)
Für jeden Knoten k eines binären Suchbaums B gilt: Die Schlüssel im linken Teilbaum von k sind sämtlich kleiner als der Schlüssel S(k) von k, und dieser wiederum ist kleiner als sämtliche Schlüssel im rechten Teilbaum von k,
d.h. falls die Teilbäume nicht nur aus einem Blatt bestehen gilt
(1) S(k) < S(w) für alle inneren Knoten w im linken Teilbaum von B,
(2) S(k) >=S(w) für alle inneren Knoten w im rechten Teilbaum von B.
Ein binärer Suchbaum B =<K,w,S> für eine linear geordnete Menge M ist ein geordneter, binärer Baum B =<K,w> mit einer Abbildung S: K->M von der Knotenmenge K in die Schlüsselmenge M, die die Suchbaumbedingung erfüllt.