ص۲۱۸ کتاب یوسفی
درخت های ویژه
==
توی کتاب پوران به آدرس صفحه ای که گفتم(کتاب چاپ ۸۹) اومده :
ثابت می شود که در ارتفاع h هیپ حداکثر به تعداد {(n/{2^(h+1 گره وجود دارد.
====
حالا شما بگید چطوری می تونه جمله ی فوق صحیح باشه ؟
شما یه درخت کامل دودویی با ۴ گره رو فرض کنید. شکلشم اینا
![[تصویر: 141842_1_1379088121.gif]](https://img.manesht.ir/141842_1_1379088121.gif)
حالا ما توی ارتفاع ۲(یعنی همین سطر دوم یا سطح ۲ یا level2 یا هرچی اسمشو میذارید) با توجه به اینکه تعداد گره ها یا n برابر ۴ هست و h=2 داریم:
![[تصویر: 141842_2_1379088121.gif]](https://img.manesht.ir/141842_2_1379088121.gif)
این چه ربطی داشت به اون ۲ تا node که توی سطح ۲ بود؟
شما مفهوم ارتفاع رو درست متوجه نشدید. ارتفاع گره x برابر است با حداکثر تعداد یال‌ها در طولانی‌ترین مسیری که گره x رو به یک برگ متصل میکنه.
در همون شکلی که قرار دادید فرض کنید شماره سطوح از یک شروع میشه و گره‌ها رو از بالا به پایین و از چپ به راست با شروع از عدد یک شماره‌گذاری کردیم. ارتفاع گره شماره ۴ میشه ۰، ارتفاع گره ۳ میشه ۰، ارتفاع گره ۲ میشه ۱ و ارتفاع ریشه میشه ۲.
پس اونی که من می گم عمق و سطح هست که از بالا به پایین شماه گذاری میشه ؟
ضمنا اگه اینطوری شما می گید از پایین به بالا ارتفاع رو شماره می ذاریم،پس باید گره ی ۲و ۳ که در یک ارتفاع هستند باید ارتفاعشون ۱ باشه (اگه فرض کنیم از صفر شماره گذاری کرده باشیم)
درسته ؟
(۲۲ آبان ۱۳۹۱ ۰۷:۳۰ ب.ظ)csharpisatechnology نوشته شده توسط: درسته ؟نه. ارتفاع گره ۳ برابر با صفر هستش نه یک
(۲۲ آبان ۱۳۹۱ ۰۷:۳۰ ب.ظ)csharpisatechnology نوشته شده توسط: پس اونی که من می گم عمق و سطح هست که از بالا به پایین شماه گذاری میشه ؟
ضمنا اگه اینطوری شما می گید از پایین به بالا ارتفاع رو شماره می ذاریم،پس باید گره ی ۲و ۳ که در یک ارتفاع هستند باید ارتفاعشون ۱ باشه (اگه فرض کنیم از صفر شماره گذاری کرده باشیم)
درسته ؟
نگاه
از پایین درخت میگم:
۱-آیا بعد از گره ۴ یالی هست؟نه پس ارتفاع صفر میشه
۲-آیا بعد از گره ۳ یالی هست ؟نه پس ارتفاع ۰ میشه
۳- ایا بعد از گره ۲ یالی هست؟ بله ۱ یال هست پس ارتفاع میشه ا(یعنی اگر تو گره ۲ رو ریشه فرض کنی ارتفاعت می شه ۱ درسته؟)
۴-حالا گره ۱ که سمت راستش گره ۳ هست که از گره ۱ به ۳ ارتفاع میشه ۱(ارتفاع گره۱)وسمت چپ گره ۱ ارتفاع شده ۲ که ارتفاع ریشه(گره ۱) می شه ۲ درسته
منظورش اینه که در ارتفاع مثلا صفر که ریشه قرار دارد یک نود هست. در ارتفاع مثلا یک که فرزندان ریشه قرار دارد ۲ نود هست.
(۰۷ آذر ۱۳۹۱ ۰۴:۵۲ ب.ظ)sufia_lido نوشته شده توسط: منظورش اینه که در ارتفاع مثلا صفر که ریشه قرار دارد یک نود هست. در ارتفاع مثلا یک که فرزندان ریشه قرار دارد ۲ نود هست.کاملاً غلطه
ارتفاع پایین سطح ترین برگ = ۰
ارتفاع پدر پایین سطح ترین برگ = ۱
ارتفاع پدر پدر پایین سطح ترین برگ = ۲
ارتفاع پدر پدر پدر پایین سطح ترین برگ = ۳
ارتفاع پدر پدر پدر پدر پایین سطح ترین برگ = ۴
...
ارتفاع ریشه میشه بیشترین ارتفاع از یک برگ تا ریشه.
و درنهایت ارتفاع درخت میشه ارتفاع ریشه.
-------------------------------------------------
حالا اینجا که گفته n/2^h+1 ، منظورش از اون h ارتفاع درخت هست.(توجه کن که کل عبارت حد بالا رو گرفته یعنی حاصل اون تقسیم حد بالا رو باید گرفت)، و همچنین باید توچه کرد که گفته "حداکثر" تعداد نودها در اون سطح. یعنی اگه مثلا تعداد نودها برابر با ۱۵ تا باشه، در سطح آخر حداکثر می تونیم ۸تا نود داشته باشیم. چون اگه ۱۵ رو تقسیم بر ۲به توان ۱ کنی (که میشه همون ۲) و حدبالا رو حساب کنی حاصل میشه ۸/
این تعریف ارتفاع مربوط به کتاب کرمن میشه، در کتابای دیگه ممکنه ارتفاع رو جور دیگه ای تعریف کرده باشن، اما این سوال منظورش همون تعریف ارتفاع در کتاب کرمن هست که در بالا توضیح دادم.
موفق باشی.