Suchbäume

Ein binärer Suchbaum ist ein Binärbaum, dessen Knoten p jeweils mit einem Schlüsselwert $key(p)$ versehen sind, so dass für alle inneren Knoten $p$ gilt:

• ist $w$ ein Knoten im linken Teilbaum von $p$, dann ist $key(w) < key(p)$
• ist $u$ ein Knoten im rechten Teilbaum von $p$, dann ist $key(u) > key(p)$

Ein Beispiel ist in Abbildung 1 dargestellt. Den Unterschied zu zu einem gewöhnlichen binären Baum zeigt Abbildung 2.

Abbildung 1: Ein binärer Suchbaum

Abbildung 2: Bei einem Suchbaum haben die linken Knoten einen kleineren Wert, als die rechten