RT - Journal Article
T1 - Study of Random Biased d-ary Tries Model
JF - khu-mmr
YR - 2016
JO - khu-mmr
VO - 2
IS - 2
UR - http://mmr.khu.ac.ir/article-1-2584-en.html
SP - 39
EP - 50
K1 - d-ary tries
K1 - profile
K1 - height
K1 - depth.
AB - Tries are the most popular data structure on strings. We can construct d-ary tries by using strings over an alphabet leading to d-ary tries. Throughout the paper we assume that strings stored in trie are generated by an appropriate memory less source. In this paper, with a special combinatorial approach we extend their analysis for average profiles to d-ary tries. We use this combinatorial approach for studying of average profile, since its probability distribution is unknown. We obtain the probability distribution of depth and the distribution function of height as n is large. These results follow from the study of certain recurrence equations that we solve by a analytic method.
LA eng
UL http://mmr.khu.ac.ir/article-1-2584-en.html
M3 10.29252/mmr.2.2.39
ER -