موضوع مقاله: درخت دودویی جستجوی بهینه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت دودویی جستجوی بهینه | مقدمه: درخت دودویی جستجو یک داده ساختار مناسب برای پیاده‌سازی فرهنگ‌های داده‌ای است که برای فرهنگی با n عنصر، اعمال درج، حذف و جستجو را با میانگین (O(lg n ولی با هزینه حداکثر (O(n انجام می‌دهد. | ## بخش 1: درخت دودویی جستجوی بهینه | درصورتی که از قبل بدانیم دقیقاً چه عناصری قرار است در درخت درج شود و درضمن احتمال آن که هر کدام از این عناصر مورد جستجو قرار گیرند را بدانیم می‌توانیم شکل بهینه تری از درخت دودویی جستجو را تشکیل دهیم. در مجموع دو روش برای بهینه تر کردن درخت دودویی جستجو وجود دارد، یکی ایجاد یک درخت دودویی جستجوی متوازن و دیگری ایجاد درخت دودویی جستجوی بهینه با محاسبه احتمال دسترسی به هر کدام از عناصر. درخت دودویی جستجوی متوازن اگر داده‌ها از پیش آماده باشند، می‌توانیم آن‌ها را به گونه ای در درخت دو دویی جستجو قرار دهیم تا درختی متوازن ایجاد شود. در چنین شرایطی، یعنی با داشتن یک درخت دودویی جستجو که متوازن نیز هست هر کدام از اعمال فرهنگ داده ای در بدترین حالت نیز با (O(lg n انجام می‌شوند. ساخت درخت دودوی جستجوی متوازن برای ساخت این درخت فرض کردیم که از قبل می‌دانیم دقیقاً چه عناصری قرار است در این درخت قرار گیرند و داده‌ای در میان کار به این داده‌ها اضافه نمی‌شود. با این کار طبق ویژگی‌های درخت دودویی جستجو، نیمی از عناصر در زیر درخت سمت راست و نیمه دیگر در زیر درخت سمت چپ قرار می‌گیرد. | ## بخش 2: درخت دودویی جستجوی بهینه | همین روند را به صورت بازگشتی برای زیر درخت‌های راست و چپ (داده‌های نیمه سمت راست عنصر میانه و داده‌های نیمه سمت چپ میانه) انجام می‌دهیم. درخت دودویی جستجوی بهینه یک درخت دودویی جستجو را در نظر بگیرید که عملیات جستجو در آن اصلی‌ترین عمل مورد نیاز است و همچنین تعداد تقاضاها برای جستجوی هرکدام از عناصر این درخت با یکدیگر تفاوت قابل ملاحظه ای دارد. با توجه به این که زمان انجام عمل جستجو برای یک عنصر متناسب با عمق آن در درخت دودویی جستجو است، در صورتی که بتوانیم عناصری که بیشتر مورد تقاضا قرار می‌گیرند و احتمال جستجو شدن برای آن‌ها بیشتر است به ریشه نزدیک تر کنیم و در واقع پر جستجوترین عنصر را در ریشه قرار دهیم، میانگین زمان جستجو را حتی از حالت متوازن نیز کم‌تر کرده‌ایم. ساخت درخت دودویی جستجوی بهینه [P[i را برابر با احتمال جستجوی [a[i (جستجوی موفق ) در نظر بگیرید. با داشتن این احتمال‌ها می‌خواهیم یک درخت دودویی جستجو تشکیل دهیم به صورتی که میانگین زمان جستجو ( اعم از موفق یا نا موفق ) کمینه شود. در اینجا، زمان جستجو برای مقدار x را تعداد مقایسه‌های بین x و کلیدهای درخت دودویی جستجو تعریف می‌کنیم. | ## بخش 3: درخت دودویی جستجوی بهینه | اگر جستجو ناموفق باشد، بسته به مقدار x، الگوریتم جستجو در یکی از اشاره گرهای null متوقف می‌شود. اگر ak ریشه درخت باشد در این صورت [Ck[i,j را هزینه بهینه این درخت تعریف می‌کنیم. با همین استدلال مقدار هزینه زیر درخت سمت راست برابر با مجموع [C[k,j و [w[k,j خواهد بود. بنابر این: و در نتیجه: اگر بخواهیم برای ساخت این درخت از روش بازگشتی استفاده کنیم تعداد زیادی زیر مسئله تکراری خواهیم داشت؛ یعنی ممکن است یک زیر مسئله خاص را چندین بار در مراحل مختلف حل کنیم. روش بازگشتی در واقع همه درخت‌های دودویی جستجویی که با این n عنصر می‌توان ساخت (همان عدد کاتالان) را در نظر می‌گیرد و بین آن‌ها بهینه را تشخیص می‌دهد. | ## جمع‌بندی | راه حلپویا در صورتی که هر زیر مسئله را فقط یک بار حل کنیم و حاصل آن را در جایی ذخیره کنیم، برای حل زیر مسئله بزرگتر نیازی به فراخوانی مجدد زیر مسئله‌های کوچکتر نیست چون قبلاً حل شده اند و پاسخ آن‌ها را به صورت ذخیره شده در جایی داریم و این جواب‌ها مجدداً قابل استفاده هستند.