ارائه روش جدید برای تولید درختان دودویی تصادفی با توزیع یکنواخت

موضوع اصلی در این مقاله، ارائه روشی برای تولید درختان دودویی تصادفی با توزیع یکنواخت است. روش های موجود برای تولید درختان تصادفی دودویی از لحاظ مرتبه زمانی، حافظه مصرفی، عملیات پیش پردازشی و دیگر خصیصه ها با یکدیگر تفاوت دارند. در این مقاله با به کارگیری یک گرامر مستقل از متن به تولید رشته پرانتز های خوش فرم، به صورت تصادفی و با توزیع یکنواخت پرداخته شده است. نوآوری این مقاله در ارائه ی الگوریتمی جدید با زمان خطی جهت تولید درخت تصادفی با توزیع یکنواخت است که علاوه بر بهینه بودن زمان اجرای آن به دلیل استفاده از یک گرامر مستقل از متن غیر مبهم یکی از مسائل ترکیبیاتی مطرح شده در بحث تئوری گرامرهای مستقل از متن را نیز حل می کند. در روش پیشنهادی ابتدا با مفروض بودن n یک عبارت پرانتزی خوش فرم به طول 2n به صورت تصادفی با توزیع یکنواخت تولید می شود و سپس از روی آن می توان یک درخت دودویی متناظر با آن را ایجاد کرد. میزان مصرف حافظه الگوریتم پیشنهاد شده نیز از 2n تجاوز نمی کند که از این جنبه نیز بهینه محسوب می شود.

کلیدواژه ها:

درخت تصادفی ، توزیع یکنواخت ، عبارت پرانتزی خوش فرم