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