Binärbaum

Grundidee und zentrale Begriffe

Ein Binärbaum ist eine in der Informatik besonders häufig verwendete Baumstruktur. Er ist entweder leer oder besteht aus einer Wurzel sowie einem linken und einem rechten Teilbaum, die selbst wieder Binärbäume sind. Jeder Knoten besitzt höchstens zwei direkte Nachkommen, die gewöhnlich eindeutig als linkes und rechtes Kind unterschieden werden. Ist ein Teilbaum leer, fehlt das entsprechende Kind. In Zeichnungen steht die Wurzel meist oben und die Blätter stehen unten.

Die Verbindungen zwischen den Knoten heißen gerichtete Kanten oder Bögen. Ein Binärbaum wird gewöhnlich als Out-Tree betrachtet: Genau die Wurzel hat den Eingangsgrad 0, alle anderen Knoten haben den Eingangsgrad 1. Der Ausgangsgrad gibt die Zahl der Kinder an und beträgt höchstens 2. Ein innerer Knoten hat mindestens ein Kind; ein Blatt oder äußerer Knoten hat kein Kind. Ein Knoten mit genau einem Kind wird gelegentlich Halbblatt genannt.

Im Artikel tragen alle Knoten einschließlich der Blätter Informationen. Die Höhe ist die maximale Anzahl der Knotenebenen. Andere Autoren definieren sie um 1 kleiner als maximale Tiefe; diese unterschiedliche Konvention ist zu beachten. Die Tiefe eines Knotens ist die Anzahl der Bögen zwischen ihm und der Wurzel.

Ein geordneter Binärbaum besitzt bei jedem inneren Knoten ein linkes und eventuell zusätzlich ein rechtes Kind; außerdem ist der linke Knoten „kleiner“ und der rechte „größer“ als der betrachtete Knoten. Ein voller, auch saturierter oder strikter Binärbaum hat an jedem Knoten entweder kein Kind oder genau zwei Kinder. Ein voller Baum heißt vollständig, wenn alle Blätter dieselbe Tiefe haben. Ein entarteter Binärbaum besteht nur aus Blättern und Halbblättern und entspricht damit einer Liste; Sonderfälle enthalten ausschließlich linke oder ausschließlich rechte Kinder.

Eigenschaften, Formen und Anzahl

Für einen Binärbaum mit n Knoten gelten grundlegende Zählregeln:

• Er besitzt n−1 Kanten.
• Er besitzt n+1 unmittelbare Einfügepunkte.
• Bei b Blättern und c Halbblättern gibt es 2b+c unmittelbare Einfügepunkte.
• Ist i die Zahl der inneren Knoten, gilt i=b−1.

Ein vollständiger Binärbaum der Höhe h≥1, oft B_h genannt, besitzt genau 2^h−1 Knoten, 2^(h−1)−1 innere Knoten, 2^t Knoten in Tiefe t für 0≤t≤h−1 und damit 2^(h−1) Blätter. Ein vollständig balancierter Binärbaum ist voll und die Abstände von der Wurzel zu zwei beliebigen Blättern unterscheiden sich höchstens um 1. Jeder vollständige Binärbaum ist daher vollständig balanciert.

Die Anzahl C_n verschiedener Binärbäume mit n Knoten ist die n-te Catalan-Zahl. Es gilt C_0=1 und für n>0 C_n=Σ_(i=0)^(n−1) C_i·C_(n−1−i). Explizit gilt C_n=1/(n+1)·(2n über n)=(2n)!/((n+1)!·n!). Für n=1 bis 8 ergeben sich 1, 2, 5, 14, 42, 132, 429 und 1430 Bäume.

Diese Zählung entspricht den Möglichkeiten, einen Ausdruck aus n zweistelligen Operatoren und n+1 fest angeordneten Elementen vollständig zu klammern. Für n=3 besitzt XXXX genau fünf zulässige Klammerungen, beispielsweise ((XX)X)X oder (XX)(X*X). Jeder Operator entspricht einem Knoten, sein linker beziehungsweise rechter Ausdruck dem linken beziehungsweise rechten Teilbaum. Zusätzliche, inhaltlich überflüssige Klammern werden nicht mitgezählt.

