Binärbaum

Binaerbaum.png
Ein voller, aber nicht vollständiger Binärbaum
Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt. Oft wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen.
Eine verbale Definition: Ein Baum ist entweder leer, oder er besteht aus einem linken oder rechten Teilbaum, die wiederum Bäume sind!

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 nn, den man häufig auch als BnB_{n} bezeichnet, genau
  • 2n+12^{n+1}-1 Knoten,
  • 2i2^{i} Knoten in Tiefe ii, insbesondere also
  • 2n2^{n} Blätter
besitzt, wobei mit Höhe nn die Länge des Pfades zu einem tiefsten Knoten bezeichnet wird. 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.

Anwendungen

Viele Datenstrukturen wie beispielsweise binäre Suchbäume, AVL-Bäume, Fibonacci-Bäume und binäre Heaps basieren auf 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 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 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. (siehe auch Balancierter Baum oder AVL-Baum)
 
 

Wie ist es möglich, daß die Mathematik, letztlich doch ein Produkt menschlichen Denkens unabhängig von der Erfahrung, den wirklichen Gegebenheiten so wunderbar entspricht?

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Binärbaum aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Wälder