Binärbaum

Binärbäume sind in der Informatik die am häufigsten verwendete Unterart der Bäume. Im Gegensatz zu anderen Arten von Bäumen können die Knoten eines Binärbaumes nur höchstens zwei direkte Nachkommen haben.

Meist wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen. Ein anschauliches Beispiel für einen solchen Binärbaum ist die Ahnentafel, bei der allerdings die Elternteile durch die Kindknoten zu modellieren sind.

Ein Binärbaum ist entweder leer, oder er besteht aus einer Wurzel mit einem linken und rechten Teilbaum, die wiederum Binärbäume sind. Ist ein Teilbaum leer, bezeichnet man den entsprechenden Kindknoten als fehlend.

Meistens wird die Wurzel in graphischen Darstellungen (wie in der nebenstehenden) oben und die Blätter unten platziert. Entsprechend ist ein Weg von der Wurzel in Richtung Blatt einer von oben nach unten.

Begriffe mini|235px|Binärbaum mit Knotentypenzu finden bei Rot-Schwarz-Bäumen Die Begriffe Knoten und Kante werden von den Graphen übernommen. Die Kante ist definitionsgemäß gerichtet (auch: Bogen oder Pfeil). Wenn es aus dem Kontext klar genug hervorgeht, wird auch nur von Kante gesprochen.

Bei gerichteten Graphen kann man einem Knoten sowohl Ausgangsgrad wie Eingangsgrad zuordnen. Üblicherweise werden Binärbäume als Out-Trees aufgefasst. In einem solchen gewurzelten Baum gibt es genau einen Knoten, der den Eingangsgrad 0 hat. Er wird als die Wurzel bezeichnet. Alle anderen Knoten haben den Eingangsgrad 1. Der Ausgangsgrad ist die Anzahl der Kindknoten und ist beim Binärbaum auf maximal zwei beschränkt. Damit ist seine Ordnung als . Knoten mit Ausgangsgrad ≥ 1 bezeichnet man als innere Knoten, solche mit Ausgangsgrad 0 als Blätter oder äußere Knoten.

mini|235px|Binärbaum mit Knotentypen Vielfach findet sich in der Literatur auch eine Sichtweise, bei der alle Knoten Information tragen und externe Blätter nicht vorkommen. Dann gibt es bei Binärbäumen – und nur dort – gelegentlich die Bezeichnung Halbblatt für einen Knoten mit Ausgangsgrad 1 (englisch manchmal: non-branching node).

Die Höhe eines gewurzelten Baums ist die maximal auftretende Tiefe. Viele Autoren setzen sie aber um eins höher, da man so dem leeren Baum die Höhe 0 und dem nur aus der Wurzel bestehenden Baum die Höhe 1 geben kann, was gewisse rekursive Definitionen kürzer zu fassen gestattet. (Und da Tiefe ein Attribut eines Knotens, Höhe aber eines des ganzen Baums ist, muss es nicht unbedingt Verwirrungen geben.)Die Höhe kommt betragsmäßig damit auf denselben Wert wie Knuth, der neben den Schlüssel tragenden Knoten (bei ihm „innere“ genannt) noch „äußere“ Knoten kennt, die als Einfügepunkte aufgefasst werden können und die die Höhe (der ersten Definition entsprechend) um 1 erhöhen.

Zur Beachtung In diesem Artikel ist die letztere Sichtweise durchgehalten: Alle Knoten einschließlich Wurzel und Blätter tragen Information („knotenorientierte Speicherung“). Die Höhe des Baums ist die Maximalzahl der Knotenebenen.

Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwa nur ein rechtes Kind), sowie der linke Knoten „kleiner“, der rechte Knoten „größer“ als der Betrachtungsknoten ist. Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt), oder aber zwei (also sowohl ein linkes wie ein rechtes) Kinder besitzt – es also kein Halbblatt gibt. Für die Eigenschaft voll werden gelegentlich auch die Begriffe saturiert oder strikt verwendet. Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe haben, wobei die Tiefe eines Knotens als die Anzahl der Bögen bis zur Wurzel definiert ist.

Der Binärbaum wird entartet genannt, wenn jeder Knoten entweder Blatt ist (Anzahl Kinder ist 0) oder Halbblatt (Anzahl Kinder ist 1). In diesem Fall stellt der Baum eine Liste dar. Besondere Formen sind die geordneten Listen, bei denen ein Baum jeweils nur aus linken oder nur aus rechten Kindern besteht.

