۱
subtitle
ارسال: #۱
  
درج و حذف AVL
سلام درج و حذف و درخت AVL به چه صورت هست ؟ اگه بشه باشکل نشون بدین عالی میشه
۳
ارسال: #۲
  
درج و حذف AVL
سلام مجدد از نو عزیزم.
نکته :
درخت AVL نوعی BST هست که متوازن باشه و اختلاف سطح برگ هاش از ۱ بیشتر نشه.
یعنی عنصر تکراری نمی تونه داشته باشه.اگه یه عنصر تکراری رو توی AVL درج کنیم.اونقدر مقایسه میشه تا ببینه عنصر تکراری داریم یا نه.اگه به عنصر تکراری برخورد کرد عملیات رو پایان میده.
ضمنا وقتی یک عنصر رو درک می کنیم.اختلاف ارتفاع چپ و راست هر گره و اجدادش رو چک می کنیم اگه فهمیدیم متوازن نبود باید چرخش هایی رو انجام بدیم که این قسمت کار به نظر مشکل ترین بحث هست که اکثر دوستان مشکل دارند.
برای یاد گیری درج و حذف و جستجو در AVL یک نرم افزار آنلاین بهتون معرفی می کنم تا لذت ببرید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
---
موارد دیگه ای مثل avl tree rotation و چرخش درخت رو توی اینترنت سرچ کنید و اگه به مطلب مهمی رسیدید لینکشو بذارید.
نکته :
درخت AVL نوعی BST هست که متوازن باشه و اختلاف سطح برگ هاش از ۱ بیشتر نشه.
یعنی عنصر تکراری نمی تونه داشته باشه.اگه یه عنصر تکراری رو توی AVL درج کنیم.اونقدر مقایسه میشه تا ببینه عنصر تکراری داریم یا نه.اگه به عنصر تکراری برخورد کرد عملیات رو پایان میده.
ضمنا وقتی یک عنصر رو درک می کنیم.اختلاف ارتفاع چپ و راست هر گره و اجدادش رو چک می کنیم اگه فهمیدیم متوازن نبود باید چرخش هایی رو انجام بدیم که این قسمت کار به نظر مشکل ترین بحث هست که اکثر دوستان مشکل دارند.
برای یاد گیری درج و حذف و جستجو در AVL یک نرم افزار آنلاین بهتون معرفی می کنم تا لذت ببرید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
---
موارد دیگه ای مثل avl tree rotation و چرخش درخت رو توی اینترنت سرچ کنید و اگه به مطلب مهمی رسیدید لینکشو بذارید.
۱
ارسال: #۳
  
