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

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

ارسال:
  

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

۰
ارسال:
  

mohsentafresh پاسخ داده:

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

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

Blush
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۴۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۴ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۳ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  تعداد درخت فراگیر ss311 ۰ ۲,۰۵۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۷۹,۸۶۱ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس gnulinux ۰ ۲,۲۷۶ ۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ
آخرین ارسال: gnulinux
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲,۱۱۵ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  سطح و عمق و ارتفاع درخت remove ۵ ۱۰,۶۷۷ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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