بررسي مدل تراي هاي d-d يي اريب تصادفي

Study of Random Biased d-ary Tries Mode

تراي ها عمومي ترين ساختار داده اي روي رشته ها هستند. با استفاده از رشته ها روي الفبايي كه منجر به توليد درخت هاي d-d يي مي شود، مي توان تراي هاي d-d يي ساخت. سراسر مقاله فرض مي كنيم كه رشته هاي ذخيره شده در تراي به وسيله منشا بي حافظه مناسب توليد مي شوند. در اين مقاله، تحليل ميانگين نمايه با روي كرد تركيبياتي خاصي به تراي هاي d-d يي توسيع داده مي شود. از اين رويكرد تركيبياتي براي بررسي ميانگين نمايه استفاده مي كنيم زيرا تابع احتمال آن نامعلوم است. تابع احتمال عمق و تابع توزيع ارتفاع را هنگامي كه n بزرگ است، به دست مي آوريم. اين نتايج از بررسي معادله هاي بازگشتي مشخصي كه آن ها را با روش تحليلي حل مي كنيم، به دست مي آيند.

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.