درج و حذف AVL
سلام.
ببخشید شکل نمی تونم نشونت بدم ولی می تونم بگم سوال ۳۹ سال ۹۰ فناوری اطلاعات رو ببینی کفایت می کنه.
برای درج مثل درخت دو دودویی با ریشه مقایسه اگه کوچیک تر بود میایم چپ و اگه بزگ تر بود می ریم راست و تا آخر این کارو ادامه می دیم و در آخر به یه برگ می رسیم که ندمون رو بهش اضافه می کنیم دقیقا مثل درخت دو دویی تنها تفاوتش اینه که ممکنه درخت از تعادل بیرون بیاد که مجبوریم با چرخش به راست یا چپ یا ... دوباره تبدیلش کنیم به AVL.
حذفش رو تا حالا جایی ندیدم ولی این چیزی که می گم باید درست باشه چون اضافه کردنشم تا حالا ندیده بودم ولی تو سوالای ۹۰ درست حسابش کردم
مثل درخت دو دویی عمل کن که سه حالت پیش می آد.
ند که می خوای حذف کنی:
۱/ برگ باشه
۲/ تک فرزندی باشه
۳/دو فرزندی باشه
و همه مراحل رو برو و نکتش اینه که اگه حذف باعث شد درخت از تعادل خارج شه دوباره با چرخش درستش کن.
تعادل و چرخش رو هم که بلدی اگه مشکلی بود بگو توضیح می دم.
ببخشید شکل نمی تونم نشونت بدم ولی می تونم بگم سوال ۳۹ سال ۹۰ فناوری اطلاعات رو ببینی کفایت می کنه.
برای درج مثل درخت دو دودویی با ریشه مقایسه اگه کوچیک تر بود میایم چپ و اگه بزگ تر بود می ریم راست و تا آخر این کارو ادامه می دیم و در آخر به یه برگ می رسیم که ندمون رو بهش اضافه می کنیم دقیقا مثل درخت دو دویی تنها تفاوتش اینه که ممکنه درخت از تعادل بیرون بیاد که مجبوریم با چرخش به راست یا چپ یا ... دوباره تبدیلش کنیم به AVL.
حذفش رو تا حالا جایی ندیدم ولی این چیزی که می گم باید درست باشه چون اضافه کردنشم تا حالا ندیده بودم ولی تو سوالای ۹۰ درست حسابش کردم
مثل درخت دو دویی عمل کن که سه حالت پیش می آد.
ند که می خوای حذف کنی:
۱/ برگ باشه
۲/ تک فرزندی باشه
۳/دو فرزندی باشه
و همه مراحل رو برو و نکتش اینه که اگه حذف باعث شد درخت از تعادل خارج شه دوباره با چرخش درستش کن.
تعادل و چرخش رو هم که بلدی اگه مشکلی بود بگو توضیح می دم.
۱
۱
ارسال: #۵
  
RE: درج و حذف AVL
چون درخت avl یک درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
ارتفاع راست نود - ارتفاع چپ نود= فاکتور توازن
تو شکل که گذاشتم درخت سمت چپ قبل از درج عدد ۱۴ یک درخت متوازن بود پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم (دوران می دهیم ).
ارتفاع راست نود - ارتفاع چپ نود= فاکتور توازن
تو شکل که گذاشتم درخت سمت چپ قبل از درج عدد ۱۴ یک درخت متوازن بود پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم (دوران می دهیم ).
۰
ارسال: #۶
  
درج و حذف AVL
خواهش.
فدا مدات.
همون طور که گفتم مث درخت دو دویی اضافه کرده بعد چرخش داده.
فدا مدات.
همون طور که گفتم مث درخت دو دویی اضافه کرده بعد چرخش داده.
۰
ارسال: #۷
  
درج و حذف AVL
دو چیزو از جزوه پارسه باید یاد بگیرید :
ارتفاع چپ : طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت چپ
ارتفاع راست: طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت راست
---
در (درخت با ارتفاع متوازن) داریم :
اگر برای هر گره، ارتفاع چپ را منهای ارتفاع راست کنیم و از حاصل قدر مطلق بگیریم حاصل نباید از ۱ بیشتر شود.
یعنی اختلاف ارتفاع چپ و راست باید حداکثر ۱ باشد.
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید
ارتفاع چپ : طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت چپ
ارتفاع راست: طولانی ترین مسیر رو ب پایین از یک گره تا برگ برای زیر درخت راست
---
در (درخت با ارتفاع متوازن) داریم :
اگر برای هر گره، ارتفاع چپ را منهای ارتفاع راست کنیم و از حاصل قدر مطلق بگیریم حاصل نباید از ۱ بیشتر شود.
یعنی اختلاف ارتفاع چپ و راست باید حداکثر ۱ باشد.
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید
ارسال: #۸
  
