چندmin-heap می توان با ۷ گره با کلید های ۱ تا ۷ ساخت؟
سلام قبلا اینجا سوال شده با چند روش توضیح داده شده
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ولی اینجا باز یه کم جزئی تر توضیح میدم . ببین باید توجه کنیم چون درخ min-heap هستش پس حتما کوچکترین داده توی ریشه قرار میگیره خب ما ۱ رو توی ریشه قرار میدیم و برای بقیه حالات باید تعداد رو محاسبه کنیم ، اگر یه کم دقت کنیم پی میبریم که تنها اعدادی که میتونن توی سطح دوم قرار بگیرن تا درخت شرط min-heap بودن خودش رو داشته باشه تنها اعداد { {۲و۳} {۲و۴} {۲و۵} } هستن که باید تعداد حالت ها رو وقتی این اعداد توی سطح قرار میگیرن حساب کنیم :
حالت اول ۱ ریشه و {۲و۳} سطح دوم : خب میدونیم اگه ۲و۳ توی سطح دوم باشن خودشون دو حالت میتونن فرزند چپ یا راست ریشه باشن و واسه هر کدوم هم میتونیم از ۴ عدد باقی مانده ۴و۵و۶و۷ هر کدوم رو انتخاب کنیم و فرزند این دو قرار بدیم پس تعداد حالات میشه
[tex]2*4![/tex]
حالت دوم ۱ ریشه و {۲و۴} سطح دوم : باز خود این اعداد {۲و۴} مثل حالت قبل به دو طریق میتونن فرزند ریشه باشن و برای فرزندانشون ما حتما باید اول عدد ۳ رو به عنوان فرزند گره ۲ قرار بدین چون در غیر این صورت گره ۴ نمیتونه اونو به عنوان فرزند قبول کنه(شرط min-heap نقض میشه) پس ۳ رو به عنوان فرزند ۲ قرار میدیم حالا باید از اون سه عدد باقی مونده یعنی ۵و۶و۷ یکی رو انتخاب و به عنوان فرزند دیگر ۲ قرار بدیم که اینم میتونه به [tex]\binom{3}{1}[/tex] صورت بگیره و این فرزندان ۲ هم به دو حالت میتونن فرزند چپ یا راست ۲ باشن. برای گره ۴ هم باید از این ۳ عدد باز ۲ تا رو انتخاب و فرزند چپ یا راستش قرار بدیم که این میتونه به [tex]\binom{3}{2}[/tex] قرار بگیره پس کلا این حالت میشه
[tex]2*\left \{ 2!*\binom{3}{1} 2!*\binom{3}{2} \right \}[/tex]
حالت سوم ۱ ریشه و {۲و۵} سطح دوم : باز خود این اعدا {۲و۵} به دو طریق میتونن فرزند ریشه باشن
این حالت یک حالت ویژه است که شمارش اونم راحت میکنه ببین فرزندان ۵ حتما باید ۶و۷ بشان که شرط برقرار باشه و برای ۲ هم میدونیم که یه فرزندش مثل حالت قبل ۳ هستش و یه فرزند دیگشم فقط ۴ میمونه حالا هر یکی از این فرزندان ۲و۵ هم میوتنن به دوحالت چپ یا راست باشن که میشه :
[tex]2*\left \{ 2 2 \right \}[/tex]
و در مجموع هم کل این حالات رو جمع کنیم
[tex]\left [ \left \{ 2!*4! \right \} \left \{ 2*(2!*\binom{3}{1} 2!*\binom{3}{2}) \right \} \left \{ 2*(2 2) \right \}\right ] = 80[/tex]
سلام
واقعا ممنونم بابت جواب کاملتون
