نمايۀ تِراي هاي سطلي

تِراي ها يكي از كاربردي ترين ساختمان داده ها با ساختار درختي در علوم كامپيوتر هستند. تِراي ها، داده هاي رشته اي را در برگ هاي درخت ذخيره مي كنند. يك نسخۀ تعميم يافتۀ تِراي، موسوم به تِراي سطلي است كه در آن هر برگ يا سطل، ظرفيت ذخيرۀ بيش از يك داده را دارد. تِراي تصادفي با تعريف يك قاعده رشد تصادفي براي تِراي حاصل مي شود. تعداد گره هاي هم نوع كه در فاصلۀ يك‌سان از ريشۀ يك درخت ريشه دار هستند را نمايه نامند. بررسي نمايۀ يك درخت، اهميت زيادي دارد. زيرا بسياري از پارامترهاي درخت ريشه دار را مي توان برحسب نمايۀ آن درخت بيان كرد. در اين مقاله به بررسي مجانبي اميدرياضي، واريانس و توزيع حدي هر يك از دو نمايۀ سطلي و داخلي (تعداد گره هاي سطلي يا برگ و تعداد گره هاي داخلي يا غيربرگ كه در فاصلۀ يك‌سان از ريشه هستند) در تِراي سطلي تصادفي مي پردازيم، وقتي كه تعداد داده هاي ذخيره شده در تِراي افزايش يابد. اميد رياضي و واريانس هاي هر دو نمايه شامل توابعي متناوب هستند و نشان مي‌دهيم آن توابع متناوب ناصفرند كه اين نكته در مقاله مربوط به نمايه تراي معمولي، به اثبات نرسيده است. هم‌چنين به بررسي مقدار مجانبي نسبت اميد رياضي هاي دو نمايۀ سطلي و داخلي مي پردازيم. روش هايي كه براي حصول نتايج به‌كار مي بريم، براساس استفاده از پواسوني سازي، تبديل ملين، معادلات بازگشتي، توابع مولد، تحليل تكيني و روش نقطۀ زيني است.