Ausgeglichenheit

Ein Baum T ist in der Höhe ausgeglichen, wenn entweder T leer ist oder gilt, daß

| h(T₁) - h(T₂) | 1 und

sowohl T₁ als auch T₂ in der Höhe ausgeglichen sind.

Ein Baum T ist nach dem Gewicht ausgeglichen, wenn entweder T leer ist oder gilt, daß

| card(T₁) - card(T₂) | 1 und

sowohl T₁ als auch T₂ nach dem Gewicht ausgeglichen sind.

Wenn ein Baum T nach dem Gewicht ausgeglichen ist, so folgt daraus, daß er auch in der Höhe ausgeglichen ist.

Nach dem Satz von Adelson-Velsky und Landis gilt für einen in der Höhe ausgeglichenen Baum T:
log₂(n+1) h(T) 1.4404 log₂(n+2) - 0.3277

Somit sind Suchpfade im höhenausgeglichene Bäume niemals um mehr als 45% länger im Vergleich zum optimalen Fall.