تالار گفتمان مانشت
ارتفاع هرم - نسخه‌ی قابل چاپ

ارتفاع هرم - Hopegod - 10 آذر ۱۳۹۵ ۰۱:۳۹ ب.ظ

سلام دوستان بر طبق سوال زیر
[attachment=20941]
و جوابش
[attachment=20942]
میخاستم بپرسم که چرا گفته ارتفاع زیردرخت چپ h-1 و زیر درخت راست h-2؟

RE: ارتفاع هرم - delete4all - 10 آذر ۱۳۹۵ ۰۲:۲۵ ب.ظ

سلام
طبق گفته ارتفاع درخت h هست که اینجا h=4 هست و ارتفاع زیر درخت چپ رو گفته h-1 که اینجا ارتفاع زیر درخت چپ میشه h-1=3 و زیر درخت راست هم گفته h-2 که میشه h-2=2
و حداکثر گره های زیر درخت چپ هم گفته ۲n/3 که اینجا میشه ۲۲/۳=۷ که تعداد گره های زیر شاخه چپ رو اگه بشمارید میشه ۷

RE: ارتفاع هرم - Jooybari - 10 آذر ۱۳۹۵ ۰۳:۵۵ ب.ظ

سلام. وقت بخیر.
به جواب کتاب توجه نکنید. به نظرم خواسته با استفاده از یه نکته (که حالت بهینه نیست) یه تست طرح کنه. با فرض اینکه اندیس اولین عنصر هرم برابر ۱ باشه، اندیس والد گره i ام برابر [i/2] میشه. (منظور جزء صحیحه) ارتفاع والد هر گره هم یکی بیشتر از ارتفاع اون گره هست و گزینه ۳ با استفاده از رابطه برابری درسته. یعنی نیاز به بزرگتر مساوی نیست. درصورتی که اندیس ریشه برابر ۰ باشه اون موقع باید از بزرگتر مساوی استفاده بشه که باز هم گزینه ۳ درسته.
اگه بگیم گزینه ۲ غلط نیست خوب میتونیم بگیم ۴ هم علط نیست. چون یه شرط راحت تری نسبت به ۳ دارن.

RE: ارتفاع هرم - Hopegod - 10 آذر ۱۳۹۵ ۰۶:۰۹ ب.ظ

خیلی ممنونم دوستان . مرسی.