Zur Themenübersicht
Ein binärer Suchbaum ist ein Baum, dessen Knoten einen maximalen Outdegree von 2 besitzen. Zusätzlich sind alle Knoten so angeordnet, dass jene Knoten, welche einen Inhalt besitzen, der kleiner ist als der eines anderen Knotens, sich auf einer Seite jeden Knotens befinden und alle die, welche einen größeren Inhalt besitzen, auf der anderen Seite jeden Knotens angelagert sind. Mit Ausnahme der Wurzel, welche einen Indegree von 0 besitzt, weisen alle anderen Knoten einen Indegree von 1 auf.
Dieses klingt zunächst recht verwirrend, ist jedoch anhand eines Beispiels gut zu verstehen.
In einen leeren binären Suchbaum wird ein Knoten mit dem Inhalt M eingefügt. |
 |
Ein weiterer Knoten mit dem Inhalt F wird eingefügt. Da F kleiner ist als M, wird der neue Knoten links von der Wurzel angelagert. |
 |
Ein weiterer Knoten mit dem Inhalt S wird eingefügt. Da S größer ist als M, wird der neue Knoten rechts von der Wurzel angelagert. |
 |
Ein weiterer Knoten mit dem Inhalt I wird eingefügt. Da I kleiner ist als M, muß der neue Knoten links von der Wurzel angelagert werden. I ist jedoch größer als F, woraus folgt, daß der neue Knoten rechts an dem Blatt F angelagert wird. |
 |
Ein weiterer Knoten mit dem Inhalt K wird eingefügt. Da K kleiner ist als M, muß der neue Knoten links von der Wurzel angelagert werden. K ist jedoch größer als F, woraus folgt, daß der neue Knoten rechts vom Knoten F angelagert werden muß. K ist ebenfalls größer als I, sodaß der neue Knoten rechts an dem Blatt I angelagert wird. |
 |
Ein weiterer Knoten mit dem Inhalt J wird eingefügt. Da J kleiner ist als M, muß der neue Knoten links von der Wurzel angelagert werden. J ist jedoch größer als F, woraus folgt, daß der neue Knoten rechts vom Knoten F angelagert werden muß. J ist ebenfalls größer als I, sodaß der neue Knoten sich rechts vom Knoten I befinden muß. Da J kleiner ist als K, wird der Knoten links von dem Blatt K angelagert. |
 |
Ein weiterer Knoten mit dem Inhalt H wird eingefügt. Da H kleiner ist als M, muß der neue Knoten links von der Wurzel angelagert werden. H ist jedoch größer als F, woraus folgt, daß der neue Knoten rechts vom Knoten F angelagert werden muß. H ist kleiner als I, sodaß der neue Knoten links von dem Knoten I angelagert wird. |
 |
| Zur
Themenübersicht |
|
Zum Seitenanfang |
|
Zur vorigen Seite |
Zur nächsten Seite  |
| © 2001 LK 12 If , Moritz Möhrke und G. Kubitz | Hannah-Arendt-Gymnasium, Lengerich |