Reguläre binäre Bäume

Hat ein Baum genau einen Knoten vom Grad 2 und sonst nur Knoten vom Grad 1 oder 3, dann wird er regulärer binärer Baum genannt.
Die Knotenzahl in regulären binären Bäumen ist ungerade. Reguläre Bäume mit der Knotenzahl n haben (n+1)/2 Knoten vom Grad 1. Das Niveau eines Knotens ist sein Abstand von der Wurzel. Das maximale auftretende Niveau wird Höhe des Baumes genannt. Für reguläre binäre Wurzelbäume gibt es die verschiedensten Anwendungsmöglichkeiten, z.B. in der Informatik.