Abbildung 3 zeigt einen regulaeren binaeren Baum mit 7 internen Knoten und 8 externen Knoten.
Gegeben seien n unterschiedene Indize oder Schluessel
einer total geordneten Menge von Indize.
Definition 2.11: Ein binaerer Suchbaum fuer n Schluessel ist ein binaerer, indizierter Baum T mit n internen Knoten, dessen n interne Knoten mit den n Schluesseln indiziert sind, so dass sie die binaere Suchbedingung erfuellen: Fuer alle internen Knoten u in T ist der Wert eines jeden Schluessels in dem linken Unterbaum von u kleiner als der Schluesselwert von u, und der Wert des Schluessels von u ist kleiner als der Wert eines jeden Schluessels in dem rechten Unterbaum von u. [Cormen]
Bild 4 zeigt einen binaeren Suchbaum fuer natuerlichen Zahlen zwischen 1 und 16.
Um in einem binaeren Suchbaum ein Element zu finden, benutzt man den Algorithmus der binaeren Suche, den wir im Kapitel 3 beschreiben werden.
