Was ist ein Binärbaum?
Ein Binärbaum ist ein spezieller Graph in Form eines sich verästelnden Baumes. Binärbäume haben die Besonderheit, dass ihre Knoten immer höchstens zwei Nachkommen aufweisen. Diese teilen sich systematisch in eine linken und einen rechten Teilbaum auf.
Mit dieser Methode werden Dateien in einer Datenbank platziert und aufgefunden. Der Algorithmus findet Daten, indem er die Anzahl der letztlich zugänglichen Datensätze wiederholt halbiert, bis nur noch einer übrig bleibt.
Wie funktioniert ein Binärbaum?
In einem Baum werden Datensätze an Orten gespeichert, die Blätter genannt werden. Dieser Name leitet sich von der Tatsache ab, dass Datensätze immer an den Endpunkten vorhanden sind; dahinter gibt es nichts. Die Verzweigungspunkte werden als Knoten bezeichnet. Die Ordnung eines Baumes ergibt sich aus der Anzahl der Zweige (Kinder genannt) pro Knoten. In einem binären Baum gibt es immer zwei Kinder pro Knoten, die Ordnung ist also 2. Die Anzahl der Blätter in einem binären Baum ist immer eine Potenz von 2. Die Anzahl der Zugriffsoperationen, die erforderlich sind, um den gewünschten Datensatz zu erreichen, wird als Tiefe des Baums bezeichnet.
In einem praktischen Baum kann es Tausende, Millionen oder Milliarden von Datensätzen geben. Nicht alle Blätter enthalten notwendigerweise einen Datensatz, aber mehr als die Hälfte schon. Ein Blatt, das keinen Datensatz enthält, wird als Null bezeichnet.
Eine der bekanntesten Programmiersprachen ist hierbei Java. In Java hat ein binärer Suchbaum eine knotenbasierte binäre Baumdatenstruktur, die die folgenden Eigenschaften aufweist: Der linke Teilbaum eines Knotens enthält nur Knoten, deren Schlüssel kleiner als der Schlüssel des Elternknotens ist und der rechte Teilbaum enthält dagegen nur Knoten mit größerem Schlüssel.
Welche Anwendungen haben Binärbäume?
Es gibt verschiedene Arten von Binärbäumen, mit einzigartigen Eigenschaften.:
- Binäre Suchbäume stellen die relevantesten Vertreter der Binärbäume dar. Die Knoten in diesen Bäumen werden linear nach ihrem Schlüssel angeordnet. Mit ihrer Hilfe lassen sich in der Praxis effizientere Suchen umsetzen.
- Volle Binärbäume sind eine spezielle Art von Binärbaum, der entweder keine oder zwei Kinder hat. Das bedeutet, dass alle Knoten in diesem Baum entweder zwei Kindknoten des Elternknotens haben oder der Elternknoten selbst der Blattknoten oder der externe Knoten ist. Mit anderen Worten: Bei einem vollen Binärbaum handelt es sich um einen eindeutigen Baum, in welchem jeglicher Knoten zwei Kinder hat, außer dem externen Knoten. Selbst wenn dieser lediglich ein einziges Kind besitzt, ist ein solcher binärer Baum kein vollständiger Binärbaum. Hier ist die Anzahl der Blattknoten gleich der Anzahl der inneren Knoten +1. Die Gleichung lautet: L=I+1, wobei L die Anzahl der Blattknoten und I die Anzahl der internen Knoten ist.
- Ein vollständiger Binärbaum hat alle Ebenen des Baums vollständig mit Knoten gefüllt. Eine Ausnahme bildet hierbei die unterste Ebene des Baums. Auch in der letzten oder untersten Ebene dieses Baums sollte sich jeder Knoten möglichst auf der linken Seite befinden.
- Partiell geordnete Binärbäume zeichnen sich durch die Tatsache aus, dass ihre Wurzel immer ein Minimum für den Knoten des Teilbaums darstellen. In Richtung ihrer Blätter nehmen die Werte der Knoten zu oder bleiben zumindest auf einem gleichen Niveau.
- Ein Binärbaum wird als „perfekt“ bezeichnet, wenn alle internen Knoten genau zwei Kinder haben und jeder externe oder Blattknoten sich auf derselben Ebene oder Tiefe innerhalb eines Baumes befindet. Ein perfekter binärer Baum mit der Höhe ‚h‘ hat 2h – 1 Knoten.
- Liegt Baumhöhe O(logN), wobei „N“ die Anzahl der Knoten ist, vor, wird von ausgewogenen Binärbäumen gesprochen. In diesen sollte die Höhe des linken und des rechten Teilbaums jedes Knotens höchstens um eins variieren. Ein AVL-Baum und ein Rot-Schwarz-Baum sind einige gängige Beispiele für Datenstrukturen, die einen ausgewogenen binären Suchbaum erzeugen können.
- Bei degenerierten oder pathologischen Binärbäumen hat jeder interne Knoten nur ein einziges Kind. Solche Bäume ähneln in ihrer Leistung einer verketteten Liste.
