PDA

View Full Version : حداکثر چند تا درخت AVL میشه ساخت؟

Afshin_Zavar
سه شنبه 08 اسفند 1385, 12:59 قبل از ظهر
سلام؛

با n گره، حداکثر چند درخت AVL میتوان ساخت؟
Microsoft.net
سه شنبه 08 اسفند 1385, 03:30 قبل از ظهر
فرمولش اینه :

با 1 نود 1 درخت avl میشه درست کرد با 2 نود 2 درخت. از 3 به بعد با فرمول1 + (n-2) + (n-1) یعنی با 3 نود 2+1+1=4 درخت میشه ساخت یا با 4 نود 4+2+1=7 درخت AVL میشه ساخت
Afshin_Zavar
سه شنبه 08 اسفند 1385, 11:51 قبل از ظهر
سلام؛
مطمئنی؟ این فرمول که گفتی مال "حداقل تعداد نودهای AVL در ارتفاع h" هست ها !
n(h)=n(h-1)+n(h-2)+1

با توجه به فرمول شما، اگه ارتفاع درخت تهی رو 1- در نظربگیریم، با 5 گره، حداکثر چند درخت AVL میشه ساخت؟
Microsoft.net
یک شنبه 13 اسفند 1385, 01:40 قبل از ظهر
با n گره اگه بخوای بدونی چندتا درخت دودویی متفاوت میشه درست کرد فرمولش دنباله اعداد کاتالان هست که همون ترکیب 2n از n تقسیم بر n+1 هست که اگه Avl رو بخوای باید مواردی که متوازن نیست رو ازش کم کنی فرمولی من تا حالا ندیدم در این مورد
Afshin_Zavar
یک شنبه 13 اسفند 1385, 01:05 بعد از ظهر
سلام؛
من هم مثل شما فکر میکنم.
پارسال،سراسری 85، این رو سئوال داده بود... من هم گزینه ای رو که به عدد کاتالان نزدیک بود رو انتخاب کردم.
Microsoft.net
یک شنبه 13 اسفند 1385, 03:42 بعد از ظهر
خوب البته از اعداد کاتالان کمتر باید باشه شاید تا حدود نصف کمتر