درخت دودویی جستجوی بهینه

درخت دودویی جستجوی بهینه یک نوع درخت دودویی جستجو است. درخت دودویی جستجو یک داده ساختار مناسب برای پیاده‌سازی فرهنگ‌های داده‌ای است که برای فرهنگی با n عنصر، اعمال درج، حذف و جستجو را با میانگین (O(lg n ولی با هزینه حداکثر (O(n انجام می‌دهد. درصورتی که از قبل بدانیم دقیقاً چه عناصری قرار است در درخت درج شود و درضمن احتمال آن که هر کدام از این عناصر مورد جستجو قرار گیرند را بدانیم می‌توانیم شکل بهینه تری از درخت دودویی جستجو را تشکیل دهیم. در مجموع دو روش برای بهینه تر کردن درخت دودویی جستجو وجود دارد، یکی ایجاد یک درخت دودویی جستجوی متوازن و دیگری ایجاد درخت دودویی جستجوی بهینه با محاسبه احتمال دسترسی به هر کدام از عناصر.

درخت دودویی جستجوی متوازن

اگر داده‌ها از پیش آماده باشند، می‌توانیم آن‌ها را به گونه ای در درخت دو دویی جستجو قرار دهیم تا درختی متوازن ایجاد شود. در چنین شرایطی، یعنی با داشتن یک درخت دودویی جستجو که متوازن نیز هست هر کدام از اعمال فرهنگ داده ای در بدترین حالت نیز با (O(lg n انجام می‌شوند.

ساخت درخت دودوی جستجوی متوازن

برای ساخت این درخت فرض کردیم که از قبل می‌دانیم دقیقاً چه عناصری قرار است در این درخت قرار گیرند و داده‌ای در میان کار به این داده‌ها اضافه نمی‌شود. ابتدا باید عنصر میانه را در ریشه درخت قرار داد. با این کار طبق ویژگی‌های درخت دودویی جستجو، نیمی از عناصر در زیر درخت سمت راست و نیمه دیگر در زیر درخت سمت چپ قرار می‌گیرد. همین روند را به صورت بازگشتی برای زیر درخت‌های راست و چپ (داده‌های نیمه سمت راست عنصر میانه و داده‌های نیمه سمت چپ میانه) انجام می‌دهیم. با این روش در نهایت یک درخت متوازن دودویی در اختیار خواهیم داشت.

درخت دودویی جستجوی بهینه

یک درخت دودویی جستجو را در نظر بگیرید که عملیات جستجو در آن اصلی‌ترین عمل مورد نیاز است و همچنین تعداد تقاضاها برای جستجوی هرکدام از عناصر این درخت با یکدیگر تفاوت قابل ملاحظه ای دارد. با توجه به این که زمان انجام عمل جستجو برای یک عنصر متناسب با عمق آن در درخت دودویی جستجو است، در صورتی که بتوانیم عناصری که بیشتر مورد تقاضا قرار می‌گیرند و احتمال جستجو شدن برای آن‌ها بیشتر است به ریشه نزدیک تر کنیم و در واقع پر جستجوترین عنصر را در ریشه قرار دهیم، میانگین زمان جستجو را حتی از حالت متوازن نیز کم‌تر کرده‌ایم. این روش ایده اصلی درخت دودویی جستجوی بهینه است.

ساخت درخت دودویی جستجوی بهینه

• [P[i را برابر با احتمال جستجوی [a[i (جستجوی موفق ) در نظر بگیرید.
• [q[i را برابر با احتمال جستجوی [b[i ( جستجوی ناموفق برای عنصر ai <x <ai+1 :x ) در نظر بگیرید.

با داشتن این احتمال‌ها می‌خواهیم یک درخت دودویی جستجو تشکیل دهیم به صورتی که میانگین زمان جستجو ( اعم از موفق یا نا موفق ) کمینه شود. در اینجا، زمان جستجو برای مقدار x را تعداد مقایسه‌های بین x و کلیدهای درخت دودویی جستجو تعریف می‌کنیم. در درخت دودویی جستجوی T جستجو برای عنصر ai به تعداد 1+(depth(ai مقایسه بین کلیدهای عناصر در T نیاز دارد. اگر جستجو ناموفق باشد، بسته به مقدار x، الگوریتم جستجو در یکی از اشاره گرهای null متوقف می‌شود. به عبارت دیگر به یکی از عناصر [b[i می‌رسد.

هم چنین می‌دانیم که مجموع احتمال‌های [P[i و [q[i باید برابر با ۱ شود.

راه حل بازگشتی

زیر مسئله [T[i,j درخت دودویی جستجوی بهینه برای عناصر ai+1 تا aj است که با در اختیار داشتن [q[i و [P[i+1 تا [P[j و [q[j ایجاد می‌شود.

بنابر این درخت اصلی مسئله مطابق با [T[0,n خواهد بود.

در این مسئله[C[i,j هزینه بهینه یا میانگین زمان جستجوی بهینه در [T[i,j است.

$C[i,j]=\sum _{r=i+1}^{j}p_{r}[1+depth(a_{r})]+\sum _{r=i}^{j}q_{r}[1+depth(b_{r})].$

[w[i,j مجموع احتمال‌ها در [T[i,j است.

[r[i,j شماره ریشه [T[i,j است.

برای ساختن [T[i,j ریشه آن را مشخص می‌کنیم. اگر ak ریشه درخت باشد در این صورت [Ck[i,j را هزینه بهینه این درخت تعریف می‌کنیم. اگر [a[k ریشه درخت باشد، عناصر [a[i+1 تا [a[k-1 با احتمال‌های [q[i و [p[i+1 تا [p[k-1 و [q[k-1 حتماً زیر درخت چپ را تشکیل می‌دهند. همچنین عناصر [a[k+1 تا [a[j با احتمال‌های [q[k و [p[k+1 تا [p[j و [q[j زیر درخت راست را تشکیل می‌دهند. بدیهی است برای آن که [T[i,j بهینه باشد، این دو زیر درخت نیز باید بهینه باشند. یعنی هزینه‌های زیر درخت‌های چپ و راست به ترتیب باید [C[i,k-1 و [C[k,j باشند.

پس با توجه به رابطه ای که برای هزینه در بالا گفتیم، هزینه زیر درخت [T[i,k-1 در درخت [T[i,j برابر با مجموع [C[i,k-1 و [w[i,k-1 خواهد بود. با همین استدلال مقدار هزینه زیر درخت سمت راست برابر با مجموع [C[k,j و [w[k,j خواهد بود.

بنابر این:

$Ck[i,j]=(C[j,k-1]+w[i,k-1])+(C[k,j]+w[k,j])+p_{k}.$

و در نتیجه:

$C[i,j]={\begin{cases}q_{i}\\min(i<k<j){C[i,k-1]+C[k,j]}+w[i,j]\end{cases}}$

اگر بخواهیم برای ساخت این درخت از روش بازگشتی استفاده کنیم تعداد زیادی زیر مسئله تکراری خواهیم داشت؛ یعنی ممکن است یک زیر مسئله خاص را چندین بار در مراحل مختلف حل کنیم. روش بازگشتی در واقع همه درخت‌های دودویی جستجویی که با این n عنصر می‌توان ساخت (همان عدد کاتالان) را در نظر می‌گیرد و بین آن‌ها بهینه را تشخیص می‌دهد. تعداد این درخت‌ها و در نتیجه زمان اجرای الگوریتم به صورت بازگشتی، نمایی است.

راه حلپویا

در صورتی که هر زیر مسئله را فقط یک بار حل کنیم و حاصل آن را در جایی ذخیره کنیم، برای حل زیر مسئله بزرگتر نیازی به فراخوانی مجدد زیر مسئله‌های کوچکتر نیست چون قبلاً حل شده اند و پاسخ آن‌ها را به صورت ذخیره شده در جایی داریم و این جواب‌ها مجدداً قابل استفاده هستند. این روش راه حل پویا برای حل این مسئله است. برای راه حل پویا ماتریس‌های r و w و C را تعریف می‌کنیم.

[C[0....n,0....n و [w[0....n,0....n و [r[0....n,0....n

و با رویه Make_OBST این ماتریس‌ها را پر می‌کنیم:

Make_OBST(p,q)
for i=0 to n
 do w[i,i] = qi
 C[i,i] = 0
for l=1 to n
 do for i=0 to n-l
  do j=i+1
  w[i,j] = w[i,j-1] + p[j] + q[j]
  C[i,j] = min {C[j,k-1]+C[k+1,j]} + w[i,j]
  suppose for k=m c[i,j] is minimum
  r[i,j] = a[m]

منابع

داده ساختارها و مبانی الگوریتم - دکتر محمد قدسی

پیوند به بیرون

• Optimal BST