IJPAM: Volume 80, No. 5 (2012)
Department of Statistics
Imam Khomeini International University
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