Suchbäume

Definition:
Ein Suchbaum (Search Tree) ist eine gerichteter Baum mit (nicht notwendigerweise eindeutigen) Schlüsselwerten zu den Daten in den Knoten und der Sortierungsbedingung:
Schlüssel des linkes Kindes $\leq$ Knotenschlüssel $\leq$ Schlüssel des rechten Kindes
Ein Suchbaum stellt mindestens die Operationen Find, Insert und Delete zur Verfügung, häufig auch FindMin/FindMax und FindPred/FindSucc.

Definition:
Ein Wörterbuch (Dictionary) ist eine Datenstruktur mit den Operationen Find, Insert und Delete.

Definition:
Ein interner Suchbaum ist ein Suchbaum mit Datenwerten an den inneren Knoten. Verweise auf Blätter sind NULL-Zeiger.
Ein externer Suchbaum ist ein Suchbaum mit Datenwerten an den Blättern. Die inneren Knoten enthalten Verwaltungsinformationen.