Als Blattsuchbaum wird in der Informatik die Erweiterung des geordneten binären Baums, in dem die Schlüssel in Blättern und nicht mehr in den inneren Knoten abgelegt werden, bezeichnet. Die inneren Knoten fungieren hier lediglich als Wegweiser und nicht mehr als eigentliche Schlüsselträger.
Struktur
Der Blattsuchbaum ist ähnlich aufgebaut, wie der geordnete binäre Baum, mit dem Unterschied, dass hier alle Schlüssel in Blätter abgelegt aber nach bekannten Regeln an das Ende des Suchbaums einsortiert werden. Da in diesem Baum folglich auch die Möglichkeit besteht mehrere innerer Knoten mit gleichen Schlüsseln einzufügen, muss die bisherige Einsortierregelung für diesen Fall, erweitert werden:
- jeder Knoten, dessen Schlüssel kleiner oder gleich seines Vater ist, wird links einsortiert
- jeder Knoten, dessen Schlüssel größer als der seines Vater ist, wird in den rechten Teilbaum einsortiert.
Suchalgorithmus
Es gibt zwei Fälle, die beim Suchen in einem Blattsuchbaum nun unterschieden werden müssen:
1. Fall: Betrachtetes Element ist kein Blatt
Hier ist es nicht relevant, ob der gesuchte Schlüssel gleich dem Knotenschlüssel, sondern nur, ob das Blatt mit dem gesuchten Schlüssel in dem linken oder in dem rechten Teilbaum zufinden ist. Um an diese Information zu gelangen, reicht es aus, zu fragen, ob der gesuchte Schlüssel kleiner oder gleich dem Knotenschlüssel ist, oder nicht.
2. Fall: Betrachtetes Element ist ein Blatt
Hier interessiert nur noch, ob der Blattschlüssel gleich dem gesuchten ist. Sollte dies nicht der Fall sein, so ist sicher, dass der gesuchte Schlüssel im gesamten Baum nicht vorhanden ist.
Folgender Pseudocode soll die Funktionsweise des Suchalgorithmus verdeutlichen:
X: Wurzel des Suchbaums S: gesuchter Schlüssel
Fall 1: Knoten ist kein Blatt 1 suche(x, s) 2 wenn x <= schlüssel[x] 3 dann suche(linke_Wurzel[x],s) 4 sonst suche(rechte_Wurzel[x],s)
Fall 2: Knoten ist ein Blatt 5 wenn s = Schlüssel[x] 6 dann ergebnis: x 7 sonst ergebnis: kein Schlüssel vorhanden