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

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