(۰۷ خرداد ۱۳۹۵ ۰۶:۲۱ ب.ظ)Pure Liveliness نوشته شده توسط:  

(12 فروردین ۱۳۹۵ ۱۲:۳۱ ق.ظ)baharkhanoom نوشته شده توسط:  سلام دوستان. عرض تبریک سال نو
من توی ارتفاع حساب کردن انواع درخت ها مشکل دارم. یجااز log استفاده میشه ، یجا از [log]+ 1
انگار توی درختهای متفاوت (هیپ - دودویی ساده- ...) متفاوتن!!
واینکه بخای با استفاده از پارامترهای دیگه ارتفاع بدست بیاد . مثلا تعداد گره ها رو داشته باشیم
کلا این مدلیا..
کسی میتونه کمک کنه؟

سلام. در حد تجربه ی خودم میگم.
log n+1? خب شاید چون بعضی کتابها ارتفاع رو از ۰ میشمرند و بعضی از ۱ شروع میکنند. در واقع اولین سطح(سطح ریشه) رو صفر یا یک در نظر میگیرن.
توی تمامی درخت ها بزرگترین ارتفاع میشه ارتفاع درختمون. بزرگترین ارتفاع اونی هست که دیرتر برسه به برگ های درخت. برگ ها هم معمولا (۱)f یا (f(2 و این ها هستن. که بهمون داده شده یا اگه داده نشده همون (۱)f در نظر می گیریم برگ ها رو. توی درختی که توی عکس هست، توی یه مسیر هر بار n بر ۵ تقسیم میشه، توی یک مسیر اما هر بار n بر ۱۰/۷ تقسیم میشه، توی مسیر های دیگه(مسیر های میانی که اون ها رو در نظر نمیگیریم به دلیلی که در ادامه میگم) یک بار به ۵ و یک بار به ۱۰/۷ پس ارتفاع توی این مسیر ها تا برگ ها یه چیزی بین ارتفاعِ تقسیم به ۵ و ارتفاعِ تقسیم به ۱۰/۷ هست. پس اینجا ارتفاع میشه logn در مبنای ۱۰/۷/ چون دیر تر به ریشه میرسه.
توی این جا می دونیم که توی مسیری که با قرمز مشخص کردم، داریم :
( f(n/5^k که k همون ارتفاع درخت هست. که k توی سطح ریشه برابر با ۰ هست. توی سطح بعدی ۱ و تا برسه به n
خب این باید به (۱)f برسه دیگه. یعنی:
n/5^k >= 1
پس:
n >= 5^k
logn >= k در مبانی ۵
پس: ارتفاع مسیر قرمز که همون k هست میشه : logn در مبانی ۵
توی این جا می دونیم که توی مسیری که با آبی مشخص کردم، داریم :
( f(n/(۱۰/۷)^k که k همون ارتفاع درخت هست. که k توی سطح ریشه برابر با ۰ هست. توی سطح بعدی ۱ و تا برسه به n
خب این باید به (۱)f برسه دیگه. یعنی:
n/(۱۰/۷)^k >= 1
پس:
n>= (10/7) ^k
logn >= k در مبانی ۱۰/۷
پس: ارتفاع مسیر آبی که همون k هست میشه : logn در مبانی ۱۰/۷


logn در مبانی ۱۰/۷ مقدار بیشتری هست و بلند ترین مسیر درخت از ریشه تا دورترین برگ هست که میشه ارتفاع درخت.

راجع به داشتن تعداد گره ها، مثلا میگن فلان تعداد گره داریم، درخت پر بکشیم ارتفاع چند میشه، از اینا منظورتونه؟ اگه سوال خاصی رو در نظر داشتید، بذاریدش.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۱۲ فروردین ۱۳۹۵ ۱۲:۳۱ ق.ظ)baharkhanoom نوشته شده توسط:  سلام دوستان. عرض تبریک سال نو
من توی ارتفاع حساب کردن انواع درخت ها مشکل دارم. یجااز log استفاده میشه ، یجا از [log]+ 1
انگار توی درختهای متفاوت (هیپ - دودویی ساده- ...) متفاوتن!!
واینکه بخای با استفاده از پارامترهای دیگه ارتفاع بدست بیاد . مثلا تعداد گره ها رو داشته باشیم
کلا این مدلیا..
کسی میتونه کمک کنه؟