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

صفحه‌ها: ۱ ۲
RE: درخت AVL چیه؟ - fe_atash - 25 بهمن ۱۳۹۰ ۰۷:۵۰ ق.ظ

کسی میدونه درج و حذف در درخت AVL به چه صورته؟
این سوال ۳۹ آی تی ۹۰ رو ببینید:

[تصویر:  attachment.php?aid=2707]


کلید ۱۵ رو خواسته در درخت درج کنه...من اومدم ۱۵ رو گذاشتم فرزند ۱۰ که کاره غلطی بود...ولی جوابش درست در اومد
چون در جواب تست در کتاب مدرسان گفته کلید ۱۵ رو فرزند چپ گره ۲۰ میگذاریم که درخت از حالت توازن خارج میشود پس درخت رو دوران میدیم..پس از دوران ۱۵ جای گره ۱۰ رو میگیره و گره ۱۰ میشه فرزند چپ ۱۵ و گره ۲۰ فرزند راستش
جواب هم میشه گزینه ۳

یعنی همیشه وقتی حالت درخت AVL بهم میخوره باید با دوران درستش کنیم؟اصلا چجوری دوران میدیم؟ و کلا برای حذف و درج در AVL به چه صورته چون تو مقسمی نگفته.

درخت AVL چیه؟ - atharrashno - 25 بهمن ۱۳۹۰ ۱۰:۴۷ ق.ظ

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

RE: درخت AVL چیه؟ - programmer1389 - 06 تیر ۱۳۹۱ ۱۰:۰۳ ق.ظ

(۲۵ بهمن ۱۳۹۰ ۰۷:۵۰ ق.ظ)fe_atash نوشته شده توسط:  کسی میدونه درج و حذف در درخت AVL به چه صورته؟
این سوال ۳۹ آی تی ۹۰ رو ببینید:

[تصویر:  attachment.php?aid=2707]


کلید ۱۵ رو خواسته در درخت درج کنه...من اومدم ۱۵ رو گذاشتم فرزند ۱۰ که کاره غلطی بود...ولی جوابش درست در اومد
چون در جواب تست در کتاب مدرسان گفته کلید ۱۵ رو فرزند چپ گره ۲۰ میگذاریم که درخت از حالت توازن خارج میشود پس درخت رو دوران میدیم..پس از دوران ۱۵ جای گره ۱۰ رو میگیره و گره ۱۰ میشه فرزند چپ ۱۵ و گره ۲۰ فرزند راستش
جواب هم میشه گزینه ۳

یعنی همیشه وقتی حالت درخت AVL بهم میخوره باید با دوران درستش کنیم؟اصلا چجوری دوران میدیم؟ و کلا برای حذف و درج در AVL به چه صورته چون تو مقسمی نگفته.

اگر چه که پست مال قبله اما گفتم جوابش رو همینجا بدم تا کسایی هم که این پست رو جستجو میکنن همین جا جوابشون رو بگیرن
اینکه ۱۵ فرزند راست ۲۰ میشه که کاملا مشخصه چون ۱۵ از ۱۰ بزرگتره پس باید از ۱۰ رد بشیم و به ۲۰ میرسیم که اونجا چون ۱۵ از ۲۰ کوچکتره فرزند چپ ۲۰ میشه حالا شروع میکنیم به برگشت از ۱۵ به سمت ریشه و اونجا هایی که ارتفاع گره سمت چپ و راست اختلافشون بیشتر از یکی میشه رو چرخش میدیم در اینجا ارتفاع گره سمت چپ ۱۰ صفر و ارتفاع گره سمت راستش ۲ است که اختلاف بیشتر از یکی میشه همون جور که میبینید شکل ان بصورت ۱۰ و سپس ۲۰ و سپس ۱۵ است که یک خط شکسته است پس یک دوبل چرخش خواهیم داشت اما روش سریع اینه که جای گره اخر یعنی ۱۵ رو با گره ای که دارای مشکل است عوض کنیم و گره ۱۰ رو فرزند اون قرار بدیم که همونجور که گفتید میشه
همیشه باید avl رو اگه حالتش به هم خورد مجددا با یکی از سه روش دوران به چپ به راست یا دوبل درستش کنیم وگرنه که avl نیست