تالار گفتمان مانشت
سوالتی در مورد درختAVL - نسخه‌ی قابل چاپ

صفحه‌ها: ۱ ۲
سوالتی در مورد درختAVL - si.mozhgan - 01 بهمن ۱۳۹۰ ۰۱:۴۲ ب.ظ

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

(مرسی).

تعداد درخت AVL - mamat - 01 بهمن ۱۳۹۰ ۰۳:۰۹ ب.ظ

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

تعداد درخت AVL - si.mozhgan - 01 بهمن ۱۳۹۰ ۰۵:۲۷ ب.ظ

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

RE: تعداد درخت AVL - narges_r - 02 بهمن ۱۳۹۰ ۰۳:۵۶ ق.ظ

(۰۲ بهمن ۱۳۹۰ ۰۱:۰۰ ق.ظ)Masoud05 نوشته شده توسط:  چونکه درخت AVL کامله .....

ببخشید چرا درخت AVL کامل در نظر گرفتید؟!

RE: تعداد درخت AVL - Masoud05 - 02 بهمن ۱۳۹۰ ۱۰:۱۳ ق.ظ

(۰۲ بهمن ۱۳۹۰ ۰۳:۵۶ ق.ظ)narges_r نوشته شده توسط:  
(02 بهمن ۱۳۹۰ ۰۱:۰۰ ق.ظ)Masoud05 نوشته شده توسط:  چونکه درخت AVL کامله .....

ببخشید چرا درخت AVL کامل در نظر گرفتید؟!

بجای متوازن گفتم کامل . ارسالم رو پاک کردم.

تعداد درخت AVL - si.mozhgan - 02 بهمن ۱۳۹۰ ۰۲:۲۶ ب.ظ

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

درخت AVL چیه؟ - netsupport - 04 بهمن ۱۳۹۰ ۰۲:۴۸ ب.ظ

درخت AVL چیه و سوال زیر چجوری حل میشه؟
بطور کلی چند درخت AVL با ارتفاع ۳ وجود دارد؟

درخت AVL چیه؟ - narges_r - 04 بهمن ۱۳۹۰ ۰۴:۱۴ ب.ظ

درخت AVL درخت BST متوازنه
در مورد این سوال که پرسیدید قبلا بحث شده

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

بنظر سوال مشکل داره
باید تعداد وخود نودهارو هم ذکر میکرد
مثل سوالی که تو کنکور سال ۸۵ اومده!

RE: درخت AVL چیه؟ - shervinrs - 04 بهمن ۱۳۹۰ ۰۷:۰۴ ب.ظ

نقل قول: درخت AVL درخت BST متوازنه.
درخت زیر متوازن نیست، اما AVL هست. چون تعریف AVL میگه که درخت باید حداکثر ضریب توازن یک داشته باشه. که ضریب توازن رو هم اختلاف ارتفاع فرزندان چپ و راست تعریف میکنن.
اما توازن اختلاف سطح برگ هاست که نباید بیشتر از یک باشه.
درسته؟ یا من دارم اشتباه می کنم؟ Huh

[attachment=2544]

درخت AVL چیه؟ - mamat - 04 بهمن ۱۳۹۰ ۰۸:۱۶ ب.ظ

(۰۴ بهمن ۱۳۹۰ ۰۷:۰۴ ب.ظ)shervinrs نوشته شده توسط:  درخت زیر متوازن نیست، اما AVL هست.
تعریف درخت متوازن رو غلط برداشت کردید فکر کنم.
درخت AVL هم شرطی که داره اینه که کتوازن باشه و در ضمن خصوصیات BST بودن را حفظ کنه.
درخت متوازن دختی هست که اختلاف دو زیر درخت سمت چپ و راست هر گره حداکثر ۱ باشد.
اونی که شما میپید درخت کاملا متوازنه که تمام زیر درختها ارتفاعشون برابر باشه.
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ​ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ​ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ

در مورد سوال دوم هم باید سوالتون رو دقیقتر مطرح کنید تا جواب مناسب بگیرید.

RE: درخت AVL چیه؟ - shervinrs - 04 بهمن ۱۳۹۰ ۰۹:۰۰ ب.ظ

نقل قول: درخت متوازن دختی هست که اختلاف دو زیر درخت سمت چپ و راست هر گره حداکثر ۱ باشد.
اما در کتاب داده ساختارهای دکتر قدسی در ابتدای قسمت درخت‌ها (همه درخت ها، نه فقط درخت دودویی) گفته شده:
درخت متوازن درختی است که سطح برگ های آن حداکثر یک واحد با هم اختلاف داشته باشد.

همچنین تعریفی که شما از توازن آوردید در کتاب مقسمی (برای توضیح درخت AVL) تحت عنوان درخت BST با ارتفاع متوازن گفته شده.

درخت متوازن با درخت با ارتفاع متوازن فرق میکنه. درسته؟ و درخت BST با ارتفاع متوازن درخت AVL هست؟

نقل قول: اونی که شما میپید درخت کاملا متوازنه که تمام زیر درختها ارتفاعشون برابر باشه.
من صحبتی از برابر بودن نکردم.

درخت AVL چیه؟ - mfXpert - 04 بهمن ۱۳۹۰ ۰۹:۰۸ ب.ظ

یه درخت میتونه متوازن باشه اما AVL نباشه.عکس این موضوع هم صادق هستش.یعنی یه درخت میتونه AVL باشه ولی متوازن نباشه.

درخت AVL چیه؟ - narges_r - 04 بهمن ۱۳۹۰ ۰۹:۳۴ ب.ظ

تعریفی که من از AVL دادم دقیقا تعریفی هست که هم تو کتاب پوران اقای یوسفی اومده هم تو ساختمان پارسه اقای طورانی!

(۰۴ بهمن ۱۳۹۰ ۰۹:۰۸ ب.ظ)mfXpert نوشته شده توسط:  یه درخت میتونه AVL باشه ولی متوازن نباشه.

فکر میکنم AVL باید متوازن باشه!
میشه بیشتر توضیح بدید

درخت AVL چیه؟ - mamat - 04 بهمن ۱۳۹۰ ۱۰:۳۶ ب.ظ

(۰۴ بهمن ۱۳۹۰ ۰۹:۰۰ ب.ظ)shervinrs نوشته شده توسط:  درخت متوازن با درخت با ارتفاع متوازن فرق میکنه.
منظور من هم ارتفاع متوازن بود یکم بد گفتم شاید.

(۰۴ بهمن ۱۳۹۰ ۰۹:۰۰ ب.ظ)shervinrs نوشته شده توسط:  اما در کتاب داده ساختارهای دکتر قدسی در ابتدای قسمت درخت‌ها (همه درخت ها، نه فقط درخت دودویی) گفته شده:
درخت متوازن درختی است که سطح برگ های آن حداکثر یک واحد با هم اختلاف داشته باشد.

کتاب داده ساختارهای دکتر قدسی صفحه ۴۲۹ تعریف درخت AVL:
تعریف ۱-۷ ---> "درخت ای وی ال درخت جستجوی دودویی است که اختلاف ارتفاع های دو زیر درخت هر گره آن حداکثر یک واحد باشد."

صفحه ۱۸۲ از کتاب داده ساختارهای دکتر قدسی:
درخت متوازن‌: "درختی که سطح برگهای آن حداکثر یک واحد با هم اختلاف داشته باشند."
درخت کاملا متوازن‌: "درختی که سطح برگهای آن با هم برابر باشند."

تعداد درخت AVL - mamat - 16 بهمن ۱۳۹۰ ۰۳:۵۱ ب.ظ

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

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

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

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

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