Wichtige Anwendungen

Die wichtigste praktische Anwendung ist der binäre Suchbaum. Jeder Knoten enthält einen Schlüssel; die Schlüssel sind linear im Baum geordnet, sodass effizient gesucht werden kann. Zu den binären Suchbäumen gehören AVL-Bäume, Rot-Schwarz-Bäume und Splay-Bäume.

Bei einem partiell geordneten Baum stammen die Knotenmarkierungen aus einem geordneten Wertebereich. Für jeden Teilbaum mit Wurzel x sind alle enthaltenen Knoten größer oder gleich x markiert. Die Wurzel jedes Teilbaums stellt somit dessen Minimum dar; in Richtung der Blätter nehmen die Werte zu oder bleiben gleich. Solche Bäume werden häufig für Heaps verwendet.

Binäre Heaps, Fibonacci-Bäume und pythagoreische Binärbäume beruhen ebenfalls auf Binärbäumen. Beim pythagoreischen Binärbaum werden die Knoten als rechtwinklige Dreiecke und die Bögen als Rechtecke dargestellt.

Speicherung und Zugriff

Eine übliche Speicherform legt für jeden Knoten einen Schlüssel sowie zwei Zeiger auf das linke und rechte Kind an. Ein besonderer Zeiger verweist auf die Wurzel; ein Nullzeiger kennzeichnet ein fehlendes Kind. Gegenüber einem Array erlaubt diese Darstellung eine flexible Speicherverwaltung, weil Speicher zusammen mit einzelnen Knoten angelegt oder freigegeben werden kann.

Speichert jeder Knoten zusätzlich die Anzahl der Elemente seines Teilbaums, lässt sich ein Element anhand seines In-Order-Index ähnlich wie anhand eines Schlüssels im Suchbaum finden. Der Aufwand beträgt O(h), wobei h die Baumhöhe ist. Einfügen und Löschen erfordern allerdings Korrekturen bis zur Wurzel und können die Indizes verändern. Für statische Bäume ist ein gewöhnlicher Array-Index schneller.

Ein Knoten kann auch durch eine Binärkette beschrieben werden: Eine anfängliche 0 bezeichnet den leeren Baum, eine anfängliche 1 die Wurzel; jede weitere 0 führt zum linken, jede 1 zum rechten Kind. Der maximale Zugriffsaufwand ist O(h). Bei höhenbalancierten Bäumen ist die Länge durch O(log n) beschränkt.

Bei einer impliziten Arraydarstellung beginnt die Wurzel bei Index 1; anschließend werden die Ebenen jeweils von links nach rechts gespeichert. Für A_i liegt das linke Kind bei A_(2i), das rechte bei A_(2i+1) und der Elternknoten bei A_⌊i/2⌋. Es sind keine ausdrücklichen Zeiger nötig. Ein nicht voll besetzter Baum benötigt jedoch Platzhalter und verschwendet bei Höhe h und n Knoten 2^h−1−n Speicherzellen. Diese Darstellung wird unter anderem für binäre Heaps genutzt; in der Genealogie heißt das Schema Kekule-Nummerierung.

Traversieren, Einfügen und Löschen

Traversierung bedeutet, alle Knoten systematisch in einer bestimmten Reihenfolge zu untersuchen. Bei der Tiefensuche wird zunächst ein Pfad in die Tiefe verfolgt. Standardmäßig kommt der linke Teilbaum L vor dem rechten R. Abhängig von der Position des aktuellen Knotens N entstehen:

• Pre-order N–L–R: erst N, dann linker und rechter Teilbaum.
• In-order L–N–R: linker Teilbaum, N, rechter Teilbaum. Bei binären Suchbäumen entspricht dies der Sortierreihenfolge.
• Post-order L–R–N: beide Teilbäume vor N.
• Reverse in-order R–N–L: rechter Teilbaum, N, linker Teilbaum.