Eigenschaften So wie ein Baum mit Knoten Kanten hat, hat ein Binärbaum mit Knoten Kanten. Ein Binärbaum mit Knoten hat (unmittelbare) Einfügepunkte. Ein Binärbaum mit Blättern und Halbblättern hat an jedem Halbblatt einen Einfügepunkt und an jedem Blatt zwei, also (unmittelbare) Einfügepunkte. Ist die Anzahl der inneren Knoten, so errechnet sich .

Kombinatorik Die Anzahl der Binärbäume mit Knoten entspricht der Anzahl der Möglichkeiten, eine Zeichenfolge von geordneten Symbolen, die durch mathematische Operatoren für eine zweistellige Verknüpfung, zum Beispiel Addition, Subtraktion, Multiplikation oder Division, getrennt sind, vollständig in Klammern zu setzen. Die Reihenfolge der Zahlen oder Elemente, zum Beispiel Matrizen, ist festgelegt. Die Operation muss weder assoziativ noch kommutativ sein.

Dabei entspricht jeder Knoten einer zweistelligen Verknüpfung und für jeden Knoten entspricht der linke Teilbaum dem linken Ausdruck und der rechte Teilbaum dem rechten Ausdruck der Verknüpfung.

Zum Beispiel muss man für eine Zeichenfolge wie in Klammern setzen, was auf fünf verschiedene Arten möglich ist:

Ein explizites Beispiel für die Subtraktion ist

Das Hinzufügen redundanter Klammern um einen bereits in Klammern gesetzten Ausdruck oder um den vollständigen Ausdruck herum ist nicht zulässig.

Es gibt einen Binärbaum mit 0 Knoten und jeder andere Binärbaum ist durch die Kombination aus seinem linken und seinem rechten Teilbaum gekennzeichnet. Wenn diese Teilbäume bzw. Knoten haben, hat der gesamte Baum die Knoten. Daher hat die Anzahl von Binärbäumen mit Knoten die folgende rekursive Beschreibung und für jede positive ganze Zahl . Daraus folgt, dass die Catalan-Zahl mit Index ist. Es gilt Anzahl der BinärbäumenCn1122354145426132742981430

Anwendungen Binärer Suchbaum Die in der Praxis wohl wichtigste Anwendung der Binärbäume sind die binären Suchbäume, worunter die AVL-Bäume, Rot-Schwarz-Bäume und Splay-Bäume zu rechnen sind. Bei Suchbäumen gibt es in jedem Knoten „Schlüssel“, nach denen die Knoten „linear“ im Baum geordnet sind. Auf dieser Ordnung basiert dann ein möglichst effizientes Suchen.

Partiell geordneter Baum Ein partiell geordneter Baum T ist ein spezieller Baum, dessen Knoten markiert sind dessen Markierungen aus einem geordneten Wertebereich stammen in dem für jeden Teilbaum U mit der Wurzel x gilt: Alle Knoten aus U sind größer markiert als x oder gleich x.

Intuitiv bedeutet dies: Die Wurzel jedes Teilbaumes stellt ein Minimum für diesen Teilbaum dar. Die Werte des Teilbaumes nehmen in Richtung der Blätter zu oder bleiben gleich.

Derartige Bäume werden häufig in Heaps verwendet.

Vollständiger Binärbaum und vollständig balancierter Binärbaum Ein vollständiger Binärbaum ist ein voller Binärbaum (alle Knoten haben entweder 2 oder 0 Kinder), in dem alle Blätter die gleiche Tiefe haben. Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe , den man häufig als bezeichnet, genau Knoten, innere Knoten (nicht Blatt, aber evtl. Wurzel), Knoten in Tiefe für , insbesondere also Blätter besitzt.

Ein vollständig balancierter Binärbaum ist ein voller Binärbaum, bei dem die Abstände von der Wurzel zu zwei beliebigen Blättern um höchstens 1 voneinander abweichen. Ein vollständiger Binärbaum ist ein vollständig balancierter Binärbaum. (Vergleiche Balancierter Baum und AVL-Baum.)

Weitere Binärbäume Eine Darstellung eines Binärbaumes, in dem die Knoten mit rechtwinkligen Dreiecken und die Bögen mit Rechtecken dargestellt werden, nennt man pythagoreischen Binärbaum.

Auch Fibonacci-Bäume und binäre Heaps basieren auf Binärbäumen.

