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

سوالتی در مورد درختAVL

ارسال:
  

si.mozhgan پرسیده:

سوالتی در مورد درختAVL

به طور کلی چند درخت متمایز avl با ارتفاع سه وجود دارد؟(پارسه آی تی-۱۰۰درصد اول)
۴
۶
۱۰
۱۵

(مرسی).

۶
ارسال:
  

mamat پاسخ داده:

تعداد درخت AVL

جوابش میشه ۱۵ چند روز پیش حلش کردم اما چون مانشت نمیومد بالا نشد بیام بگم.

تار ارتفاع دو درخت که ۳ کلید میتونه جا بگیره هیچ حالت خاص دیگه ای براش نمیتونه باشه.

حالات مختلف برای سطح سوم هست که چون درخت جستجوی دودویی هم هست میشه اینطور گفت که حالات مختلف وجود ۱ گره تا ۴ گره را بایئ بررسی کنیم.

پس میشه اینطور نوشت [tex]\binom{4}{1} \binom{4}{2} \binom{4}{3} \binom{4}{4}=4 6 4 1=15[/tex]

امیدوارم قابل فهم بوده باشه

۰
ارسال:
  

mamat پاسخ داده:

تعداد درخت AVL

اگه تو این سوال بخوایم همه حالات برای تعداد گره های متفاوت رو بدست بیاریم هیچکدوم از اون گزینه‌ها نمیتونه جواب باشه. یعنی جواب خیلی بزرگتر از این حرفا میشه. مثلا حالتهای مختلف بودن و نبودن یک گره را در نظر بگیدرید متوجه میشوید که چی میگم یعنی حالتهای مختلف بودن و نبودن گره‌ها تا رسیدن به یک درخت کاملا متوازن.
ولی اگه درخت متوازن با حداقل گره منظورش بوده و اونو در نظر بگیریم باز هم از گزینه های گذاشته شده نمیتونه جواب باشه.
یعنی میشه ۱۶ درخت متمایز با ارتفاع ۳ با حداقل گره‌ها در درخت AVL.(ارتفاع ریشه ۰ در نظر گرفته شده).
حتی فکر کنم به صورت بازگشتی هم بشه براش این فرمول رو در نظر گرفت. T(h)=2(T(h-1)*T(h-2)) , T(1)=2 , T(2)=4
البته نمیدونم درسته یا نه این به ذهنم رسید ولی میدونم که سوال صورتش به احتمال قوی ناقصه.

۰
ارسال:
  

si.mozhgan پاسخ داده:

تعداد درخت AVL

مرسی از جوابتون. منم باهاتون موافقم .

۰
ارسال:
  

si.mozhgan پاسخ داده:

تعداد درخت AVL

فکر میکنم منظور سوال مثل تست آی تی نود درخت متمایز از نظر توپولوژی منظورشه . اگه اینجوری باشه درخت متوازن در عمق سه می تونه یک گره‌، دو گره‌، سه گره یا چهار گره داشته باشه .



پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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