Binärbäume sind wichtige Datenstrukturen, die in der Informatik sehr gebräuchlich sind. Außer in Übungen während des Studiums werden Binärbäume eher selten selbst programmiert, aber man sollte ungefähr wissen, um was es sich dabei handelt – wie bei allen Datenstrukturen und Algorithmen kann ein Verständnis der Binärbäume das Verständnis für die Informatik und die Softwareentwicklung verbessern. In diesem Artikel soll allgemein erklärt werden, was Bäume im Allgemeinen und Binärbäume im Speziellen sind und wozu man sie benötigt.
Was sind Bäume?
Zuerst soll die Frage geklärt werden, was überhaupt Bäume in der Informatik sind. Sehen wir uns erst einmal Bäume in der Realität an – die Gewächse, deren Wurzeln unten in der Erde stecken. Ein Baum beginnt bei der Wurzel, dann folgt ein Stamm. Von diesem Stamm zweigen große Äste ab, von diesen Ästen weitere Äste, die immer kleiner werden. Schließlich werden die Äste zu dünnen Zweigen und an diesen hängen Blätter. Und an den Blättern hängt nichts mehr; hier „endet“ der Baum.
Wieder einmal hat die Realität bei der Namensgebung in der Informatik Pate gestanden. Bäume in der Informatik sind genauso aufgebaut wie die oben beschriebenen Gewächse. Sie beginnen bei einer Wurzel. Von dieser Wurzel zweigen Äste ab, die sogenannten „Kanten“ (eng. „edge“). Die Stellen, an denen eine solche Abzweigung stattfindet, werden als „Knoten“ (eng. „node“) bezeichnet. An Knoten können immer mehr Kanten abzweigen, bis zu Knoten, die keine Nachfolger mehr haben. Das sind die sogenannten „Blätter“. Auf diese Art gibt es genau einen Weg zwischen zwei Knoten („Pfad“). Beachten Sie nur, dass die Wurzel von Informatik-Bäumen „oben“ stehen.
Wichtig ist, dass jeder Knoten genau einen Vorgänger hat, aber – je nach Art des Baums – mehrere Nachfolger haben kann aber nicht haben muss. Sie können jeden beliebigen Knoten als Wurzel eines Teilbaums innerhalb des Hauptbaums betrachten.
Sie haben bereits Bäume gesehen. So ist z.B. das Dateisystem von Windows in einer Baumstruktur angeordnet. Beginnend bei dem Arbeitsplatz als Wurzel und über die Festplatten und Laufwerke als erste Knoten geht es über die Verzeichnisse, welche Knoten darstellen, bis zu den Dateien, den Blättern. In Ordnern können weitere Ordner stecken, bei Dateien ist jedoch Schluss. Hier findet keine weitere Verzweigung statt. Sie können für jede Datei einen eindeutigen Pfad durch den Baum definieren.
Warum werden Bäume verwendet?
Am Beispiel des Dateisystems sehen Sie die Vorteile eines Baums. Durch eindeutige Pfade können Sie die gewünschte Datei schnell finden. Sie wissen sofort, wo Sie eine neue Datei oder einen neuen Ordner erstellen müssen. Sie müssen (theoretisch) nicht jede Datei durchsuchen, wenn Sie eine bestimmte Datei suchen, sondern können sofort dorthin navigieren (das setzt natürlich einen gut organisierten Dateibaum voraus).
Bäume sind also sehr effiziente Datenstrukturen, weil Sie schnell nach Daten suchen können. Schließlich müssen Sie nicht jedes Element betrachten. Somit können Sie auch schneller Daten einfügen und Daten löschen.
Was ist ein Binärbaum?
Es gibt verschiedene Arten von Bäumen. Einer der Wichtigsten ist der Binärbaum. Das bedeutet, dass jeder Knoten maximal zwei Nachfolger haben darf. Die Daten stehen in den Knoten bzw. den Blättern. Warum ein Binärbaum sehr effizient ist, können Sie an einem einfachen Beispiel sehen: dem Telefonbuch. Wie suchen Sie in einem Telefonbuch nach einem Namen? Wir gehen von dem Fall aus, dass die Daten alphabetisch sortiert und nicht in Städte eingeteilt sind.
Sie suchen z.B. den Namen „Michael Weber“. Dazu schlagen Sie das Telefonbuch in der Mitte auf. Da es alphabetisch sortiert ist, können Sie sagen, dass der gesuchte Name in der hinteren Hälfte liegt. Die vordere Hälfte müssen Sie also nicht mehr durchsuchen. Sie schlagen die hintere Hälfte in der Mitte auf. Auch hier können Sie bestimmen, in welchem Teil Sie weitersuchen müssen und welchen Teil Sie außer Acht lassen können. Auf diese Art können Sie sehr schnell und effektiv nach einem Namen suchen. Dies ist natürlich nur eine Analogie, mit der Sie sich das Prinzip vielleicht etwas besser vorstellen können.
Einfügen von Daten
Wie fügen wir nun Daten in einen Binärbaum ein? Die einfache Regel ist: in einem Teilbaum kommen die kleineren Werte links von der Wurzel, die größeren Werte rechts. Als Beispiel möchten wir Zahlen von 1 bis 100 in der folgenden Reihenfolge einfügen: 65, 40, 30, 80, 84, 75, 90.
Unsere Wurzel ist die erste Zahl, die 65. Die nächste Zahl ist kleiner; sie wird das linke Kind der Wurzel. 30 ist kleiner als 65: Sie betreten den linken Teilbaum. 30 ist aber auch kleiner als 40, also wird die Zahl das linke Kind von 40. 80 ist größer als 65, Sie betreten den rechten Teilbaum. Die Wurzel hat aber noch kein rechtes Kind. Folglich übernimmt die 80 diese Stelle. Die 84 ist größer als die Wurzel, also geht es nach rechts. Sie ist aber auch größer als die 80. Folglich wird sie rechtes Kind dieser Zahl. Die 75 ist größer als die Wurzel, aber kleiner als deren rechtes Kind (80). Sie wird also das linke Kind von 80.
Balancierte und unbalancierte Bäume
Binärbäume sollten balanciert sein. Das bedeutet, das die Daten ungefähr gleich auf allen Seiten verteilt sind. Sie können jedoch auch unbalanciert werden. Bleiben wir beim obigen Beispiel, den Zahlen von 1 bis 100. Starten wir mit der 90. Die meisten Zahl werden im linken Teilbaum angeordnet. Der Baum „hängt“ also sehr stark nach links; rechts stehen nur wenige Daten. Bei einem unbalancierten Baum, werden sämtliche Aktionen natürlich langwieriger, weil Sie durch längere Pfade navigieren müssen.