[Home ] [Archive]   [ فارسی ]  
:: Search Submit Contact ::
:: Volume 2, Issue 2 (4-2016) ::
2016, 2(2): 39-50 Back to browse issues page
Study of Random Biased d-ary Tries Model
R Kazemi, H. Abdolahinohoji, S Norouzi
Abstract:   (1909 Views)

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. 

Keywords: d-ary tries, profile, height, depth.
Full-Text [PDF 456 kb]   (673 Downloads)    
Type of Study: S | Subject: alg
Received: 2017/01/16 | Revised: 2017/09/13 | Accepted: 2017/01/16 | Published: 2017/01/16 | ePublished: 2017/01/16
Add your comments about this article
Your username or Email:

CAPTCHA



XML   Persian Abstract   Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

kazemi R, abdolahinohoji H, norouzi S. Study of Random Biased d-ary Tries Model. Journal title 2016; 2 (2) :39-50
URL: http://mmr.khu.ac.ir/article-1-2584-en.html


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Volume 2, Issue 2 (4-2016) Back to browse issues page
پژوهش‌های ریاضی Mathematical Researches
Persian site map - English site map - Created in 0.09 seconds with 33 queries by YEKTAWEB 4553