درخت بازگشتی _ مهندسی کامپیوتر ۹۰ - نسخه‌ی قابل چاپ

درخت بازگشتی _ مهندسی کامپیوتر ۹۰ - majid10 - 09 آبان ۱۳۹۵ ۰۵:۵۷ ب.ظ سلام ، تو عکس زیر سوالمو مشخص کردم چرا تو این سوال گفته ارتفاع شاخه های وسط از بقیه شاخه ها (چپ وراست) بزرگتر است ؟؟ ولی معمولا تو سوالای مشابه همیشه یا شاخه چپی بزرگتره یا راستی یا با هم برابرند ؟؟ از کجا و چجوری تشخیص باید بدیم Sent from my Nexus 5 using Tapatalk

RE: درخت بازگشتی _ مهندسی کامپیوتر ۹۰ - Pure Liveliness - 09 آبان ۱۳۹۵ ۰۹:۳۷ ب.ظ [attachment=20747] سلام. توی این جا میبینیم که بالاخره توی اونی که قرمز کردم متغیر اول میرسه به ۱یعنی n/2^x میشه یک منتهی هنوز k همون k هست و تغییر نکرده. از اون به بعد رو با سبز نشون دادم که چه اتفاقی میفته. خب ارتفاع تا جایی که قرمز رنگ هست میشه log در پایه ی ۲ اما این ارتفاع درخت نیست و درخت همچنان ادامه داره تا k هم به یک برسه. با نارنجی نشون دادم. ارتفاع از سبز تا نارنجی هم میشه log در پایه ی ۴. پس ارتفاع درخت میشه جمع این دو تا اگه از شاخه ی راست حساب کنیم هم به همین نتیجه میرسیم. کلا وقتی که درخت بازگشت بر حسب بیش از یک متغیر هست باید تغییر همه ی متغیر ها و رسیدن همه شون به شرایط اولیه رو در نظر بگیریم. مثلا واسه مثال [tex]T(n)=T(\frac{n}{2})+T(\frac{n}{4})[/tex] رو در نظر بگیرید. شاخه ی سمت راست داره هر بار به ۴ تقسیم میشه تا برسه به [tex]T(1)[/tex] یعنی ارتفاعش میشه [tex]\log_4n[/tex] و شاخه ی سمت چپ هر بار داره به ۲ تقسیم میشه تا برسه به شرط اولیه که [tex]T(1)[/tex] باشه. توی سوالای دیگه ممکنه چیز دیگه باشه. یعنی ارتفاعش میشه [tex]\log_2n[/tex] اما در مورد شاخه های وسطی. هر گره توی شاخه های وسطی یا هر بار داره به ۲ تقسیم میشه یا گاهی به ۴. حداقل یه بار به ۴ تقسیم شده پس ارتفاعش از [tex]\log_2n[/tex] قطعا کمتر هست. حداقل یه بار هم به ۲ تقسیم شده پس ارتفاعش از [tex]\log_4n[/tex] بیشتر هست. یعنی ارتفاعش یه چیزی بین ارتفاع شاخه ی راست و چپش هست.