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: 24.09.2014 16:41 (Externe Bearbeitung)
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki