دانشگاه زنجان، دانشکدۀ علوم، گروه آمار ، javanian@znu.ac.ir
چکیده: (2106 مشاهده)
تِرایها یکی از کاربردیترین ساختمان دادهها با ساختار درختی در علوم کامپیوتر هستند. تِرایها، دادههای رشتهای را در برگهای درخت ذخیره میکنند. یک نسخۀ تعمیم یافتۀ تِرای، موسوم به تِرای سطلی است که در آن هر برگ یا سطل، ظرفیت ذخیرۀ بیش از یک داده را دارد. تِرای تصادفی با تعریف یک قاعده رشد تصادفی برای تِرای حاصل میشود. تعداد گرههای هم نوع که در فاصلۀ یکسان از ریشۀ یک درخت ریشه دار هستند را نمایه نامند. بررسی نمایۀ یک درخت، اهمیت زیادی دارد. زیرا بسیاری از پارامترهای درخت ریشهدار را میتوان برحسب نمایۀ آن درخت بیان کرد. در این مقاله به بررسی مجانبی امیدریاضی، واریانس و توزیع حدی هر یک از دو نمایۀ سطلی و داخلی (تعداد گرههای سطلی یا برگ و تعداد گرههای داخلی یا غیربرگ که در فاصلۀ یکسان از ریشه هستند) در تِرای سطلی تصادفی میپردازیم، وقتی که تعداد دادههای ذخیره شده در تِرای افزایش یابد. امید ریاضی و واریانسهای هر دو نمایه شامل توابعی متناوب هستند و نشان میدهیم آن توابع متناوب ناصفرند که این نکته در مقاله مربوط به نمایه ترای معمولی، به اثبات نرسیده است. همچنین به بررسی مقدار مجانبی نسبت امید ریاضیهای دو نمایۀ سطلی و داخلی میپردازیم. روشهایی که برای حصول نتایج بهکار میبریم، براساس استفاده از پواسونی سازی، تبدیل ملین، معادلات بازگشتی، توابع مولد، تحلیل تکینی و روش نقطۀ زینی است.
نوع مطالعه:
علمی پژوهشی بنیادی |
موضوع مقاله:
آمار دریافت: 1396/5/15 | ویرایش نهایی: 1399/6/15 | پذیرش: 1397/8/7 | انتشار: 1398/11/8 | انتشار الکترونیک: 1398/11/8