سلام
دوستان وقتی گره ۱۴ به شاخه سمت راست ۱۲ اضافه میشه خوب الان این چرخشی که باید انجام بشه تا دوباره به صورت AVL دربیاد به چه صورته؟؟من این چرخش بعضی گره هارو میشه متوجه نمیشم.اگر کسی میدونه برام توضیح بده آخه تو هیچ کتابی طریقه چرخشو نگفته.
جواب گزینه ۳ است.
توی کتاب ساختمان داده هوروویتز صفحات ۴۹۷ تا ۵۰۱ نوشته کامل با مثال....نمیشه اینجا توضیح داد باید خودت بری شکل ها رو ببینی تا بشه توضیح داد.. ولی واسه این تست که شکلش رو بکش بعد می بینی که ۱۴ باید به زیر درخت راست ۱۲ اضافه بشه وقتی اضافه کردی حالا باید واسه تمام گره ها branch factor ش رو حساب کن.. bf برای هر گره اینجوری حساب میشه:
( ارتفاع زیر درخت راست گره -ارتفاع زیر درخت چپ گره) =bf
اگه حساب کنی می بینی که bf گره ها اعدادی توی بازه ی -۲و-۱و۰و۱و۲ خواهد بود... حالا از مسیر گره اضافه شده یعنی ۱۴ تا ریشه به اولین گره ای رسیدی که bf اش -۲ یا +۲ بود انتخاب کن حالا میبینی که فقط میشه ۱۲ رو جای این عدد انتخاب شده قرار داد تا درخت متوازن در بیاد در عین حال AVL هم باشه .... باید بری کتاب رو بخونی تا جزئیات دستت بیاد اینجوری نمیشه توضیح داد امیدوارم تا حدودی جوابت رو گرفته باشی...
شما درست میگید ولی من اگر کتابی داشتم که توضیح داده بود این سوالو اینجا مطرح نمیکردم من کتاب مقسمی رو دارم اصلا توضیحی نداده و اون کتابو ندارم.
حالا اگر کسی میتونه اون صفحات کتاب که توضیح داده در مورد چرخش AVL برام اسکن کنه ممنون میشم.
(۰۴ آذر ۱۳۹۲ ۰۹:۲۳ ب.ظ)tarane1992 نوشته شده توسط: سلام
دوستان وقتی گره ۱۴ به شاخه سمت راست ۱۲ اضافه میشه خوب الان این چرخشی که باید انجام بشه تا دوباره به صورت AVL دربیاد به چه صورته؟؟من این چرخش بعضی گره هارو میشه متوجه نمیشم.اگر کسی میدونه برام توضیح بده آخه تو هیچ کتابی طریقه چرخشو نگفته.
جواب گزینه ۳ است.
چون درخت avl یک درخت bst متوازن است یعنی درختی که فاکتور توازن هر نودش ۱+ و ۱- و ۰ باشد .
ارتفاع راست نود - ارتفاع چپ نود= فاکتور توازن
پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم .
جواب این دوستمون درسته اما من یک راه حل جامع میگم برای متوازن کردن درخت ناا متوازن:
۱:پیدا کردن گره محور:اولین گره نزدیک موقعیت درج که اختلاف ارتفاع دو زیردرخت آن بیشتر از ۱ باشه
۲:با توجه به اینکه گره جدید (گره که ارتفاع درخت نامتوازن کرده)در سمت چپ یا راست، فرزندان چپ یا راست گره محور قرار بگیره نوع چرخش مشخص میشه
الف) چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
مراحل:۱-گره محور به سمت چپ ۲-فرزند راست گره محور، جایگزین محور ۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور
نیاز به ۱ دوران
ب)چرخش چپ - چپLL :گره جدید در زیر درخت چپ ،فرزند چپ محور باشد
مراحل:گره محور به سمت راست۲-فرزند چپ محور،جایگزین محور ۳-زیردرخت راست گره جایگزین(در صورت وجود) زیردرخت چپ گره محور
نیاز به ۱ دوران
ج)چرخش مضاعف راست- چپ RL:گره جدید در زیردرخت چپ،فرزند راست گره محور باشد
مراحل:۱-گره محور به سمت چپ ۲-فرزند چپ،فرزند راست گره محور ،جایگزین محور۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور
نیاز به ۲ دوران
د)چرخش چپ - راست LR: گره جدید زیردرخت راست، فرزند چپ محور باشد
مراحل:گره محور به سمت راست۲- فرزند راست فرزند چپ محور ،جایگزین محور ۳-زیر درخت راست گره جایگزین (در صورت وجود) زیر درخت چپ محور
نیاز به ۲ دوران
توی این سوال اگه بالای هر عنصر بعد اضافه کردن ۱۴ عدد توازن بذارید همانطور که دوستان گفتن و رسم کردن عنصر محور میشه ۱۰ چون نزدیکترین به موقعیت درجه
اینجا گره ۱۴ زیر درخت چپ فرزند راست محور هست پس میشه روش (ج) طبق مراحل که بالا گفتم بری میرسی به شکل سوم که معصومه خانم رسم کرد نیاز به شکل ۲ نیست
فکر کنم جامع گفتم با چندتا مثال حل کن یاد میگیری
have good time
یاد گرفتم آقا مهرداد عالی و جامع توضیح دادید واقعا کیف کردم مشکلم حل شد.
نمیدونم چی بگم....
فقط آرزو میکنه یکی از رتبه های خوب مانشت بشین....
خیلی خوشحالم
یک دنیا ممنونم.
(۰۶ آذر ۱۳۹۲ ۰۲:۰۳ ب.ظ)Mehrdad7soft نوشته شده توسط: جواب این دوستمون درسته اما من یک راه حل جامع میگم برای متوازن کردن درخت ناا متوازن:این شکل با این حرف شما که گفتید
۱:پیدا کردن گره محور:اولین گره نزدیک موقعیت درج که اختلاف ارتفاع دو زیردرخت آن بیشتر از ۱ باشه
۲:با توجه به اینکه گره جدید (گره که ارتفاع درخت نامتوازن کرده)در سمت چپ یا راست، فرزندان چپ یا راست گره محور قرار بگیره نوع چرخش مشخص میشه
الف) چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
مراحل:۱-گره محور به سمت چپ ۲-فرزند راست گره محور، جایگزین محور ۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور
نیاز به ۱ دوران
ب)چرخش چپ - چپLL :گره جدید در زیر درخت چپ ،فرزند چپ محور باشد
مراحل:گره محور به سمت راست۲-فرزند چپ محور،جایگزین محور ۳-زیردرخت راست گره جایگزین(در صورت وجود) زیردرخت چپ گره محور
نیاز به ۱ دوران
ج)چرخش مضاعف راست- چپ RL:گره جدید در زیردرخت چپ،فرزند راست گره محور باشد
مراحل:۱-گره محور به سمت چپ ۲-فرزند چپ،فرزند راست گره محور ،جایگزین محور۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور
نیاز به ۲ دوران
د)چرخش چپ - راست LR: گره جدید زیردرخت راست، فرزند چپ محور باشد
مراحل:گره محور به سمت راست۲- فرزند راست فرزند چپ محور ،جایگزین محور ۳-زیر درخت راست گره جایگزین (در صورت وجود) زیر درخت چپ محور
نیاز به ۲ دوران
توی این سوال اگه بالای هر عنصر بعد اضافه کردن ۱۴ عدد توازن بذارید همانطور که دوستان گفتن و رسم کردن عنصر محور میشه ۱۰ چون نزدیکترین به موقعیت درجه
اینجا گره ۱۴ زیر درخت چپ فرزند راست محور هست پس میشه روش (ج) طبق مراحل که بالا گفتم بری میرسی به شکل سوم که معصومه خانم رسم کرد نیاز به شکل ۲ نیست
فکر کنم جامع گفتم با چندتا مثال حل کن یاد میگیری
have good time
چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
همخونی نداره. گره جدید یعنی ۲ توشکل نامتوازن جز فرزندچپه....تو شکل متوازن هم بازم فرزند چپ مونده...ولی شما گفتی گره جدید در زیر درخت راست، فرزند راسته محوره!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
have good time
[/quote]
این شکل با این حرف شما که گفتید
چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
همخونی نداره. گره جدید یعنی ۲ توشکل نامتوازن جز فرزندچپه....تو شکل متوازن هم بازم فرزند چپ مونده...ولی شما گفتی گره جدید در زیر درخت راست، فرزند راسته محوره!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
[/quote]
چرا پس توضیحاتی که داده شده اینجا جواب نمیده؟؟؟؟؟؟؟
کسی نیست جواب بده؟؟؟؟؟؟؟؟؟
(۱۳ آذر ۱۳۹۲ ۱۲:۴۴ ق.ظ)mary1234 نوشته شده توسط:(06 آذر ۱۳۹۲ ۰۲:۰۳ ب.ظ)Mehrdad7soft نوشته شده توسط: جواب این دوستمون درسته اما من یک راه حل جامع میگم برای متوازن کردن درخت ناا متوازن:این شکل با این حرف شما که گفتید
۱:پیدا کردن گره محور:اولین گره نزدیک موقعیت درج که اختلاف ارتفاع دو زیردرخت آن بیشتر از ۱ باشه
۲:با توجه به اینکه گره جدید (گره که ارتفاع درخت نامتوازن کرده)در سمت چپ یا راست، فرزندان چپ یا راست گره محور قرار بگیره نوع چرخش مشخص میشه
الف) چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
مراحل:۱-گره محور به سمت چپ ۲-فرزند راست گره محور، جایگزین محور ۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور
نیاز به ۱ دوران
ب)چرخش چپ - چپLL :گره جدید در زیر درخت چپ ،فرزند چپ محور باشد
مراحل:گره محور به سمت راست۲-فرزند چپ محور،جایگزین محور ۳-زیردرخت راست گره جایگزین(در صورت وجود) زیردرخت چپ گره محور
نیاز به ۱ دوران
ج)چرخش مضاعف راست- چپ RL:گره جدید در زیردرخت چپ،فرزند راست گره محور باشد
مراحل:۱-گره محور به سمت چپ ۲-فرزند چپ،فرزند راست گره محور ،جایگزین محور۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور
نیاز به ۲ دوران
د)چرخش چپ - راست LR: گره جدید زیردرخت راست، فرزند چپ محور باشد
مراحل:گره محور به سمت راست۲- فرزند راست فرزند چپ محور ،جایگزین محور ۳-زیر درخت راست گره جایگزین (در صورت وجود) زیر درخت چپ محور
نیاز به ۲ دوران
توی این سوال اگه بالای هر عنصر بعد اضافه کردن ۱۴ عدد توازن بذارید همانطور که دوستان گفتن و رسم کردن عنصر محور میشه ۱۰ چون نزدیکترین به موقعیت درجه
اینجا گره ۱۴ زیر درخت چپ فرزند راست محور هست پس میشه روش (ج) طبق مراحل که بالا گفتم بری میرسی به شکل سوم که معصومه خانم رسم کرد نیاز به شکل ۲ نیست
فکر کنم جامع گفتم با چندتا مثال حل کن یاد میگیری
have good time
چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
همخونی نداره. گره جدید یعنی ۲ توشکل نامتوازن جز فرزندچپه....تو شکل متوازن هم بازم فرزند چپ مونده...ولی شما گفتی گره جدید در زیر درخت راست، فرزند راسته محوره!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
چون این راه حل کتاب که شما عکس گرفتی اسمشو اشتباه نوشته این چرخش چپ چپ هست
چون گره جدید زیردرخت چپ فرزند چپ محور هست
چون این راه حل کتاب که شما عکس گرفتی اسمشو اشتباه نوشته این چرخش چپ چپ هست
چون گره جدید زیردرخت چپ فرزند چپ محور هست
[/quote]
سپاس