On the Height of Height-Balanced Trees

Height-balanced binary trees with height unbalances up to ¿ are investigated, and the asymptotic value of the height h of such trees is studied for an increasing number of nodes N. It is shown that, in the worst case, the asymptotic value of h is a logarithmic function of N: [h = K log N]n¿¿. Specifically, an upper bound for h can be posed as: h ¿ K1 log (N+2) - K2 for ¿ ¿ 3; and h ¿ K1 log (N+K2) - K3 for ¿ = 4. Less strict bounds are posed for ¿ ≫ 4.