A Random Binary Trees Generation Method
Saud M. Maghrabi · 2000
هناك نوعان من التوزيعات العشوائية والتي تستخدم على نطاق واسع ، هما: توزيع شجرة البحث الثنائية، والتوزيع المتماثل . بتحليل أداة الخوارزميات (الطرق ) التي حلت مشكلة إنشاء الأشجار الثنائية بشكل عشوائي ، وجد أنه من المحتمل أن يقوم إنجاز الخوارزمية باستعمال متوسط حالة إنجازها . يعطي متوسط حالة إنجاز الخوارزمية في الغالب انعكاسا مفيدا لمدى ملاءمة الخوارزمية أكثر مما يعطيه أسوأ حالات إنجازها ، أسوأ حالات وقت التنفيذ لأي خوارزمية يمثل مدى التعقيد في هذا الوقت ، ولكن متوسط الحالة لوقت التنفيذ يمثل تعقيدا متعدد الحدود في وقت . من مثل هذه الحالات، إذا رغب أحدنا في أن يقوم أداء خوارزمية على مجموعة مثالية من الأشجار المنتظمة من حيث الخواص المستعملة بإنشاء الأشجار بشكل عشوائي ، ومن أمثلة هذه الخواص خاصية العمق ، وكذلك من حيث السمات المؤثرة في وقت تنفيذ الخوارزمية . إن الهدف من هذا البحث هو تصميم وتطبيق خوارزمية لإنشاء الأشجار الثنائية بشكل عشوائي بحيث يعتمد تقويم أداء هذه الخوارزمية على متوسط حالة وقت التنفيذ. وتختلف هذه الخوارزمية عن التوزيعين المذكورين أعلاه : التوزيع المتماثل ، وتوزيع شجرة البحث الثنائي ، ولقد تمت دراسة وتحليل خوارزمية هذا البحث .