Binärbaum

Ein voller, aber nicht vollständiger Binärbaum

Ein Binärbaum ist in der Graphentheorie ein gewurzelter Baum, genauer ein Out-Tree, bei dem jeder Knoten höchstens zwei Kinder besitzt. Oft wird verlangt, dass sich die Kinder eindeutig in linkes und rechtes Kind einteilen lassen.

Weitere Begriffe

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). 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. Man bezeichnet ihn als vollständig, wenn alle Blätter die gleiche Tiefe besitzen. Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe n, den man häufig auch als B_n bezeichnet, genau

2ⁿ-1 Knoten,
2ⁱ Knoten in Tiefe i, insbesondere also
2ⁿ Blätter und
2²ⁿ-1 innere Knoten

besitzt.

Eine Darstellung eines Binärbaumes, in dem die Knoten mit rechtwinkligen Dreiecken und die Kanten mit Rechtecken dargestellt werden, nennt man pythagoräischen Binärbaum.

Rekursive Definition

Der leere Baum ist ein binärer Baum.
Sei $x$ ein Knoten und seien $T_{1}$ sowie $T_{2}$ binäre Bäume. Dann ist auch das Tripel $(T_{1},x,T_{2})$ ein binärer Baum. Grafisch veranschaulicht sieht das so aus:

Datei:Binaerbaum-definition.png

Mittels dieser beiden Regeln lassen sich beliebige binäre Bäume aufbauen. Man beachte, dass der Aufbau eines Baumes dabei bottom-up verläuft. Man beginnt mit den Blättern und baut dann den Baum schrittweise bis zum Wurzelknoten auf.

Anwendungen

Viele Datenstrukturen wie beispielsweise binäre Suchbäume, AVL-Bäume und binäre Heaps basieren auf Binärbäumen.

Linearisierung von Binärbäumen

Es gibt verschiedene Möglichkeiten, die Knoten von Binärbäumen zu durchlaufen. Diesen Prozess nennt man auch Linearisieren. Man unterscheidet hier in

pre-order (W - L - R): wobei zuerst die Wurzel (W) betrachtet wird und anschließend zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird,
in-order (L - W - R): wobei zuerst der linke (L) Teilbaum durchlaufen wird, dann die Wurzel (W) betrachtet und anschließend der rechte (R) Teilbaum durchlaufen wird und
post-order (L - R - W): wobei zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird und anschließend die Wurzel (W) betrachtet wird.

siehe auch: Linearisierung von Binärbäumen

Einige spezielle Binärbäume

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 T' mit der Wurzel x gilt: Alle Knoten aus T' sind kleiner 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 balancierter Binärbaum

Ein vollständiger balancierter Binärbaum ist ein vollständiger Binärbaum, bei dem die Abstände zweier beliebiger Blätter von der Wurzel um höchstens 1 voneinander abweichen, ficken!!!