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

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

$x$ : نودی که فاکتور توازنش به هم ریخته

$y$ : فرزند $x$

$z$ : نودی جدیدی که درج کردیم و باعث بر هم ریختن توازن شده

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


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

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

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


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