سلام.ببخشید اینبار سوال نیست راستش یه تاپیک درباره چرخش تو AVL بود که من دو حالت رو گفتم و نیمه کار موند!!من همه حالت ها رو میگم که اگه کسی خواست استفاده کنه !!

سلام.خب من دوران رو میگم یعنی اون کاری که خودم انجام میدم!!شایدم سخت باشه ولی خب میگم حالا شاید کمک کرد

اول یکم درباره [tex]AVL[/tex] بگیم که این درخت چیه اصلا!
[tex]AVL[/tex] درخت جست وجو دودوی متوازن هستش!!!اگه یادتون باشه توی درخت [tex]BST[/tex] عملیات هایی مثل درج و جست وجو و... به ارتفاع درخت وابسته بود و حالا این احتمال وجود داشت که درخت مورب باشه و اونوقت کارمون درمیومد و باید تمام گره ها رو در بدترین حالت بررسی میکردیم
ولی اینجا این مشکل رو نداریم و همه چی لگاریتمی هستش که این کار رو به وسیله فاکتور توازن انجام میدیم!!فاکتور توازن نمیذاره ارتفاع درخت از حالت توازنش(لگاریتمی بودن) خارج شه و به این صورت تعریفش میکنیم:
مقادیر مجاز هم برای فاکتور توازن [tex]-1,0,1[/tex] هستش
خب حالا سوال اینه این فاکتور توازن چه موقع به هم میخوره؟؟؟
با یه مثال میگم!!!ببینید فرض کنید اول ما فقط نود ریشه رو داریم الان فاکتور توازن ریشه ۰ هستش!!بعدش یه نود به زیر درخت سمت چپ اضافه میکنیم فاکتور توازن ریشه ۱ میشه.دوباره یه نود به زیر درخت سمت چپ اضافه میکنیم و الان فاکتور توازن ریشه ۲ میشه!!و درختمون الان از حالت متوازن بودن خارج هستش
راه کار چیه؟؟؟اینجاست که دوران وارد میشه ما باید نود یه سری نود ها رو دوران (چرخش یا [tex]Rotate[/tex] ) بدیم تا این مشکل رو حل کنیم
این به هم ریختگی فاکتور توازن ۴ تا حالت مختلف داره که یکی یکی بررسی میکنیم
قبلش همین اول کار من میخوام ۳ تا پارامتر تعریف کنم!به خاطر سپاریشون هم اصلا کاری نداره البته تسلط هم پیدا کردید اصلا نیازی به این پارامتر ها ندارید ولی خب الان برای اینکه بشه توضیح داد من اینا رو تعریف میکنیم

[tex]x[/tex] : نودی که فاکتور توازنش به هم ریخته

[tex]y[/tex] : فرزند [tex]x[/tex]

[tex]z[/tex] : نودی جدیدی که درج کردیم و باعث بر هم ریختن توازن شده

همینا بودن!!فک نکنم خیلی سخت باشه اینا یادتون بمونه!!


حالت اول:اگه y فرزند راست x باشه , z هم به زیر درخت راست y اضافه شه (ببینید ریتم کار معلومه مثلا برای حالت دوم دقیقا برعکس اینه)
یا یه کار دیگه هم میتونید انجام بدید اینکه x رو داشته باش حالا y باید فرزند سمت راستش باشه و y رو در نظر بگیر z باید تو زیر درخت سمت راستش باشه حالا گره ای که فاکتور توازنش به هم خورده رو دوران میدیم یعنی x و اونم دوران به چپ.حالا نحوه دوران به چپ چجوریه؟
ببینید اینجوری تصور کنید که اون نود رو با دست گرفتی و داری به سمت چپ میچرخونیش!!!همین !!
اون نود و فرزنداش رو فقط میچرخونیم . به بقیه نودا کاری نداریم !!!یه کوچولو ریزه کاری داره که اونا رو فعلا نمیگم تا پیچیده نشه پس یه بار دیگه هم میگم مثل اینه که با دستت اون نود رو گرفتی رو داری با دستت به سمت چپ میچرخونی
من یه مثال زدم تا ببینید اون فلشی که تو شکل به عنوان جهت دوران نشون دادم تصور کن خودت داری اون نود رو میچرخونی

