زمان کنونی: ۱۶ آبان ۱۴۰۳, ۰۴:۰۷ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

درج و حذف AVL

ارسال:
  

teacherpc پرسیده:

درج و حذف AVL

سلام درج و حذف و درخت AVL به چه صورت هست ؟ اگه بشه باشکل نشون بدین عالی میشه
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

csharpisatechnology پاسخ داده:

درج و حذف AVL

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

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

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

۱
ارسال:
  

mehdi.nine پاسخ داده:

درج و حذف AVL

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


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

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

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

۱
ارسال:
  

teacherpc پاسخ داده:

RE: درج و حذف AVL

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

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

۱
ارسال:
  

masoomeh_s پاسخ داده:

RE: درج و حذف AVL

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

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


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


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

mehdi.nine پاسخ داده:

درج و حذف AVL

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

۰
ارسال:
  

csharpisatechnology پاسخ داده:

درج و حذف AVL

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


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

ارسال:
  

setarehfb پاسخ داده:

RE: درج و حذف AVL

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

۰
ارسال:
  

ana_12345 پاسخ داده:

درج و حذف AVL

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

۰
ارسال: #۱۰
  

teacherpc پاسخ داده:

درج و حذف AVL

اگه بگن درخت جستجوی متوازن منظر AVL هست
اگه بگن درخت متوازن میتونه AVL نباشه
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۱
  

csharpisatechnology پاسخ داده:

درج و حذف AVL

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

۰
ارسال: #۱۳
  

teacherpc پاسخ داده:

درج و حذف AVL

سلام من نتونستم دانلود کنم اصلن دانلود نمیشه نمیدونم مشکل کجاست
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۴
  

Mohammad-A پاسخ داده:

درج و حذف AVL

احتمالا با https مشکل داشته باشید٬ s رو بردارید٬ حل میشه.
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۵
  

teacherpc پاسخ داده:

درج و حذف AVL

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

۰
ارسال: #۱۶
  

هدا پاسخ داده:

RE: درج و حذف AVL

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

۰
ارسال: #۱۷
  

masoomeh_s پاسخ داده:

RE: درج و حذف AVL

سلام

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

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

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

موفق باشید.
نقل قول این ارسال در یک پاسخ

ارسال: #۱۸
  

calm boy پاسخ داده:

RE: درج و حذف AVL

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

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

موفق باشید.

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

ارسال: #۱۹
  

masoomeh_s پاسخ داده:

RE: درج و حذف AVL

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

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

موفق باشید.

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

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

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


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


فایل‌(های) پیوست شده

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۲۰
  

setarehfb پاسخ داده:

RE: درج و حذف AVL

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

یکی بگه لطفا

یکی بگه لطفا
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۲۱
  

masoomeh_s پاسخ داده:

RE: درج و حذف AVL

سلام

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

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


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

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


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

ارسال: #۲۲
  

setarehfb پاسخ داده:

RE: درج و حذف AVL

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




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


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

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


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

اگه سوال دارید بفرماید..
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حذف اکانت Alireza_1387 ۴ ۵,۶۷۶ ۱۴ آذر ۱۴۰۱ ۰۸:۲۱ ب.ظ
آخرین ارسال: shirin.kh90
  حذف درس برای خواندن کنکور ارشد sima84 ۴ ۵,۰۳۶ ۲۶ اردیبهشت ۱۳۹۹ ۰۹:۰۰ ب.ظ
آخرین ارسال: عزیز دادخواه
  درج عبارت "نوبت دوم" در مدرک دکتری siiib70 ۳ ۴,۰۳۸ ۲۸ مهر ۱۳۹۸ ۰۲:۵۰ ق.ظ
آخرین ارسال: marvelous
  حذف از b tree کمک لطفا Sanazzz ۰ ۱,۸۴۹ ۱۱ بهمن ۱۳۹۷ ۰۹:۳۴ ب.ظ
آخرین ارسال: Sanazzz
  مشکلات مغایرت معدل درج شده در سنجش و معدل موجود در کارنامه newwink ۳۳ ۲۸,۲۶۰ ۰۴ شهریور ۱۳۹۷ ۱۲:۴۷ ق.ظ
آخرین ارسال: alie0928
  حذف ضمیر موصولی ☹ jinubo ۲ ۶,۹۹۶ ۰۱ اردیبهشت ۱۳۹۷ ۰۶:۴۳ ب.ظ
آخرین ارسال: jinubo
  حذف اضطراری دو درس در ارشد asalimi ۰ ۲,۵۸۳ ۰۸ آذر ۱۳۹۶ ۰۲:۳۲ ق.ظ
آخرین ارسال: asalimi
  حذف وزارت علوم H-Arshad ۰ ۱۰ ۲۱ آبان ۱۳۹۶ ۰۱:۵۲ ب.ظ
آخرین ارسال: H-Arshad
  با بدهی استقلال و پرسپولیس چند کلاس کپری حذف می شود؟ H-Arshad ۰ ۴ ۱۱ آبان ۱۳۹۶ ۱۲:۰۹ ق.ظ
آخرین ارسال: H-Arshad
  درج ایمیل تمامی نویسندگان یا نویسنده اول؟ siiib70 ۵ ۳,۳۲۱ ۲۸ مرداد ۱۳۹۶ ۰۹:۲۳ ب.ظ
آخرین ارسال: The BesT

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close