Was ist ein binärer Baum?
Ein binärer Baum ist eine Art Datenstruktur, die in der Computerprogrammierung zum Speichern, Sortieren und Zugreifen auf Informationen verwendet wird. Binäre Bäume sind die einfachste Baumsorte, aber sehr nützlich und einfach zu implementieren. Eine typische Implementierung eines Binärbaums beruht auf einem Wurzelknoten, der mit einer Reihe von Knoten verknüpft ist, aus denen der Baum selbst durch Zeigervariablen besteht. Dieser Baumtyp leitet seinen Namen von der Tatsache ab, dass kein Knoten innerhalb des Baums mehr als zwei Kinder haben kann.
Baumdatenstrukturen gibt es in vielen Varianten. Sie bestehen aus verschiedenen Knoten, die in einem hierarchischen Muster organisiert sind. Ein einzelner Knoten, der Stamm, ist der Zugriffspunkt, über den der gesamte Datenbaum durchsucht oder auf andere Weise bearbeitet werden kann. Dieser Wurzelknoten zeigt auf den obersten Knoten innerhalb des Baums.
Jeder Knoten in einem Baum, mit Ausnahme des obersten Knotens, hat einen übergeordneten Knoten, der sich in der Hierarchie des Baums darüber befindet. Es kann auch untergeordnete Knoten haben, die sich darunter befinden. Auf einen bestimmten Knoten wird über die darüber liegenden Knoten in der Baumstruktur zugegriffen und bietet Zugriff auf die darunter liegenden Knoten.
Bei binären Baumdatenstrukturen darf jeder Knoten nicht mehr als zwei untergeordnete Knoten haben. An einen bestimmten Knoten können daher null, ein oder zwei untergeordnete Knoten angehängt sein. Normale Binärbäume ermöglichen Knoten mit einer beliebigen Anzahl von untergeordneten Elementen an einer beliebigen Stelle im Baum. Sie unterliegen auch keinen Einschränkungen hinsichtlich der Anordnung der Werte, die in Knoten gespeichert sind, aus denen ein Baum besteht.
Datenstrukturen sind am nützlichsten, wenn sie die Geschwindigkeit verbessern, mit der ein Computer auf Daten zugreifen kann, und modifizierte Versionen von Binärbäumen verwendet werden, um deren Effizienz zu verbessern. Ein binärer Suchbaum ist einer, in dem alle Datenwerte, die sich auf dem linken absteigenden Ast eines bestimmten Knotens befinden, Werte haben, die gleich oder kleiner als der in diesem Knoten gespeicherte Wert sind. Die Werte auf der rechten Seite eines Knotens in einem geordneten Binärbaum müssen wiederum größer sein als der Wert im Basisknoten. Diese Datenreihenfolge ermöglicht das Schreiben eines viel effizienteren Suchalgorithmus.
Die Form eines Binärbaums ist auch wichtig für die Bestimmung der Effizienz eines Suchalgorithmus. Die am wenigsten effiziente Variante eines Binärbaums ist eine, bei der jeder Knoten nur ein einziges Kind hat. Ein Computer muss möglicherweise jedes Datenelement in der gesamten Struktur untersuchen, um eine einzelne Information in dieser Konfiguration zu finden. Im Gegensatz dazu ist der effizienteste Binärbaum einer, bei dem jeder Knoten, der für die am unteren Ende des Baums gespeichert ist, zwei untergeordnete Knoten hat und bei dem alle Blattknoten, die unteren Knoten im Baum, den gleichen Abstand von der Wurzel haben.