سلام بچه ها خسته نباشین
سوال طراحی الگوریتم علوم کامپیوتر سال ۸۲ هست
جواب سوال رو هم دیدم ولی متاسفانه متوجه نشدم چرا a3 را به عنوان گره ریشه درنظر گرفته
ممنون میشم اگه کسی میدونه جواب بده
متشکر
عکس های صورت سوال و جواب رو گذاشتم :
سوال:
میخواهیم یک درخت دودویی جستجو با عنصر a6>...>a2>a1 بسازیم تا متوسط عمق عناصر در آن کمینه شود اگر Pi احتمال ai باشد متوسط عمق برابر سیگما ( ( Pi.depth(qi) ،
i از ۱تا۶ تعریف میشود اگر P1=2/7 و Pi=1/7 ، i=2,...6 باشد متوسط عمق درخت بهینه چقدر است؟ (عمق ریشه صفر فرض شود )
سلام.
تو این عکس خوب توضیح داده شده. شما اگه بقیه حالات رو امتحان کنید میبینید وقتی a3 در ریشه باشه متوسط عمق کمینه است. توی بقیه حالات یکی از aiها تو ارتفاع سه قرار میگیره که باعث میشه متوسط عمق کمینه نشه.
ممنون خیلیییی لطف کردین
