19.7 Implementierung eines binären Suchbaums mit Hilfe von Arrays

In der Literatur und auch im Internet gibt es keinen Konsens darüber, ob der binäre Suchbaum nun eine Datenstruktur oder ein abstrakter Datentyp ist. Die Wikipedia vom 24.11.07 hilft uns auch nicht viel weiter:

Unter einer Datenstruktur versteht man normalerweise die physikalische Realisierung von Daten im Arbeitsspeicher oder auf der Festplatte des Rechners. So bestehen int-Zahlen in vielen Programmiersprachen zum Beispiel aus acht aufeinander folgenden Bits, während Strings häufig aus 256 aufeinander folgenden Bits zusammengesetzt sind. Neben den einfachen Datenstrukturen wie int, double, float, boolean und so weiter gibt es auch zusammengesetzte Datenstrukturen. Die bekannteste ist wohl der Array, der aus lauter gleichen, im Arbeitsspeicher aufeinander folgenden einfachen oder zusammengesetzten Datenstrukturen besteht, wobei jedes Arrayelement einen fortlaufenden Index besitzt, angefangen bei Null. So gesehen, könnte man auch eine Datenstruktur Binärbaum definieren, die aus Knoten zusammengesetzt ist, die aus je drei Komponenten bestehen, nämlich der Adresse der eigentlichen Daten, der Adresse des linken Nachfolgers, und der Adresse des rechten Nachfolgers. Ergänzt man diese Definition um ein Sortierkriterium, ist man bei der Datenstruktur „binärer Suchbaum“ angelangt.

Ein abstrakter Datentyp sagt umgekehrt überhaupt nichts aus über eine mögliche physikalische Struktur; er wird nur durch seine Operationen definiert. Beim ADT Stack ist zum Beispiel nur bekannt, dass er eine push()- und eine pop()-Operation besitzt, außerdem eine empty()-Operation. Durch bestimmte Axiome wird dann die Arbeitsweise der Operationen genau definiert. So gilt für den ADT Stack beispielsweise das Axiom

pop(push(x,s)) = s

welches Folgendes besagt: Wenn man auf einen Stack, der sich gerade im Zustand s befindet, das Element x pusht und anschließend die pop-Operation ausführt, so befindet sich der Stack wieder im Zustand s. Durch dieses Axiom wird festgelegt, dass mit pop das zuletzt gepushte Element entfernt wird.

Was ist nun ein binärer Suchbaum? Eine Datenstruktur oder ein abstrakter Datentyp? Für letzteres spricht, dass man einen Binärbaum auch ohne Zeiger implementieren kann, zum Beispiel mit Hilfe eines Arrays. Den ADT „binärer Suchbaum“ kann man auf unterschiedliche Weise implementieren, also mit Zeigern, mit Arrays oder vielleicht auch anders.

Andererseits ist der mit Hilfe von Zeigern oder Arrays implementierte „binäre Suchbaum“ auch eine physikalische Datenstruktur. Man kann eine solche Datenstruktur nämlich verwenden, um beispielsweise den ADT „Dictionary„ zu implementieren.

Wir kommen mit unserer Frage, ob der „binäre Suchbaum“ eine physikalische Datenstruktur oder ein abstrakter Datentyp ist, also nicht viel weiter. Übrigens wäre diese Problematik ein schönes Thema, über das man sich im mündlichen Abitur auslassen könnte.

Dessen ungeachtet, wollen wir hier im Abituriententeil einen binären Suchbaum mal mit Hilfe von Arrays implementieren. Einfach so, aus Spaß, damit die Experten noch ein paar Punkte bekommen und damit die Abiturienten auf "gemeine" schriftliche Aufgaben vorbereitet werden.

Implementierung mit Hilfe eines Arrays

Zunächst legen wir uns einen Array mit möglichst vielen Elementen an - für unsere Zwecke reichen 100 Elemente wohl aus. Nun wollen wir Zahlen in diesen Array einfügen, und es dabei nach außen so aussehen lassen, als ob wir die Zahlen in einen binären Suchbaum einfügen. Die erste Zahl schreiben wir in das Array-Element mit dem Index 0. Dieses Array-Element steht für die Wurzel des binären Suchbaums. Wo steht nun der linke Nachfolger der Wurzel? Ganz einfach, im Element mit dem Index 1. Der rechte Nachfolger steht im Element mit dem Index 2.

Bisher ist das alles noch kein Problem, aber jetzt wollen wir weitere Elemente in unseren „binären Suchbaum“ einfügen. Wo kommt der linke Nachfolger des linken Nachfolgeres der Wurzel hin, die Elemente 0 bis 2 sind ja schon belegt. Wie wäre es mit Element 3? Und der rechte Nachfolger des linken Nachfolgers der Wurzel wird in Element 4 gespeichert, und so weiter. Am besten, sehen wir uns dazu mal wieder ein Bild an.

Den Rest dieses Abschnitts können Sie in meiner Buchversion nachlesen.

1. Binärbäume - Allgemeines
2. Binäre Suchbäume
3. Das Einfügen von Elementen
4. Das Anzeigen von Elementen
5. Das rekursive Einfügen von Elementen
6. Das Löschen von Elementen
7. Implementierung mit Hilfe von Arrays
8. AVL-Bäume
9. B-Bäume

Abiturienten NRW

und weiter mit 19.8 - AVL-Bäume

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 30. März 2010