Implementierung eines binären Suchbaumes

Für die Realisierung mit Hilfe einer Programmierumgebung stellen wir uns einen solchen binären Suchbaum als eine besondere Datenbank mit dem Namen BAUM vor. Wir wollen in unserer Datenbank Namen mit den zugehörigen Telefonnummern speichern. Jeder Datensatz hat also mindestens zwei Datenfelder. Der Inhalt des einen ist der Name, der des anderen die Telefonnummer.

Das Besondere an der Datenbank BAUM ist, dass jeder Datensatz zwei zusätzliche Datenfelder enthält. Die beiden ersten Datenfelder dienen ausschließlich zur Organisation des effektiven Suchalgorithmus. Sie enthalten die Verweise nach Links oder Rechts aus unserem Suchbaum. Jeder Datensatz hat dann die folgende Form:

 

Datenfeld 1	Datenfeld 2	Datenfeld 3	Datenfeld 4
Links	Rechts	Name	Telefonnummer

Aufbau eines Datensatzes in der Datenbank BAUM

 

Verwirklichen wir die ersten drei Ebenen unseres Suchbaumes in einer solchen Datenbank, dann müssen wir die Knoten bestimmten Datensätzen zuordnen und dürfen die Verweise und die Telefonnummer nicht vergessen. Die folgende Abbildung zeigt den Suchbaum mit den zusätzlichen Informationen.

 

Verweise mit dem Wert 0 (null) geben an, dass kein weiterer Ast folgt.

Wenn eine Datenbank wie ein Baum strukturiert ist, dann verwendet man in der Informationstheorie folgende Begriffspaare:

Datenbank	Baum
Datensatz	Knoten
erster Datensatz	Wurzel

 

Jetzt können wir diese Datenbank in der uns von Datenbanken her bekannten Listenform darstellen:

 

Satznummer	Links	Rechts	Name	Telefonnummer
1	2	3	Not	123456
2	5	6	Hut	112233
3	4	7	Sog	654321
4	0	0	Pol	456456
5	0	0	Erz	223344
6	0	0	Kur	332211
7	0	0	Wut	321321
8

Binärer Suchbaum als Datenbank in Listenform