An analytic approach to the height of binary search trees

An analytic approach to the height of binary search trees

0.00 Avg rating—0 Votes
Article ID: iaor2002421
Country: United States
Volume: 29
Issue: 1/2
Start Page Number: 89
End Page Number: 119
Publication Date: Jan 2001
Journal: Algorithmica
Authors:
Abstract:

By using analytic tools it is shown that the expected value of the height Hn of binary search trees of size n is asymptotically given by E(Hn) = c log(n) + O(log log(n)) and its variance by V(Hn) = O((log log(n))2), where c = 4.31107 .... The same bounds have been obtained by Devroye and Reed by completely different methods.

Reviews

Required fields are marked *. Your email address will not be published.