IJPAM: Volume 80, No. 5 (2012)

Department of Statistics
Imam Khomeini International University
Qazvin, IRAN
Abstract. In this paper we study the -ary digital search trees (
)
with maximal bucket size
. This model can be considered
as a simultaneous extension of ordinary digital search trees (or
-digital search trees in our notation). We construct this
model by using strings over an alphabet leading to
-ary trees and staying strings in a node as long as
its capacity remains less than
.
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
and
reduce to the
previous analysis on ordinary digital search trees.
Received: July 8, 2012
AMS Subject Classification: 05C05
Key Words and Phrases: -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