Rekursive Verfahren rufen für jeden Knoten genau einmal die jeweilige Traversierungsfunktion auf und benötigen daher Θ(n). Eine iterative In-Order-Traversierung bestimmt schrittweise den Nachfolger oder Vorgänger. Über den ganzen Baum wird jede der n−1 Kanten einmal abwärts und einmal aufwärts durchlaufen, also in 2n−2∈Θ(n) Schritten. Ein einzelner Schritt kostet durchschnittlich O(1), im schlechtesten Fall O(h). Bei der Breitensuche oder Level-order werden beginnend an der Wurzel die Ebenen von links nach rechts besucht. Der Abstieg zum ersten beziehungsweise letzten Element folgt fortgesetzt linken beziehungsweise rechten Kindern und benötigt O(h).

Ein Einfügepunkt besteht aus einem Knoten und der Richtung links oder rechts. Ist er bereits erreicht, wird der entsprechende Kindzeiger auf den neuen Knoten gesetzt. Das Einfügen selbst hat konstante Komplexität, und der neue Knoten ist zunächst ein Blatt. Wiederholtes Einfügen an derselben Seite kann den Baum zu einer Liste entarten.

Beim Löschen eines Blatts wird dieses entfernt. Hat der Knoten genau ein Kind, tritt dieses an seine Stelle. Bei zwei Kindern muss zur Bewahrung der In-Order-Reihenfolge bis zu einem Halbblatt abgestiegen werden. Der Knoten kann etwa durch seinen unmittelbaren linken oder rechten In-Order-Nachbarn ersetzt werden; ein vorhandener Teilbaum dieses Nachbarn wird anschließend an dessen alter Stelle eingehängt. Abwechselnde Abstiegsrichtungen oder vorhandene Balancewerte können einseitiges Wachstum begrenzen. Im schlechtesten Fall kostet das Löschen O(h); auch wiederholtes Löschen kann einen Baum entarten lassen.

Rotationen und Umformungen

Eine Rotation verändert lokal die Form eines Binärbaums, etwa um Teilbaumhöhen oder Suchtiefen zu beeinflussen. Alle beteiligten Knoten bewegen sich nur vertikal, sodass die In-Order-Reihenfolge und damit bei Suchbäumen die Sortierreihenfolge erhalten bleibt. Bei einer Linksrotation wird die bisherige Teilbaumwurzel L abgesenkt und ihr rechtes Kind R angehoben: L wird linkes Kind von R, während der zuvor linke Teilbaum von R zum rechten Teilbaum von L wird. Die Rechtsrotation ist die spiegelbildliche Umkehrung. Drei Verknüpfungen müssen angepasst werden; die Laufzeit ist O(1).

Eine Doppelrotation verbindet zwei gegenläufige Einzelrotationen und hebt einen Knoten um zwei Ebenen an. Sie wird beispielsweise beim Ausbalancieren von AVL-Bäumen verwendet und verändert fünf Verknüpfungen. Beim Spalten eines AVL-Baums können auch Dreifachrotationen auftreten.

Der Rotationsabstand zweier Binärbäume mit gleich vielen Knoten ist die kleinste Zahl von Rotationen, die den einen in den anderen überführt. Dadurch wird die Menge BT_n der Binärbäume mit n Knoten zu einem zusammenhängenden metrischen Raum. Sein Durchmesser ist höchstens 2n−6. Ob es einen polynomiellen Algorithmus zur Berechnung des Rotationsabstands gibt, ist ungeklärt.

Unter Erhaltung der In-Order-Reihenfolge sind mehrere lineare Umformungen möglich: Ein Binärbaum kann mit O(n) Zeit und Platz in eine geordnete Liste umgewandelt werden. Eine geordnete Liste lässt sich in O(n) Zeit in einen vollständig balancierten Binärbaum überführen; bei m Knoten erhält der linke Teilbaum ⌈(m−1)/2⌉ und der rechte ⌊(m−1)/2⌋ Knoten. Ebenfalls in O(n) kann jeder Knoten mit der Größe seines Teilbaums versehen werden. Ein AVL-Baum lässt sich ohne Formänderung in O(n) Zeit als Rot-Schwarz-Baum einfärben; AVL-Bäume bilden eine echte Teilmenge der Rot-Schwarz-Bäume.