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

[Afshin_Zavar]

سلام؛

با n گره، حداکثر چند درخت AVL میتوان ساخت؟

[Microsoft.net]

فرمولش اینه :

با 1 نود 1 درخت avl میشه درست کرد با 2 نود 2 درخت. از 3 به بعد با فرمول1 + (n-2) + (n-1) یعنی با 3 نود 2+1+1=4 درخت میشه ساخت یا با 4 نود 4+2+1=7 درخت AVL میشه ساخت

[Afshin_Zavar]

سلام؛
مطمئنی؟ این فرمول که گفتی مال "حداقل تعداد نودهای AVL در ارتفاع h" هست ها !
n(h)=n(h-1)+n(h-2)+1

با توجه به فرمول شما، اگه ارتفاع درخت تهی رو 1- در نظربگیریم، با 5 گره، حداکثر چند درخت AVL میشه ساخت؟

[Microsoft.net]

با n گره اگه بخوای بدونی چندتا درخت دودویی متفاوت میشه درست کرد فرمولش دنباله اعداد کاتالان هست که همون ترکیب 2n از n تقسیم بر n+1 هست که اگه Avl رو بخوای باید مواردی که متوازن نیست رو ازش کم کنی فرمولی من تا حالا ندیدم در این مورد

[Afshin_Zavar]

سلام؛
من هم مثل شما فکر میکنم.
پارسال،سراسری 85، این رو سئوال داده بود... من هم گزینه ای رو که به عدد کاتالان نزدیک بود رو انتخاب کردم.

[Microsoft.net]

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