________________________________________________________________________________​___
حالت دوم:اگه y فرزند چپ x باشه , z هم به زیر درخت چپ y اضافه شه یا یه کار دیگه هم میتونید انجام بدید اینکه x رو داشته باش حالا y باید فرزند سمت چپش باشه و y رو در نظر بگیر z باید تو زیر درخت سمت چپش باشه حالا گره ای که فاکتور توازنش به هم خورده رو دوران میدیم یعنی x و اونم دوران به راست.حالا نحوه دوران به راست چجوریه؟
اینجوری تصور کنید که اون نود رو با دست گرفتی و داری به سمت راست میچرخونیش!!!همین !!

________________________________________________________________________________​______

این مثال رو هم ببینید و خودتون باهاش این دوتا دوران رو انجام بدید و مثالای مشابه که یا حالت اول هستن و یا حالت دوم و اگه دیدید کار با این روش براتون راحته بگید تا دو تا حالت دیگه رو هم بگم!!


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


________________________________________________________________________________​________________________

قبل از حالت سوم و چهارم یه چیزی بگم-
۱-ببینید برای اینکه نوع روشا یادتون بمونه: یه حالت همه چی سمت راست اتفاق میفته-یه حالت همه چی سمت چپ -یه حالت راست و چپ-یه حالت چپ و راست-
۲-اولین دوران همیشه خلاف جهت z هستش اینم شاید جالب باشه!!! یعنی z به هر زیر درختی اضافه شد اولین دوران در خلاف جهت z هستش و اگه نیاز به دومین دوران پیدا شد در همون جهتی که z اولین بار وارد شده

الان روش سوم و چهارم رو هم میگم تا کاملا متوجه نکته دوم شید

__________________________________________________________________________

حالت سوم: توی این حالت x رو در نظر بگیرید و y فرزند چپ x هست و y رو در نظر بگیرید و z زیر درخت سمت راست y اضافه میشه خب حالا طبق نکته ۲ مسئله رو حل میکنیم و ابتدا y رو دوران راست میدیم و بعدش x رو دوران چپ میدیم.

حالت چهارم: توی این حالت x رو در نظر بگیرید و y فرزند راست x هست و y رو در نظر بگیرید و z زیر درخت سمت چپ y اضافه میشه خب حالا طبق نکته ۲ مسئله رو حل میکنیم و ابتدا y رو دوران چپ میدیم و بعدش x رو دوران راست میدیم.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


_______________________________________________________
یه سری ریزه کاری هم داره که حواستون باشه:
وقتی دارید دوران میدید فرض کنید که یه عنصری مثل y خودش فرزند چپ داره و عنصری که دوران داده میشه هم قراره سمت چپ y قرار بگیره اولویت با عنصری هستش که دوران داده میشه اول اون سمت چپ y بذارید و بعدش بقیه رو نسبت بهش بچینید-برای سمت راست هم همین

وقتی گفتم دوران بدید با کل فرزنداش اون فرزندهایی مد نظرن هستن که تو مسیر دورانن!!مثلا دوران به چپ فرزندای چپ و دوران به راست فرزندهای راست.
اگه چند تا نود داشتیم که فتکتور توازنشون به هم ریخته بود اولویت به نود نزدیکتر به z هستش
پس مهمترین مسئله اینه که x , y ,z رو مشخص کنید!!


اینم مثال هایی که یکی از دوستان گذاشته بودند
با چیزایی که گفتم انجام بدید خیلی خیلی راحت هستش

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


عذر میخوام اگه سرتونو درد اوردم