۰
subtitle
ارسال: #۱
سوالی از فصل درخت های ویژه ی کتاب پوران
ص۲۱۸ کتاب یوسفی
درخت های ویژه
==
توی کتاب پوران به آدرس صفحه ای که گفتم(کتاب چاپ ۸۹) اومده :
ثابت می شود که در ارتفاع 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 که توی سطح ۲ بود؟
درخت های ویژه
==
توی کتاب پوران به آدرس صفحه ای که گفتم(کتاب چاپ ۸۹) اومده :
ثابت می شود که در ارتفاع h هیپ حداکثر به تعداد {(n/{2^(h+1 گره وجود دارد.
====
حالا شما بگید چطوری می تونه جمله ی فوق صحیح باشه ؟
شما یه درخت کامل دودویی با ۴ گره رو فرض کنید. شکلشم اینا
حالا ما توی ارتفاع ۲(یعنی همین سطر دوم یا سطح ۲ یا level2 یا هرچی اسمشو میذارید) با توجه به اینکه تعداد گره ها یا n برابر ۴ هست و h=2 داریم:
این چه ربطی داشت به اون ۲ تا node که توی سطح ۲ بود؟
۲
ارسال: #۲
سوالی از فصل درخت های ویژه ی کتاب پوران
شما مفهوم ارتفاع رو درست متوجه نشدید. ارتفاع گره x برابر است با حداکثر تعداد یال‌ها در طولانی‌ترین مسیری که گره x رو به یک برگ متصل میکنه.
در همون شکلی که قرار دادید فرض کنید شماره سطوح از یک شروع میشه و گره‌ها رو از بالا به پایین و از چپ به راست با شروع از عدد یک شماره‌گذاری کردیم. ارتفاع گره شماره ۴ میشه ۰، ارتفاع گره ۳ میشه ۰، ارتفاع گره ۲ میشه ۱ و ارتفاع ریشه میشه ۲.
در همون شکلی که قرار دادید فرض کنید شماره سطوح از یک شروع میشه و گره‌ها رو از بالا به پایین و از چپ به راست با شروع از عدد یک شماره‌گذاری کردیم. ارتفاع گره شماره ۴ میشه ۰، ارتفاع گره ۳ میشه ۰، ارتفاع گره ۲ میشه ۱ و ارتفاع ریشه میشه ۲.
۲
ارسال: #۳
سوالی از فصل درخت های ویژه ی کتاب پوران
ارتفاع پایین سطح ترین برگ = ۰
ارتفاع پدر پایین سطح ترین برگ = ۱
ارتفاع پدر پدر پایین سطح ترین برگ = ۲
ارتفاع پدر پدر پدر پایین سطح ترین برگ = ۳
ارتفاع پدر پدر پدر پدر پایین سطح ترین برگ = ۴
...
ارتفاع ریشه میشه بیشترین ارتفاع از یک برگ تا ریشه.
و درنهایت ارتفاع درخت میشه ارتفاع ریشه.
-------------------------------------------------
حالا اینجا که گفته n/2^h+1 ، منظورش از اون h ارتفاع درخت هست.(توجه کن که کل عبارت حد بالا رو گرفته یعنی حاصل اون تقسیم حد بالا رو باید گرفت)، و همچنین باید توچه کرد که گفته "حداکثر" تعداد نودها در اون سطح. یعنی اگه مثلا تعداد نودها برابر با ۱۵ تا باشه، در سطح آخر حداکثر می تونیم ۸تا نود داشته باشیم. چون اگه ۱۵ رو تقسیم بر ۲به توان ۱ کنی (که میشه همون ۲) و حدبالا رو حساب کنی حاصل میشه ۸/
این تعریف ارتفاع مربوط به کتاب کرمن میشه، در کتابای دیگه ممکنه ارتفاع رو جور دیگه ای تعریف کرده باشن، اما این سوال منظورش همون تعریف ارتفاع در کتاب کرمن هست که در بالا توضیح دادم.
موفق باشی.
ارتفاع پدر پایین سطح ترین برگ = ۱
ارتفاع پدر پدر پایین سطح ترین برگ = ۲
ارتفاع پدر پدر پدر پایین سطح ترین برگ = ۳
ارتفاع پدر پدر پدر پدر پایین سطح ترین برگ = ۴
...
ارتفاع ریشه میشه بیشترین ارتفاع از یک برگ تا ریشه.
و درنهایت ارتفاع درخت میشه ارتفاع ریشه.
-------------------------------------------------
حالا اینجا که گفته n/2^h+1 ، منظورش از اون h ارتفاع درخت هست.(توجه کن که کل عبارت حد بالا رو گرفته یعنی حاصل اون تقسیم حد بالا رو باید گرفت)، و همچنین باید توچه کرد که گفته "حداکثر" تعداد نودها در اون سطح. یعنی اگه مثلا تعداد نودها برابر با ۱۵ تا باشه، در سطح آخر حداکثر می تونیم ۸تا نود داشته باشیم. چون اگه ۱۵ رو تقسیم بر ۲به توان ۱ کنی (که میشه همون ۲) و حدبالا رو حساب کنی حاصل میشه ۸/
این تعریف ارتفاع مربوط به کتاب کرمن میشه، در کتابای دیگه ممکنه ارتفاع رو جور دیگه ای تعریف کرده باشن، اما این سوال منظورش همون تعریف ارتفاع در کتاب کرمن هست که در بالا توضیح دادم.
موفق باشی.
۱
ارسال: #۴
سوالی از فصل درخت های ویژه ی کتاب پوران
۰
ارسال: #۵
سوالی از فصل درخت های ویژه ی کتاب پوران
پس اونی که من می گم عمق و سطح هست که از بالا به پایین شماه گذاری میشه ؟
ضمنا اگه اینطوری شما می گید از پایین به بالا ارتفاع رو شماره می ذاریم،پس باید گره ی ۲و ۳ که در یک ارتفاع هستند باید ارتفاعشون ۱ باشه (اگه فرض کنیم از صفر شماره گذاری کرده باشیم)
درسته ؟
ضمنا اگه اینطوری شما می گید از پایین به بالا ارتفاع رو شماره می ذاریم،پس باید گره ی ۲و ۳ که در یک ارتفاع هستند باید ارتفاعشون ۱ باشه (اگه فرض کنیم از صفر شماره گذاری کرده باشیم)
درسته ؟
ارسال: #۶
RE: سوالی از فصل درخت های ویژه ی کتاب پوران
(۲۲ آبان ۱۳۹۱ ۰۷:۳۰ ب.ظ)csharpisatechnology نوشته شده توسط: پس اونی که من می گم عمق و سطح هست که از بالا به پایین شماه گذاری میشه ؟
ضمنا اگه اینطوری شما می گید از پایین به بالا ارتفاع رو شماره می ذاریم،پس باید گره ی ۲و ۳ که در یک ارتفاع هستند باید ارتفاعشون ۱ باشه (اگه فرض کنیم از صفر شماره گذاری کرده باشیم)
درسته ؟
نگاه
از پایین درخت میگم:
۱-آیا بعد از گره ۴ یالی هست؟نه پس ارتفاع صفر میشه
۲-آیا بعد از گره ۳ یالی هست ؟نه پس ارتفاع ۰ میشه
۳- ایا بعد از گره ۲ یالی هست؟ بله ۱ یال هست پس ارتفاع میشه ا(یعنی اگر تو گره ۲ رو ریشه فرض کنی ارتفاعت می شه ۱ درسته؟)
۴-حالا گره ۱ که سمت راستش گره ۳ هست که از گره ۱ به ۳ ارتفاع میشه ۱(ارتفاع گره۱)وسمت چپ گره ۱ ارتفاع شده ۲ که ارتفاع ریشه(گره ۱) می شه ۲ درسته
۰
ارسال: #۷
سوالی از فصل درخت های ویژه ی کتاب پوران
۰
ارسال: #۸
سوالی از فصل درخت های ویژه ی کتاب پوران
منظورش اینه که در ارتفاع مثلا صفر که ریشه قرار دارد یک نود هست. در ارتفاع مثلا یک که فرزندان ریشه قرار دارد ۲ نود هست.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close