سوال اول
در چه زمانی (بهترین زمان) می توان با n کلید دلخواه، یک درخت AVL ایجاد کرد
n)o)
n^2)o)
nlogn)o)
logn)o)
سوال دوم
در چه زمانی (بهترین زمان) می توان با n کلید دلخواه، یک درخت max heap ایجاد کرد
logn)o)
n^2)o)
n)o)
logn)o)
سلام دوستان
هیچ کدام که جواب ندادید. من یک جواب تخمینی می دهم ببینید به نظرتان درست هست یا نه؟
سوال اول :
مرتبه ساخت درخت AVL با n عنصر :
ازا انجایی که درخت AVL درختی اختلاف زیر درخت های هر نود کمتر از ۲ است. اگر بتوانیم با n نود یک درخت کامل ایجاد کنیم خود به خود avl هم هست.
به نظرم اول عناصر مرتب کنیم و در یک ارایه درج کنیم
با این ارایه مرتب یک درخت جستجوی دودویی کامل ایجاد کنیم به این صورت که
وسط ارایه را ریشه می گیریم عنصر وسط عناصر سمت چپ به عنوان فرزند چپ ریشه و عنصر وسط عناصر سمت راست را به عنوان فرزند راست ریشه انتخاب می کنیم و همین کار را به صورت بازگشتی انجام دهیم تا تمام عناصر به درخت اضافه شوند.
t(n)=2*t(n/2)+1
مرتبه این کار: مرتب سازی (nlogn) - ایجاد درخت n - پس در کل nlogn
سوال دوم :
مرتبه ساخت درخت heap
در کتاب پوران نوشته بود که اگر عناصر را در ارایه درج کنیم و با شروع از اخرین گره میانی تا ریشه، هر گره را با بچه اش مقایسه کنیم و عنصر بزرگتر را در گره قرار بدهیم. تعداد مقایسه در هر نود دو عدد است و از انجایی که موقعیت اخرین گره میانی درخت در وسط ارایه قراردارد. و این کار را برای عنصر وسط تا عنصر یکم ارایه انجام بدهیم در کل ۲ * (n/2) تا مقایسه انجام میشه و درخت heap میشه. مرتبه الگوریتم n هست ولی نگفته بود بهترین حالت هم با حالت متوسط برابر یا نه.
مرتبه ساخت درخت heap
در کتاب پوران نوشته بود که اگر عناصر را در ارایه درج کنیم و با شروع از اخرین گره میانی تا ریشه، هر گره را با بچه اش مقایسه کنیم و عنصر بزرگتر را در گره قرار بدهیم. تعداد مقایسه در هر نود دو عدد است و از انجایی که موقعیت اخرین گره میانی درخت در وسط ارایه قراردارد. و این کار را برای عنصر وسط تا عنصر یکم ارایه انجام بدهیم در کل ۲ * (n/2) تا مقایسه انجام میشه و درخت heap میشه. مرتبه الگوریتم n هست ولی نگفته بود بهترین حالت هم با حالت متوسط برابر یا نه.