A characterization of digital search trees from the successful search viewpoint

AbstractThis paper studies the average complexity of digital search trees from the successful search point of view. The average value of the successful search is used to evaluate the search time for a given record, the number of comparisons to insert a record, etc. The average value, however, is rather a poor measure and the need for higher moments of the successful search is obvious. For example, the variance provides information on how well a digital tree is balanced; the third centralized moment is a measure of the skewness property of the distribution, etc. In this paper we concentrate on an open problem: how to evaluate all moments of the successful search in an asymmetric multiway digital search tree? We prove that the mth moment ESmn of the successful search Sn, where n is the number of stored records, satisfies ESmn/lnmn→ 1/hm1 as n → ∞, where h1 is the entropy of the alphabet. In particular, it is shown that the variance of Sn is var Sn=c ln n + O(1) for the asymmetric case, and var Sn=O(1) for the symmetric case. This paper completes a study undertaken by the author to characterize some digital trees such as regular tries, Patricia tries and digital search trees from the average viewpoint