Thumbnail
Access Restriction
Subscribed

Author Drmota, Michael
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Binary search tree ♦ Average case analysis ♦ Generating functions ♦ Height ♦ Saturation level
Abstract It is shown that all centralized absolute moments $E|\textit{Hn}$ ™ $EHn|^{α}$ (α ≥ 0) of the height $\textit{Hn}$ of binary search trees of size $\textit{n}$ and of the saturation level $\textit{Hn}′$ are bounded. The methods used rely on the analysis of a $\textit{retarded}$ differential equation of the form $Φ′(\textit{u})$ = $™α^{™2}Φ(u/α)^{2}$ with α > 1. The method can also be extended to prove the same result for the height of $\textit{m}-ary$ search trees. Finally the limiting behaviour of the distribution of the height of binary search trees is precisely determined.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2003-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 50
Issue Number 3
Page Count 42
Starting Page 333
Ending Page 374


Open content in new tab

   Open content in new tab
Source: ACM Digital Library