سلام مجدد از نو عزیزم.
نکته :
درخت AVL نوعی BST هست که متوازن باشه و اختلاف سطح برگ هاش از ۱ بیشتر نشه.
یعنی عنصر تکراری نمی تونه داشته باشه.اگه یه عنصر تکراری رو توی AVL درج کنیم.اونقدر مقایسه میشه تا ببینه عنصر تکراری داریم یا نه.اگه به عنصر تکراری برخورد کرد عملیات رو پایان میده.
ضمنا وقتی یک عنصر رو درک می کنیم.اختلاف ارتفاع چپ و راست هر گره و اجدادش رو چک می کنیم اگه فهمیدیم متوازن نبود باید چرخش هایی رو انجام بدیم که این قسمت کار به نظر مشکل ترین بحث هست که اکثر دوستان مشکل دارند.
برای یاد گیری درج و حذف و جستجو در AVL یک نرم افزار آنلاین بهتون معرفی می کنم تا لذت ببرید:

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

---
موارد دیگه ای مثل avl tree rotation و چرخش درخت رو توی اینترنت سرچ کنید و اگه به مطلب مهمی رسیدید لینکشو بذارید.

سلام.
ببخشید شکل نمی تونم نشونت بدم ولی می تونم بگم سوال ۳۹ سال ۹۰ فناوری اطلاعات رو ببینی کفایت می کنه.
برای درج مثل درخت دو دودویی با ریشه مقایسه اگه کوچیک تر بود میایم چپ و اگه بزگ تر بود می ریم راست و تا آخر این کارو ادامه می دیم و در آخر به یه برگ می رسیم که ندمون رو بهش اضافه می کنیم دقیقا مثل درخت دو دویی تنها تفاوتش اینه که ممکنه درخت از تعادل بیرون بیاد که مجبوریم با چرخش به راست یا چپ یا ... دوباره تبدیلش کنیم به AVL.


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

مثل درخت دو دویی عمل کن که سه حالت پیش می آد.
ند که می خوای حذف کنی:
۱/ برگ باشه
۲/ تک فرزندی باشه
۳/دو فرزندی باشه
و همه مراحل رو برو و نکتش اینه که اگه حذف باعث شد درخت از تعادل خارج شه دوباره با چرخش درستش کن.

تعادل و چرخش رو هم که بلدی اگه مشکلی بود بگو توضیح می دم.

ممنون که پاسخ گذاشتین
این لینک رو دانلود کنید avl فول میشید

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

چون درخت avl یک درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .

ارتفاع راست نود - ارتفاع چپ نود= فاکتور توازن


تو شکل که گذاشتم درخت سمت چپ قبل از درج عدد ۱۴ یک درخت متوازن بود پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم (دوران می دهیم ).

خواهش.
فدا مدات.
همون طور که گفتم مث درخت دو دویی اضافه کرده بعد چرخش داده.

دو چیزو از جزوه پارسه باید یاد بگیرید :
ارتفاع چپ : طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت چپ
ارتفاع راست: طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت راست
---
در (درخت با ارتفاع متوازن) داریم :
اگر برای هر گره، ارتفاع چپ را منهای ارتفاع راست کنیم و از حاصل قدر مطلق بگیریم حاصل نباید از ۱ بیشتر شود.
یعنی اختلاف ارتفاع چپ و راست باید حداکثر ۱ باشد.
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید

میشه لطفا از عملیات درج در درخت اول هم توضیحات بذاری؟
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید
[/quote]

سلام
به این تعریف درخت با ارتفاع متوازن مطمئنین ؟؟؟؟؟؟؟؟؟
تو کنکور سوال ندن درخت با ارتفاع متوازن بعد از این بریم بعد بفهمیم منظور طراح همون درخت متوازن خودمون بوده ؟؟؟؟

اگه بگن درخت جستجوی متوازن منظر AVL هست
اگه بگن درخت متوازن میتونه AVL نباشه

اگه شک دارید مثال نقض پیدا کردین از جزوه ی قدسی و مقسمی و CLRS بزنید تا بدونیم.

این هم یک فایل در رابطه‌ با ساخت این درخت و چرخش‌هاست.
نمونه‌ی خوبی میتونه باشه.

