صفحه‌ها: ۱ ۲
سلام درج و حذف و درخت AVL به چه صورت هست ؟ اگه بشه باشکل نشون بدین عالی میشه
سلام.
ببخشید شکل نمی تونم نشونت بدم ولی می تونم بگم سوال ۳۹ سال ۹۰ فناوری اطلاعات رو ببینی کفایت می کنه.
برای درج مثل درخت دو دودویی با ریشه مقایسه اگه کوچیک تر بود میایم چپ و اگه بزگ تر بود می ریم راست و تا آخر این کارو ادامه می دیم و در آخر به یه برگ می رسیم که ندمون رو بهش اضافه می کنیم دقیقا مثل درخت دو دویی تنها تفاوتش اینه که ممکنه درخت از تعادل بیرون بیاد که مجبوریم با چرخش به راست یا چپ یا ... دوباره تبدیلش کنیم به AVL.
حذفش رو تا حالا جایی ندیدم ولی این چیزی که می گم باید درست باشه چون اضافه کردنشم تا حالا ندیده بودم ولی تو سوالای ۹۰ درست حسابش کردم
مثل درخت دو دویی عمل کن که سه حالت پیش می آد.
ند که می خوای حذف کنی:
۱/ برگ باشه
۲/ تک فرزندی باشه
۳/دو فرزندی باشه
و همه مراحل رو برو و نکتش اینه که اگه حذف باعث شد درخت از تعادل خارج شه دوباره با چرخش درستش کن.
تعادل و چرخش رو هم که بلدی اگه مشکلی بود بگو توضیح می دم.
ممنون که پاسخ گذاشتین
این لینک رو دانلود کنید avl فول میشید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خواهش.
فدا مدات.
همون طور که گفتم مث درخت دو دویی اضافه کرده بعد چرخش داده.
دو چیزو از جزوه پارسه باید یاد بگیرید :
ارتفاع چپ : طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت چپ
ارتفاع راست: طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت راست
---
در (درخت با ارتفاع متوازن) داریم :
اگر برای هر گره، ارتفاع چپ را منهای ارتفاع راست کنیم و از حاصل قدر مطلق بگیریم حاصل نباید از ۱ بیشتر شود.
یعنی اختلاف ارتفاع چپ و راست باید حداکثر ۱ باشد.
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید
سلام
به این تعریف درخت با ارتفاع متوازن مطمئنین ؟؟؟؟؟؟؟؟؟
تو کنکور سوال ندن درخت با ارتفاع متوازن بعد از این بریم بعد بفهمیم منظور طراح همون درخت متوازن خودمون بوده ؟؟؟؟
اگه بگن درخت جستجوی متوازن منظر AVL هست
اگه بگن درخت متوازن میتونه AVL نباشه
اگه شک دارید مثال نقض پیدا کردین از جزوه ی قدسی و مقسمی و CLRS بزنید تا بدونیم.
این هم یک فایل در رابطه با ساخت این درخت و چرخش‌هاست.
نمونه‌ی خوبی میتونه باشه.
سلام من نتونستم دانلود کنم اصلن دانلود نمیشه نمیدونم مشکل کجاست
احتمالا با https مشکل داشته باشید٬ s رو بردارید٬ حل میشه.
مرسی روش خیلی خوبی واسه دانلود بود مشکل داشتم با httpsحالا دیگه اسون دانلود میشه
ممنون
سلام مجدد از نو عزیزم.
نکته :
درخت AVL نوعی BST هست که متوازن باشه و اختلاف سطح برگ هاش از ۱ بیشتر نشه.
یعنی عنصر تکراری نمی تونه داشته باشه.اگه یه عنصر تکراری رو توی AVL درج کنیم.اونقدر مقایسه میشه تا ببینه عنصر تکراری داریم یا نه.اگه به عنصر تکراری برخورد کرد عملیات رو پایان میده.
ضمنا وقتی یک عنصر رو درک می کنیم.اختلاف ارتفاع چپ و راست هر گره و اجدادش رو چک می کنیم اگه فهمیدیم متوازن نبود باید چرخش هایی رو انجام بدیم که این قسمت کار به نظر مشکل ترین بحث هست که اکثر دوستان مشکل دارند.
برای یاد گیری درج و حذف و جستجو در AVL یک نرم افزار آنلاین بهتون معرفی می کنم تا لذت ببرید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
---
موارد دیگه ای مثل avl tree rotation و چرخش درخت رو توی اینترنت سرچ کنید و اگه به مطلب مهمی رسیدید لینکشو بذارید.
سلام به همه خسته نباشیداگه میشه لطف کنیدچرخش ها رودردرختAVLتوضیح بدید ممنون میشم
سلام
اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.
موفق باشید.