RE: درج و حذف AVL
میشه لطفا از عملیات درج در درخت اول هم توضیحات بذاری؟
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید
[/quote]
---
خوب میایم گره ها رو در درخت درج می کنیم و هر جا دیدیم خصوصیت فوق صدق نکرد کمی جابجایی انجام میدیم تا اختلاف ارتفاع هر گره از ۱ بیشتر نشه.
مثل همون PDF
---
نکته مهم :
البته درخت با ارتفاع متوازن رو با درخت متوازن اشتباه نکنید و همچنین بدونید AVL یک BST هست که ارتفاع متوازن داره
درخت متوازن درختی هست که اختلاف سطح برگهاش حداکثر ۱ باشه.
یک عکس هم از جزوه ی پارسه میذارم سوال بود بپرسید
[/quote]
۰
ارسال: #۹
  
درج و حذف AVL
سلام
به این تعریف درخت با ارتفاع متوازن مطمئنین ؟؟؟؟؟؟؟؟؟
تو کنکور سوال ندن درخت با ارتفاع متوازن بعد از این بریم بعد بفهمیم منظور طراح همون درخت متوازن خودمون بوده ؟؟؟؟
به این تعریف درخت با ارتفاع متوازن مطمئنین ؟؟؟؟؟؟؟؟؟
تو کنکور سوال ندن درخت با ارتفاع متوازن بعد از این بریم بعد بفهمیم منظور طراح همون درخت متوازن خودمون بوده ؟؟؟؟
۰
ارسال: #۱۰
  
درج و حذف AVL
اگه بگن درخت جستجوی متوازن منظر AVL هست
اگه بگن درخت متوازن میتونه AVL نباشه
اگه بگن درخت متوازن میتونه AVL نباشه
۰
ارسال: #۱۱
  
درج و حذف AVL
اگه شک دارید مثال نقض پیدا کردین از جزوه ی قدسی و مقسمی و CLRS بزنید تا بدونیم.
۰
ارسال: #۱۲
  
RE: درج و حذف AVL
این هم یک فایل در رابطه با ساخت این درخت و چرخشهاست.
نمونهی خوبی میتونه باشه.
نمونهی خوبی میتونه باشه.
۰
۰
۰
ارسال: #۱۵
  
درج و حذف AVL
مرسی روش خیلی خوبی واسه دانلود بود مشکل داشتم با httpsحالا دیگه اسون دانلود میشه
ممنون
ممنون
۰
ارسال: #۱۶
  
RE: درج و حذف AVL
سلام به همه خسته نباشیداگه میشه لطف کنیدچرخش ها رودردرختAVLتوضیح بدید ممنون میشم
۰
ارسال: #۱۷
  
RE: درج و حذف AVL
سلام
اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.
موفق باشید.
اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.
موفق باشید.
ارسال: #۱۸
  
RE: درج و حذف AVL
ارسال: #۱۹
  
RE: درج و حذف AVL
(۰۶ آذر ۱۳۹۲ ۱۱:۲۴ ب.ظ)calm boy نوشته شده توسط:(06 آذر ۱۳۹۲ ۱۱:۰۷ ب.ظ)masoomeh_s نوشته شده توسط: سلام
اگه کتاب clrs رو دارید از روی اون بخونید ، جزوه ای که لینک دادم هم در کنارش نکات خوبی داره
فصل ۴ درخت avl رو توضیح داده اگه سوالی داشتین بعدش بفرمایید.
موفق باشید.
سلام
کتاب clrs رو نداریم
میشه یه توضیح بدین
کی باید double rotation بزنیم
چون درخت avl یک درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
ارتفاع راست نود - ارتفاع چپ نود= فاکتور توازن
تو شکل که گذاشتم درخت سمت چپ قبل از درج عدد ۱۴ یک درخت متوازن بود پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم (دوران می دهیم ).
۰
ارسال: #۲۰
  
RE: درج و حذف AVL
خواهش میکنم یکی کامل تووضیح بده درج در درخت اول چطوریه؟ دوران دادنش رو بلد نیستم. از رو شکل نمیفهمم. یکی کامل دورانشو توضیح بده
یکی بگه لطفا
یکی بگه لطفا
یکی بگه لطفا
یکی بگه لطفا
۰
ارسال: #۲۱
  
