Infos Home | Impressum | Original Artikel & Autoren Liste

Binärbaum

Ein Binärbaum ist ein Baum gemäß der Graphentheorie, bei dem jeder Knoten höchstens vom Grad 3 ist. Oft wird man auch fordern, dass sich die Nachfolgerknoten eindeutig in linke und rechte Knoten einteilen lassen. Ein Knoten mit höchstens Grad 2 kann dabei als Wurzel fungieren. Ein solcher Knoten existiert immer (im Extremfall ist er ein Blatt, hat also Grad 1).

Dendrogramme sind spezielle Darstellungen von Binärbäumen, die die Ähnlichkeit von Objekten wiedergeben und unter anderem in der Clusteranalyse eingesetzt werden.

Inhalt
1 Vollständiger Binärbaum
2 Vollständiger balancierter Binärbaum
3 Pythagoräischer Binärbaum

Vollständiger Binärbaum

Ein vollständiger Binärbaum hat zusätzlich die Eigenschaft, dass genau ein Knoten den Grad 2 besitzt. In diesem Fall wird nur dieser als Wurzel bezeichnet. Alle inneren Knoten haben einen Vorgänger (der in Anlehnung an die englische Bezeichnung parent auch als elter bezeichnet wird) und zwei Kinder, also Grad 3. Blätter haben Grad 1.

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

Pythagoräischer Binärbaum

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.

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


Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.