Balancierter Baum

Ein balancierter Baum ( oft self-balancing tree) ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von garantiert, wobei die Anzahl der Elemente im Baum angibt und eine von unabhängige Konstante ist. Manche Autoren rechnen auch Datenstrukturen dazu, die Vorkehrungen enthalten, dass die mittlere Höhe oder Pfadlänge bei jedem Baum logarithmisch bleibt.