RE: درج و حذف AVL
سلام
خسته نباشید تو ارسال ها قبلی گفته بود درخت bst درختی است که فرزندان سمت راست هرنود بزرگنر ا و فرزندان سمت چپ کوچکتر از آن نود است یعنی برای هر نود باید برقرار بشه (دقت کنید)...
درخت avl هم درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
حالا عددی مثل ۱۴ را می خواهیم در درخت درج کنیم اول طبق bst بررسی می کنیم تا محل قرارگیری نود رو پیدا کنیم . طبق شکل
حالا فاکتور توازن هر نود را بررسی می کنیم همانطور که تو شکل هست فاکتور توازن ۲۰ و ۱۰ بیشتر از ۱ شد پس ابتدا زیردرخت ۱۰ یعنی ۱۵ به سمت راست دوران می دهیم فرزند راست ۱۲ که ۱۴ بود نمیتونه فرزند چپ (خالی هست) باشه چون درخت bst است پس میره پایین و در مکان درست درج میشه بعد میریم سروقت دوران بعدی که ۱۰ هست به سمت چپ دوران میدیم..
همواره bst بودن درخت رو چک کن
اگه سوال دارید بفرماید..
خسته نباشید تو ارسال ها قبلی گفته بود درخت bst درختی است که فرزندان سمت راست هرنود بزرگنر ا و فرزندان سمت چپ کوچکتر از آن نود است یعنی برای هر نود باید برقرار بشه (دقت کنید)...
درخت avl هم درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
حالا عددی مثل ۱۴ را می خواهیم در درخت درج کنیم اول طبق bst بررسی می کنیم تا محل قرارگیری نود رو پیدا کنیم . طبق شکل
حالا فاکتور توازن هر نود را بررسی می کنیم همانطور که تو شکل هست فاکتور توازن ۲۰ و ۱۰ بیشتر از ۱ شد پس ابتدا زیردرخت ۱۰ یعنی ۱۵ به سمت راست دوران می دهیم فرزند راست ۱۲ که ۱۴ بود نمیتونه فرزند چپ (خالی هست) باشه چون درخت bst است پس میره پایین و در مکان درست درج میشه بعد میریم سروقت دوران بعدی که ۱۰ هست به سمت چپ دوران میدیم..
همواره bst بودن درخت رو چک کن
اگه سوال دارید بفرماید..
ارسال: #۲۲
  
RE: درج و حذف AVL
(۰۷ دى ۱۳۹۳ ۰۴:۲۸ ب.ظ)masoomeh_s نوشته شده توسط: سلام
مرسی. ولی اصلا توضیحات کامل نیست. از کجا فهمیدید ۱۵ رو ب راست دوران بدید؟ دابل دوران کی میشه؟ تعریف best رو هم بر عکس نوشتین
خسته نباشید تو ارسال ها قبلی گفته بود درخت bst درختی است که فرزندان سمت راست هرنود بزرگنر ا و فرزندان سمت چپ کوچکتر از آن نود است یعنی برای هر نود باید برقرار بشه (دقت کنید)...
درخت avl هم درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
حالا عددی مثل ۱۴ را می خواهیم در درخت درج کنیم اول طبق bst بررسی می کنیم تا محل قرارگیری نود رو پیدا کنیم . طبق شکل
حالا فاکتور توازن هر نود را بررسی می کنیم همانطور که تو شکل هست فاکتور توازن ۲۰ و ۱۰ بیشتر از ۱ شد پس ابتدا زیردرخت ۱۰ یعنی ۱۵ به سمت راست دوران می دهیم فرزند راست ۱۲ که ۱۴ بود نمیتونه فرزند چپ (خالی هست) باشه چون درخت bst است پس میره پایین و در مکان درست درج میشه بعد میریم سروقت دوران بعدی که ۱۰ هست به سمت چپ دوران میدیم..
همواره bst بودن درخت رو چک کن
اگه سوال دارید بفرماید..
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close