Binärbaum
framed|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 Kindknoten besitzt. Oft wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen.
| Inhaltsverzeichnis |
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 Bn bezeichnet, genau
- 2n+1-1 Knoten,
- 2i Knoten in Tiefe i, insbesondere also
- 2n Blätter und
- 2n-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 T1 sowie T2 binäre Bäume. Dann ist auch das Tripel (T1,x,T2) ein binärer Baum. Grafisch veranschaulicht sieht das so aus:
center 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, Fibonacci-Bäume und binäre Heaps basieren auf Binärbäumen.
Eine verbale Definition: Ein Baum ist entweder leer, oder er besteht aus einem linken oder rechten Teilbaum, die wiederum Bäume sind!
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.