Title :
On the Height of Height-Balanced Trees
Author :
Luccio, Fabrizio ; Pagli, Linda
Author_Institution :
Istituto di Scienze dell´ Informazione, University of Pisa, Pisa, Italy.
Abstract :
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.
Keywords :
Binary search trees; Binary trees; Costs; Equations; Height-balanced tree; information storage and retrieval; search length; search tree; tree height;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1976.5009208
