IJPAM: Volume 80, No. 5 (2012)

$(b,m)$-DIGITAL SEARCH TREES

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


Abstract. In this paper we study the $m$-ary digital search trees ($m\geq2$) with maximal bucket size $b~(\geq1)$. This model can be considered as a simultaneous extension of ordinary digital search trees (or $(1,2)$-digital search trees in our notation). We construct this model by using strings over an alphabet leading to $m$-ary trees and staying strings in a node as long as its capacity remains less than $b$. We obtain the exact formulas for the mean of the profiles of nodes in symmetric case. Also we discuss on asymptotic of mean in asymmetric case. Our analysis for $b=1$ and $m=2$ reduce to the previous analysis on ordinary digital search trees.

Received: July 8, 2012

AMS Subject Classification: 05C05

Key Words and Phrases: $(b,m)$-digital search trees, 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: 5