.webp)
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:
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 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.
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.
Außerdem muss gelten, dass jeder innere Knoten einen linken und eventuell zusätzlich einen rechten Kindsknoten besitzt.
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.
Vollständiger Binärbaum
Ein Binärbaum ist vollständig, wenn sich jedes Blatt auf der gleichen Höhe befindet.
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:
Bei dem vollständigen Beispiel-Binärbaum lautet das Ergebnis 7, da:
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.
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:
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.
.png)
.svg)
