Benutzer-Werkzeuge

Webseiten-Werkzeuge


glossar:binaerer_suchbaum

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:

  • Alle Schlüssel im linken Unterbaum von K sind echt kleiner als der Schlüssel von K .
  • Alle Schlüssel im rechten Unterbaum von K sind echt größer als der Schlüssel von K .

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.
glossar/binaerer_suchbaum.txt · Zuletzt geändert: 2016/09/22 10:14 (Externe Bearbeitung)