۲
subtitle
ارسال: #۱
  
محاسبه ارتفاع درخت....
سلام دوستان. عرض تبریک سال نو
من توی ارتفاع حساب کردن انواع درخت ها مشکل دارم. یجااز log استفاده میشه ، یجا از [log]+ 1
انگار توی درختهای متفاوت (هیپ - دودویی ساده- ...) متفاوتن!!
واینکه بخای با استفاده از پارامترهای دیگه ارتفاع بدست بیاد . مثلا تعداد گره ها رو داشته باشیم
کلا این مدلیا..
کسی میتونه کمک کنه؟
من توی ارتفاع حساب کردن انواع درخت ها مشکل دارم. یجااز log استفاده میشه ، یجا از [log]+ 1
انگار توی درختهای متفاوت (هیپ - دودویی ساده- ...) متفاوتن!!
واینکه بخای با استفاده از پارامترهای دیگه ارتفاع بدست بیاد . مثلا تعداد گره ها رو داشته باشیم
کلا این مدلیا..
کسی میتونه کمک کنه؟
۲
ارسال: #۲
  
RE: محاسبه ارتفاع درخت....
(۱۲ فروردین ۱۳۹۵ ۱۲:۳۱ ق.ظ)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 در مبانی ۱۰/۷ مقدار بیشتری هست و بلند ترین مسیر درخت از ریشه تا دورترین برگ هست که میشه ارتفاع درخت.
راجع به داشتن تعداد گره ها، مثلا میگن فلان تعداد گره داریم، درخت پر بکشیم ارتفاع چند میشه، از اینا منظورتونه؟ اگه سوال خاصی رو در نظر داشتید، بذاریدش.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ارسال: #۳
  
RE: محاسبه ارتفاع درخت....
(۰۷ خرداد ۱۳۹۵ ۰۶:۲۱ ب.ظ)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 در مبانی ۱۰/۷ مقدار بیشتری هست و بلند ترین مسیر درخت از ریشه تا دورترین برگ هست که میشه ارتفاع درخت.
راجع به داشتن تعداد گره ها، مثلا میگن فلان تعداد گره داریم، درخت پر بکشیم ارتفاع چند میشه، از اینا منظورتونه؟ اگه سوال خاصی رو در نظر داشتید، بذاریدش.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر تعداد برگهای یه درخت m تایی رو بمون بدن که پر باشه و حداقل و حداکثر ارتفاع رو بخوان چطور باید حساب کرد؟
اگه درخت پر نباشه فکر نمیکنم راهی باشه برای محاسبه ارتفاع درسته؟
۰
ارسال: #۴
  
RE: محاسبه ارتفاع درخت....
(۱۲ فروردین ۱۳۹۵ ۱۲:۳۱ ق.ظ)baharkhanoom نوشته شده توسط: سلام دوستان. عرض تبریک سال نو
من توی ارتفاع حساب کردن انواع درخت ها مشکل دارم. یجااز log استفاده میشه ، یجا از [log]+ 1
انگار توی درختهای متفاوت (هیپ - دودویی ساده- ...) متفاوتن!!
واینکه بخای با استفاده از پارامترهای دیگه ارتفاع بدست بیاد . مثلا تعداد گره ها رو داشته باشیم
کلا این مدلیا..
کسی میتونه کمک کنه؟
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close