Bäume

Ein Baum ist eine Sonderform der gerichteten Graphen. In einem Baum darf jeder Knoten nur einen Vorgänger haben. Somit darf von der Wurzel nur ein einziger Weg zu den Blättern führen.

Ein balancierter Baum ist ein Baum, indem der Tiefenunterschied aller Blätter maximal 1 beträgt.

Die Tiefe eines Knoten ist der Abstand (Anzahl der Kanten) von der Wurzel bis zum Knoten.

Ein Blatt ist ein Knoten, der keine Kindknoten hat.