زمان کنونی: ۲۳ آذر ۱۳۹۸, ۰۷:۳۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

محاسبه ارتفاع درخت....

ارسال:
  

baharkhanoom پرسیده:

محاسبه ارتفاع درخت....

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

۱
ارسال:
  

Pure Liveliness پاسخ داده:

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 در مبانی ۱۰/۷ مقدار بیشتری هست و بلند ترین مسیر درخت از ریشه تا دورترین برگ هست که میشه ارتفاع درخت.

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

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

ارسال:
  

hamid_p پاسخ داده:

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 تایی رو بمون بدن که پر باشه و حداقل و حداکثر ارتفاع رو بخوان چطور باید حساب کرد؟
اگه درخت پر نباشه فکر نمیکنم راهی باشه برای محاسبه ارتفاع درسته؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۴۳,۰۲۸ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۲ ۸۴۲ ۰۷ مهر ۱۳۹۸ ۰۶:۴۵ ب.ظ
آخرین ارسال: hamzadebaroon
  محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس gnulinux ۰ ۱۶۱ ۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ
آخرین ارسال: gnulinux
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲۵۷ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  سطح و عمق و ارتفاع درخت remove ۵ ۴,۵۵۳ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi
  الگوریتم درخت porseshgar ۰ ۱۹۹ ۱۷ بهمن ۱۳۹۷ ۱۲:۲۴ ب.ظ
آخرین ارسال: porseshgar
Question رسم درخت با ۲۶ گره و ارتفاع کمینه porseshgar ۰ ۳۰۸ ۱۶ بهمن ۱۳۹۷ ۱۲:۱۱ ب.ظ
آخرین ارسال: porseshgar
  روش به طرح درخت پیش ترتیب با آرایش داده شده porseshgar ۶ ۱,۱۳۸ ۱۴ بهمن ۱۳۹۷ ۰۸:۴۰ ب.ظ
آخرین ارسال: porseshgar
  تست در مورد درخت Sanazzz ۲ ۴۴۳ ۰۴ بهمن ۱۳۹۷ ۰۶:۴۰ ب.ظ
آخرین ارسال: Sanazzz
  تقسیم برای محاسبه کد افزونه چرخشی (CRC) Sanazzz ۴ ۸۰۹ ۲۰ آذر ۱۳۹۷ ۰۱:۱۸ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close