سلاممن الگوریتم ایجاد درخت دوردویی بهینه که توی کتاب قدسی به دو روش بازگشتی و پویا گفته شده رو نمیفهمم.کسی میتونه توضیح بده؟
درخت جستجوی دودویی بهینه به روش برنامه نویسی پویا:
اگر n کلید متمایز k[1]<k[2]<..<k[n] موجود باشد و احتمال آنکه k[i] را جستجو کنیم p[i] باشد درخت جستجوی دودویی بهینه درختی است که در آن Sigma(C[i]*P[i]) که در آن i=1 to n است مینیمم شود.
اگر A[i][j] همان مینیمم زمان جستجو برای BST با کلید های K[i] تا K[j] باشد و K[i]<=k[j] به ازای هر i,j
داریم: A[i][i]=P[i] چون فقط K[i] موجود است و یک مقایسه لازم دارد پس A[i][i]=1*P[i]=p[i]
لذا جواب ما a[1][n] است حال فرض کنید bst بهینه را یافته ایم و ریشه آن K[m] است بنا بر اصل بهینگی هر دو زیر درخت چپ و راست بهینه اند و داریم:
A[1][n]=A[1][m-1]+P[1]+P[2]+...+P[m-1]+P[m]+A[m+1][n]+P[m+1]+...P[n]=A[1][m-1]+A[m+1][n]+ Sigma(P[t]) t=1 to n
سبز: مینیمم زمان جستجو در زیر درخت چپ
قرمز:هر یک از نود های زیر درخت چپ را بخواهیم جستجو کنیم بخاطر مقایسه با ریشه یک مقایسه اضافی دارد.
مشکی:خود ریشه یک مقایسه نیاز دارد.
آبی پر رنگ: مانند سبز در مورد زیر درخت راست.
آبی کمرنگ:مانند قرمز
لذا فرمول کلی برابر است با:
A[1][n]= Min( A[i][m-1]+A[m+1][j]+ Sigma(P[t]) t=i to j) and i<j
A[i][i]=P[i]
البته این رابطه فقط مقدار مینیمم را می دهد برای بدست آوردن خود درخت باید ماتریس دیگری برای ذخیره ریشه زیر درخت از K[i] تا K[j] بکار ببریم.
مرتبه الگوریتم ظاهرا O(n^3) است
ر.ک کتاب طراحی الگوریتم پوران پژوهش صفحه ۱۵۸ تا ۱۶۰
