Balancierter Baum

Ein balancierter Baum (englisch oft self-balancing tree) ist in der Informatik ein besonderer Baum, der eine maximale Höhe von ${\displaystyle c\cdot \log(n)}$ garantiert, wobei ${\displaystyle n}$ die Anzahl der Elemente im Baum angibt und ${\displaystyle c}$ eine von ${\displaystyle n}$ 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.