Binärbaum

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

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