Repräsentation und Zugriff links|mini|260px|Darstellung eines Binärbaums im Speicher Die Abbildung zeigt eine naheliegende Art der Speicherung. Sie entspricht in etwa den C-Strukturen: struct knoten { // 1 Objekt = 1 Knoten char schlüssel; struct knoten * links; // linkes Kind struct knoten * rechts; // rechtes Kind } object; struct knoten * anker; // Zeiger auf die Wurzel Zur besseren Unterscheidung der Objekte sind diese beziehentlich mit den Schlüsseln »F«, »G«, »J« und »P« versehen. Diese Schlüssel sind auch der Einfachheit halber als Ziel der Verweise genommen worden (anstelle von echten Speicheradressen). Wie üblich soll ein Zeigerwert 0 ausdrücken, dass auf kein Objekt verwiesen wird, es also kein Kind an dieser Stelle gibt.

Der große Vorteil des Baums gegenüber dem Array liegt in der flexibleren Speicherverwaltung: Mit dem Entstehen oder Vergehen eines Objektes kann auch der es darstellende Speicher entstehen oder vergehen, wogegen die einzelnen Einträge beim Array fest mit diesem verbunden sind.

In-Order-Index Wird in jedem Knoten die Anzahl der Elemente des zugehörigen Unterbaums gehalten, kann das Aufsuchen eines Elements vermöge seines in-order-Index in ganz ähnlicher Weise wie das Aufsuchen mit einem Schlüssel im binären Suchbaum bewerkstelligt werden. Dies hat allerdings die nachteilige Implikation, dass Einfüge- und Löschoperation immer Korrekturen bis hinauf zur Wurzel erfordern, womit sich dann auch die in-order-Indizes von Knoten ändern. Die Vorgehensweise dürfte also bei nicht statischen Binärbäumen von fraglichem Wert sein, und bei statischen ist der gewöhnliche Array-Index in Bezug auf Laufzeit überlegen.

Der Aufwand ist , wobei die Höhe des Baums ist.

Links/Rechts-Index Jeder Knoten kann durch eine variabel lange Kette von Binärziffern genau spezifiziert werden. Die Maßgabe könnte folgendermaßen lauten:

Eine „0“ am Anfang (gleichzeitig Ende) entspricht dem leeren Binärbaum. Eine „1“ am Anfang lässt auf die Wurzel zugreifen. Eine anschließende „0“ bzw. „1“ lässt auf das linke bzw. rechte Kind zugreifen.

Jedem Knoten in einem Binärbaum kann so eindeutig eine Binärkette zugeordnet werden.

Bei höhen-balancierten Bäumen ist die Binärkette in ihrer Länge durch beschränkt, so dass sie in ein vorzeichenloses Integer passen mag. Eine denkbare Codierung der variablen Länge in einem Wort fester Länge lässt die Binärkette nach der ersten „1“ beginnen.

Der maximale Aufwand für einen Zugriff ist .

mini|125px|Binärbaum mit Arrayindizes an den Knoten

Repräsentation durch ein Array Ein Binärbaum kann durch ein Array repräsentiert werden, dessen Länge im Wesentlichen der Anzahl der Knoten des Baumes entspricht, genauer: mit als der Höhe des Baumes. Eine Anordnung findet sich bei der binären Suche im Array.

Eine andere Art der Repräsentation beginnt mit der Indizierung bei 1 mit Verweis auf die Wurzel. Dann setzt sie sich „zeilenweise“ fort: alle Knoten derselben Tiefe werden von links nach rechts fortlaufend nummeriert. Das heißt: das Auslesen des Arrays von links entspricht einem Level-Order-Traversal (oder Breadth-First-Traversal) des Baums. Falls der Binärbaum nicht voll besetzt ist, müssen ausgelassene Knoten durch Platzhalter besetzt werden, so dass also Speicherzellen verschwendet werden.

400px|mini|Beispiel für die implizite Darstellung eines Binärbaums in einem Array mit Startindex 1. Diese Nummerierung hat die angenehme Eigenschaft, dass man leicht die Indizes der verbundenen Knoten berechnen kann. Im Array sei ein Knoten, dann ist sein linkes und sein rechtes Kind; die abgerundete Hälfte verweist auf den Elter .

In der Genealogie ist dieses Indizierungsschema auch unter dem Begriff Kekule-Nummerierung bekannt.

Da bei der Abbildung von einem Binären Baum in ein Array keine expliziten Zeiger auf Kinder bzw. Elter-Knoten notwendig sind, wird diese Datenstruktur auch als implizite Datenstruktur bezeichnet.

Eine Anwendung dieser Darstellung ist der binäre Heap, der für die Sortierung von Elementen verwendet wird.

Traversierung Traversierung bezeichnet das systematische Untersuchen der Knoten des Baumes in einer bestimmten Reihenfolge. Von den verschiedenen Möglichkeiten, die Knoten von Binärbäumen zu durchlaufen, unterscheidet man vor allem die folgenden Varianten:Die Bezeichnungen finden sich bspw. bei Knuth.