Binärbaum - Dynamische Datenstrukturen

Baum

Ein Baum (engl. tree) ist eine dynamische Datenstruktur, in dem Werte hierarchisch gespeichert werden.


Erklärung

Du kannst dir einen Baum wie seinen Namensgeber vorstellen:

  • Die Wurzel ist ein einzelner Knoten, der keine Vorfahren hat.
  • Die Blätter sind die letzten Knoten im Baum, sie haben also keine Nachfolger.

Zusätzlich gibt es innere Knoten, die Vorgänger (auch Elternknoten) und Nachfolger (auch Kindsknoten) haben.

Hier siehst du beide Bäume im Vergleich:

Links im Bild ist ein normaler Baum, der jedoch kopfüber hängt. Rechts ist ein Baum als Datenstruktur. Er besteht aus Knoten und Kanten.

Wie du siehst, ist - anders als beim richtigen Baum - die Wurzel oben.

In den Knoten können jeweils Werte gespeichert werden.

Aufbau

Ein Baum startet oben mit einer Wurzel. Von dieser gehen Kanten zu den beliebig vielen inneren Knoten oder auch Kindsknoten.

Diese sind wiederum über Kanten mit ihren Kindsknoten verbunden.

Das geht so lange weiter, bis die Knoten keine Nachfolger haben. Diese sind die Blätter des Baumes.

Bei einem regulären Baum können Knoten beliebig viele Nachfolger haben.

Ein Baum kann aus mehreren Teilbäumen bestehen:

Ein Baum, in dem alle drei Teilbäume eingekreist sind.

Ein Baum kann auch über seine Höhe beschrieben werden.

Die Wurzel hat dabei die Höhe 1, die Kinder der Wurzel die Höhe 2 und so weiter.

Wenn ein Baum leer ist, hat er die Höhe 0.

Binärbaum

Wie auch in der Natur gibt es in der Informatik verschiedene Unterarten von Bäumen, wie den Binärbaum.

Bei einem Binärbaum hat jeder Knoten höchstens zwei Nachfolger.

Zusätzlich zu der Wurzel, den inneren Knoten und den Blättern gibt es Halbblätter. Das sind Knoten, die nur ein Blatt als Kind haben.

Ein Binärbaum mit 6 Knoten. Alle Bestandteile sind beschriftet. Die Wurzel ist der oberste Knoten, die Kanten sind die Striche zwischen den Knoten und die inneren Knoten sind die, die zwischen zwei Kanten liegen. Ein Halbblatt ist ein Knoten, der nur einen Nachfolger hat. Ein Blatt ist ein Knoten, der keine Nachfolger hat, diese sind also ganz unten im Baum.

Eigenschaften Binärbaum

Ein Binärbaum kann zusätzlich folgende Eigenschaften erfüllen:

  • Geordnet
  • Voll
  • Vollständig
  • Balanciert

Geordneter Binärbaum

Ein Binärbaum ist dann geordnet, wenn der linke Kindsknoten kleiner und der rechte Kindsknoten größer als der Elternknoten ist.

Ein Binärbaum, bei dem auf allen linken Kanten ein keiner als-Zeichen und auf allen rechten ein größer als-Zeichen steht. Der linke und rechte Teilbaum sind eingekreist.

Außerdem muss gelten, dass jeder innere Knoten einen linken und eventuell zusätzlich einen rechten Kindsknoten besitzt.

Ein Binärbaum, in dem alle linken Kinder markiert sind.

Voller Binärbaum

Ein Binärbaum ist voll, wenn er maximal besetzt ist.

Das bedeutet, dass jeder Knoten entweder ein Blatt ist oder genau zwei Kinder hat.

Ein voller Binärbaum mit fünf Knoten: eine Wurzel, zwei in der zweiten Ebene und zwei in der dritten Ebene. Dabei sind die zwei Knoten der dritten Ebene die Nachfolger des linken Knotens aus der Ebene davor.

Vollständiger Binärbaum

Ein Binärbaum ist vollständig, wenn sich jedes Blatt auf der gleichen Höhe befindet.

Ein vollständiger Binärbaum, bei der auf Ebene eins ein Knoten, auf Ebene zwei zwei und auf Ebene drei vier Knoten sind. Links steht die Höhe neben jeder Ebene.

Hier sind zum Beispiel alle Blätter auf Höhe 3.

Wenn diese Eigenschaft gilt, kann die Anzahl an Knoten (n) berechnet werden, die ein Binärbaum mit einer bestimmten Höhe (h) hat.

Dafür benutzt du folgende Formel:

n = 2^h - 1n=2h1n = 2^h - 1

Bei dem vollständigen Beispiel-Binärbaum lautet das Ergebnis 7, da:

n = 2^3 - 1 = \underline{\underline{7}}n=231=7n = 2^3 - 1 = \underline{\underline{7}}

Balanciertier Binärbaum

In einem balancierten Binärbaum (auch AVL-Baum), unterscheidet sich die Höhe der beiden Teilbäume eines jeden Knotens um höchstens 1.

Ein balancierter Binärbaum mit der Höhe vier und sieben Knoten. Die Höhe der beiden Teilbäume eines jeden Knotens unterscheiden sich um maximal 1.

Beispiel

Aus den Werten [5, 3, 1, 6, 8, 10, 13] kannst du einen Binärbaum erzeugen, der alle vier Eigenschaften erfüllt. Dieser kann beispielsweise so aussehen:

Ein  Binärbaum mit der Höhe 3 und den Zahlen 6, 3, 10, 1, 5, 8, 10. Die Zahlen sind dabei von oben nach unten und von rechts nach links abgelesen. Jeder Knoten (bis auf die Blätter) hat genau zwei Kinder.

Geordneter Binärbaum

Der Binärbaum ist geordnet, da alle Werte, die kleiner als 6 sind, links und alle die größer als 6 sind, rechts von der Wurzel (6) stehen. Auch innerhalb der Teilbäume gilt die Sortierung nach Größe.

Voller Binärbaum

Der Binärbaum ist voll, da jeder Knoten entweder ein Blatt ist oder zwei Kinder besitzt.

Vollständiger Binärbaum

Der Binärbaum ist vollständig, da jedes Blatt die gleiche Höhe hat.

Balancierter Binärbaum

Der Binärbaum ist balanciert, da er vollständig ist. Somit gilt auch die Bedingung, dass sich die Höhe der Blätter um höchstens 1 unterscheiden.

No items found.

simpleclub ist am besten in der App.

Mit unserer App hast du immer und überall Zugriff auf: Lernvideos, Erklärungen mit interaktiven Animationen, Übungsaufgaben, Karteikarten, individuelle Lernpläne uvm.

Jetzt simpleclub Azubi holen!

Mit simpleclub Azubi bekommst du Vollzugang zur App: Wir bereiten dich in deiner Ausbildung optimal auf deine Prüfungen in der Berufsschule vor. Von Ausbilder*innen empfohlen.

Jetzt simpleclub Azubi holen