Binärbaum

Ein Binärbaum ist ein Baum gemäß der Graphentheorie, bei dem jeder Knoten höchstens vom Grad 3 ist. 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).

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.

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 z.B. binäre Suchbäume, AVL-Bäume und binäre Heaps basieren auf Binärbäumen.