IJPAM: Volume 80, No. 1 (2012)

ON AVERAGE PROFILE OF
THE BINARY BUCKET DIGITAL SEARCH TREES

Ramin Kazemi
Department of Statistics
Imam Khomeini International University
Qazvin, IRAN


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 ($b$-DSTs) where each node can hold up to $b$ keys. The construction rule of $b$-DSTs is the same as DSTs, except that keys keep staying in a node as long as its capacity remains less than $b$. 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 $b$-DSTs. We show that the asymptotic results are independent of $b$ 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 $b$.

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
Year: 2012
Volume: 80
Issue: 1