IJPAM: Volume 80, No. 1 (2012)
THE BINARY BUCKET DIGITAL SEARCH TREES
Department of Statistics
Imam Khomeini International University
Abstract. Drmota and Szpankowski have studied the average profile in digital search trees (DST) [#!DS!#]. In this paper, we extend the same approach to bucket digital search trees (-DSTs) where each node can hold up to keys. The construction rule of -DSTs is the same as DSTs, except that keys keep staying in a node as long as its capacity remains less than . Here we apply an alternate but unified and shorter approach to the analysis of the expectation of two random variables (internal and external profiles) in -DSTs. We show that the asymptotic results are independent of and are quite equal to the average profile of ordinary digital search trees in spite of the partial differential equations arising here are of the order .
Received: May 8, 2012
AMS Subject Classification: 05C05
Key Words and Phrases: bucket digital search trees, external and internal profiles, average profiles
Download paper from here.
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395