سلام من نتونستم دانلود کنم اصلن دانلود نمیشه نمیدونم مشکل کجاست

احتمالا با https مشکل داشته باشید٬ s رو بردارید٬ حل میشه.

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

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

سلام

اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره

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

فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.

موفق باشید.

(۰۶ آذر ۱۳۹۲ ۱۱:۰۷ ب.ظ)masoomeh_s نوشته شده توسط:  سلام

اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.

موفق باشید.

سلام
کتاب clrs رو نداریم
میشه یه توضیح بدین
کی باید double rotation بزنیم

(۰۶ آذر ۱۳۹۲ ۱۱:۲۴ ب.ظ)calm boy نوشته شده توسط:  

(06 آذر ۱۳۹۲ ۱۱:۰۷ ب.ظ)masoomeh_s نوشته شده توسط:  سلام

اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.

موفق باشید.

سلام
کتاب clrs رو نداریم
میشه یه توضیح بدین
کی باید double rotation بزنیم

چون درخت avl یک درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .

ارتفاع راست نود - ارتفاع چپ نود= فاکتور توازن


تو شکل که گذاشتم درخت سمت چپ قبل از درج عدد ۱۴ یک درخت متوازن بود پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم (دوران می دهیم ).

خواهش میکنم یکی کامل تووضیح بده درج در درخت اول چطوریه؟ دوران دادنش رو بلد نیستم. از رو شکل نمیفهمم. یکی کامل دورانشو توضیح بده

---

یکی بگه لطفا

---

یکی بگه لطفا

سلام

خسته نباشید تو ارسال ها قبلی گفته بود درخت bst درختی است که فرزندان سمت راست هرنود بزرگنر ا و فرزندان سمت چپ کوچکتر از آن نود است یعنی برای هر نود باید برقرار بشه (دقت کنید)...
درخت avl هم درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .

حالا عددی مثل ۱۴ را می خواهیم در درخت درج کنیم اول طبق bst بررسی می کنیم تا محل قرارگیری نود رو پیدا کنیم . طبق شکل
حالا فاکتور توازن هر نود را بررسی می کنیم همانطور که تو شکل هست فاکتور توازن ۲۰ و ۱۰ بیشتر از ۱ شد پس ابتدا زیردرخت ۱۰ یعنی ۱۵ به سمت راست دوران می دهیم فرزند راست ۱۲ که ۱۴ بود نمیتونه فرزند چپ (خالی هست) باشه چون درخت bst است پس میره پایین و در مکان درست درج میشه بعد میریم سروقت دوران بعدی که ۱۰ هست به سمت چپ دوران میدیم..


همواره bst بودن درخت رو چک کن

اگه سوال دارید بفرماید..

(۰۷ دى ۱۳۹۳ ۰۴:۲۸ ب.ظ)masoomeh_s نوشته شده توسط:  سلام




مرسی. ولی اصلا توضیحات کامل نیست. از کجا فهمیدید ۱۵ رو ب راست دوران بدید؟ دابل دوران کی میشه؟ تعریف best رو هم بر عکس نوشتین


خسته نباشید تو ارسال ها قبلی گفته بود درخت bst درختی است که فرزندان سمت راست هرنود بزرگنر ا و فرزندان سمت چپ کوچکتر از آن نود است یعنی برای هر نود باید برقرار بشه (دقت کنید)...
درخت avl هم درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .

حالا عددی مثل ۱۴ را می خواهیم در درخت درج کنیم اول طبق bst بررسی می کنیم تا محل قرارگیری نود رو پیدا کنیم . طبق شکل
حالا فاکتور توازن هر نود را بررسی می کنیم همانطور که تو شکل هست فاکتور توازن ۲۰ و ۱۰ بیشتر از ۱ شد پس ابتدا زیردرخت ۱۰ یعنی ۱۵ به سمت راست دوران می دهیم فرزند راست ۱۲ که ۱۴ بود نمیتونه فرزند چپ (خالی هست) باشه چون درخت bst است پس میره پایین و در مکان درست درج میشه بعد میریم سروقت دوران بعدی که ۱۰ هست به سمت چپ دوران میدیم..


همواره bst بودن درخت رو چک کن

اگه سوال دارید بفرماید..