۱
subtitle
ارسال: #۱
درج و حذف AVL
سلام درج و حذف و درخت AVL به چه صورت هست ؟ اگه بشه باشکل نشون بدین عالی میشه
(۰۶ آذر ۱۳۹۲ ۱۱:۲۴ ب.ظ)calm boy نوشته شده توسط:(06 آذر ۱۳۹۲ ۱۱:۰۷ ب.ظ)masoomeh_s نوشته شده توسط: سلام
اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.
موفق باشید.
سلام
کتاب clrs رو نداریم
میشه یه توضیح بدین
کی باید double rotation بزنیم
(۰۷ دى ۱۳۹۳ ۰۴:۲۸ ب.ظ)masoomeh_s نوشته شده توسط: سلام
مرسی. ولی اصلا توضیحات کامل نیست. از کجا فهمیدید ۱۵ رو ب راست دوران بدید؟ دابل دوران کی میشه؟ تعریف best رو هم بر عکس نوشتین
خسته نباشید تو ارسال ها قبلی گفته بود درخت bst درختی است که فرزندان سمت راست هرنود بزرگنر ا و فرزندان سمت چپ کوچکتر از آن نود است یعنی برای هر نود باید برقرار بشه (دقت کنید)...
درخت avl هم درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
حالا عددی مثل ۱۴ را می خواهیم در درخت درج کنیم اول طبق bst بررسی می کنیم تا محل قرارگیری نود رو پیدا کنیم . طبق شکل
حالا فاکتور توازن هر نود را بررسی می کنیم همانطور که تو شکل هست فاکتور توازن ۲۰ و ۱۰ بیشتر از ۱ شد پس ابتدا زیردرخت ۱۰ یعنی ۱۵ به سمت راست دوران می دهیم فرزند راست ۱۲ که ۱۴ بود نمیتونه فرزند چپ (خالی هست) باشه چون درخت bst است پس میره پایین و در مکان درست درج میشه بعد میریم سروقت دوران بعدی که ۱۰ هست به سمت چپ دوران میدیم..
همواره bst بودن درخت رو چک کن
اگه سوال دارید بفرماید..