سلام؛
با n گره، حداکثر چند درخت AVL میتوان ساخت؟
سلام؛
با n گره، حداکثر چند درخت AVL میتوان ساخت؟
فرمولش اینه :
با 1 نود 1 درخت avl میشه درست کرد با 2 نود 2 درخت. از 3 به بعد با فرمول1 + (n-2) + (n-1) یعنی با 3 نود 2+1+1=4 درخت میشه ساخت یا با 4 نود 4+2+1=7 درخت AVL میشه ساخت
سلام؛
مطمئنی؟ این فرمول که گفتی مال "حداقل تعداد نودهای AVL در ارتفاع h" هست ها !
n(h)=n(h-1)+n(h-2)+1
با توجه به فرمول شما، اگه ارتفاع درخت تهی رو 1- در نظربگیریم، با 5 گره، حداکثر چند درخت AVL میشه ساخت؟
با n گره اگه بخوای بدونی چندتا درخت دودویی متفاوت میشه درست کرد فرمولش دنباله اعداد کاتالان هست که همون ترکیب 2n از n تقسیم بر n+1 هست که اگه Avl رو بخوای باید مواردی که متوازن نیست رو ازش کم کنی فرمولی من تا حالا ندیدم در این مورد
سلام؛
من هم مثل شما فکر میکنم.
پارسال،سراسری 85، این رو سئوال داده بود... من هم گزینه ای رو که به عدد کاتالان نزدیک بود رو انتخاب کردم.
خوب البته از اعداد کاتالان کمتر باید باشه شاید تا حدود نصف کمتر
این فرمولا که گفتید همشون اشتباس.هیچ راهی نداره مگر اینکه درختا رو بکشی.