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

سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

ارسال:
  

tarane1992 پرسیده:

سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

سلام
دوستان وقتی گره ۱۴ به شاخه سمت راست ۱۲ اضافه میشه خوب الان این چرخشی که باید انجام بشه تا دوباره به صورت AVL دربیاد به چه صورته؟؟من این چرخش بعضی گره هارو میشه متوجه نمیشم.اگر کسی میدونه برام توضیح بده آخه تو هیچ کتابی طریقه چرخشو نگفته.HuhHuhHuhHuhHuhHuh

جواب گزینه ۳ است.


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

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

۵
ارسال:
  

Mehrdad7soft پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

جواب این دوستمون درسته اما من یک راه حل جامع میگم برای متوازن کردن درخت ناا متوازن:

۱:پیدا کردن گره محور:اولین گره نزدیک موقعیت درج که اختلاف ارتفاع دو زیردرخت آن بیشتر از ۱ باشه

۲:با توجه به اینکه گره جدید (گره که ارتفاع درخت نامتوازن کرده)در سمت چپ یا راست، فرزندان چپ یا راست گره محور قرار بگیره نوع چرخش مشخص می‌شه

الف) چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد

مراحل:۱-گره محور به سمت چپ ۲-فرزند راست گره محور، جایگزین محور ۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور

نیاز به ۱ دوران

ب)چرخش چپ - چپLL :گره جدید در زیر درخت چپ ،فرزند چپ محور باشد

مراحل:گره محور به سمت راست۲-فرزند چپ محور،جایگزین محور ۳-زیردرخت راست گره جایگزین(در صورت وجود) زیردرخت چپ گره محور

نیاز به ۱ دوران

ج)چرخش مضاعف راست- چپ RL:گره جدید در زیردرخت چپ،فرزند راست گره محور باشد

مراحل:۱-گره محور به سمت چپ ۲-فرزند چپ،فرزند راست گره محور ،جایگزین محور۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور

نیاز به ۲ دوران

د)چرخش چپ - راست LR: گره جدید زیردرخت راست، فرزند چپ محور باشد

مراحل:گره محور به سمت راست۲- فرزند راست فرزند چپ محور ،جایگزین محور ۳-زیر درخت راست گره جایگزین (در صورت وجود) زیر درخت چپ محور

نیاز به ۲ دوران

توی این سوال اگه بالای هر عنصر بعد اضافه کردن ۱۴ عدد توازن بذارید همانطور که دوستان گفتن و رسم کردن عنصر محور می‌شه ۱۰ چون نزدیکترین به موقعیت درجه

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

فکر کنم جامع گفتم با چندتا مثال حل کن یاد میگیری
have good time
نقل قول این ارسال در یک پاسخ

ارسال:
  

mary1234 پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

(۰۶ آذر ۱۳۹۲ ۰۲:۰۳ ب.ظ)Mehrdad7soft نوشته شده توسط:  جواب این دوستمون درسته اما من یک راه حل جامع میگم برای متوازن کردن درخت ناا متوازن:

۱:پیدا کردن گره محور:اولین گره نزدیک موقعیت درج که اختلاف ارتفاع دو زیردرخت آن بیشتر از ۱ باشه

۲:با توجه به اینکه گره جدید (گره که ارتفاع درخت نامتوازن کرده)در سمت چپ یا راست، فرزندان چپ یا راست گره محور قرار بگیره نوع چرخش مشخص می‌شه

الف) چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد

مراحل:۱-گره محور به سمت چپ ۲-فرزند راست گره محور، جایگزین محور ۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور

نیاز به ۱ دوران

ب)چرخش چپ - چپLL :گره جدید در زیر درخت چپ ،فرزند چپ محور باشد

مراحل:گره محور به سمت راست۲-فرزند چپ محور،جایگزین محور ۳-زیردرخت راست گره جایگزین(در صورت وجود) زیردرخت چپ گره محور

نیاز به ۱ دوران

ج)چرخش مضاعف راست- چپ RL:گره جدید در زیردرخت چپ،فرزند راست گره محور باشد

مراحل:۱-گره محور به سمت چپ ۲-فرزند چپ،فرزند راست گره محور ،جایگزین محور۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور

نیاز به ۲ دوران

د)چرخش چپ - راست LR: گره جدید زیردرخت راست، فرزند چپ محور باشد

مراحل:گره محور به سمت راست۲- فرزند راست فرزند چپ محور ،جایگزین محور ۳-زیر درخت راست گره جایگزین (در صورت وجود) زیر درخت چپ محور

نیاز به ۲ دوران

توی این سوال اگه بالای هر عنصر بعد اضافه کردن ۱۴ عدد توازن بذارید همانطور که دوستان گفتن و رسم کردن عنصر محور می‌شه ۱۰ چون نزدیکترین به موقعیت درجه

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

فکر کنم جامع گفتم با چندتا مثال حل کن یاد میگیری
have good time
این شکل با این حرف شما که گفتید
چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
همخونی نداره. گره جدید یعنی ۲ توشکل نامتوازن جز فرزندچپه....تو شکل متوازن هم بازم فرزند چپ مونده...ولی شما گفتی گره جدید در زیر درخت راست، فرزند راسته محوره!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟


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

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

ارسال:
  

ماهسان لیما پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

have good time
[/quote]
این شکل با این حرف شما که گفتید
چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
همخونی نداره. گره جدید یعنی ۲ توشکل نامتوازن جز فرزندچپه....تو شکل متوازن هم بازم فرزند چپ مونده...ولی شما گفتی گره جدید در زیر درخت راست، فرزند راسته محوره!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
[/quote]

چرا پس توضیحاتی که داده شده اینجا جواب نمیده؟؟؟؟؟؟؟
کسی نیست جواب بده؟؟؟؟؟؟؟؟؟Confused
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Mehrdad7soft پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

(۱۳ آذر ۱۳۹۲ ۱۲:۴۴ ق.ظ)mary1234 نوشته شده توسط:  
(06 آذر ۱۳۹۲ ۰۲:۰۳ ب.ظ)Mehrdad7soft نوشته شده توسط:  جواب این دوستمون درسته اما من یک راه حل جامع میگم برای متوازن کردن درخت ناا متوازن:

۱:پیدا کردن گره محور:اولین گره نزدیک موقعیت درج که اختلاف ارتفاع دو زیردرخت آن بیشتر از ۱ باشه

۲:با توجه به اینکه گره جدید (گره که ارتفاع درخت نامتوازن کرده)در سمت چپ یا راست، فرزندان چپ یا راست گره محور قرار بگیره نوع چرخش مشخص می‌شه

الف) چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد

مراحل:۱-گره محور به سمت چپ ۲-فرزند راست گره محور، جایگزین محور ۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور

نیاز به ۱ دوران

ب)چرخش چپ - چپLL :گره جدید در زیر درخت چپ ،فرزند چپ محور باشد

مراحل:گره محور به سمت راست۲-فرزند چپ محور،جایگزین محور ۳-زیردرخت راست گره جایگزین(در صورت وجود) زیردرخت چپ گره محور

نیاز به ۱ دوران

ج)چرخش مضاعف راست- چپ RL:گره جدید در زیردرخت چپ،فرزند راست گره محور باشد

مراحل:۱-گره محور به سمت چپ ۲-فرزند چپ،فرزند راست گره محور ،جایگزین محور۳-زیر درخت چپ گره جایگزین(در صورت وجود) زیر درخت راست گره محور

نیاز به ۲ دوران

د)چرخش چپ - راست LR: گره جدید زیردرخت راست، فرزند چپ محور باشد

مراحل:گره محور به سمت راست۲- فرزند راست فرزند چپ محور ،جایگزین محور ۳-زیر درخت راست گره جایگزین (در صورت وجود) زیر درخت چپ محور

نیاز به ۲ دوران

توی این سوال اگه بالای هر عنصر بعد اضافه کردن ۱۴ عدد توازن بذارید همانطور که دوستان گفتن و رسم کردن عنصر محور می‌شه ۱۰ چون نزدیکترین به موقعیت درجه

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

فکر کنم جامع گفتم با چندتا مثال حل کن یاد میگیری
have good time
این شکل با این حرف شما که گفتید
چرخش راست-راست RR:گره جدید(خلاف خودمون!) در زیر درخت راست ،فرزند راست گره محور باشد
همخونی نداره. گره جدید یعنی ۲ توشکل نامتوازن جز فرزندچپه....تو شکل متوازن هم بازم فرزند چپ مونده...ولی شما گفتی گره جدید در زیر درخت راست، فرزند راسته محوره!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

چون این راه حل کتاب که شما عکس گرفتی‌ اسمشو اشتباه نوشته این چرخش چپ چپ هست

چون گره جدید زیردرخت چپ فرزند چپ محور هست
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

ماهسان لیما پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

چون این راه حل کتاب که شما عکس گرفتی‌ اسمشو اشتباه نوشته این چرخش چپ چپ هست

چون گره جدید زیردرخت چپ فرزند چپ محور هست
[/quote]

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

۳
ارسال:
  

masoomeh_s پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

(۰۴ آذر ۱۳۹۲ ۰۹:۲۳ ب.ظ)tarane1992 نوشته شده توسط:  سلام
دوستان وقتی گره ۱۴ به شاخه سمت راست ۱۲ اضافه میشه خوب الان این چرخشی که باید انجام بشه تا دوباره به صورت AVL دربیاد به چه صورته؟؟من این چرخش بعضی گره هارو میشه متوجه نمیشم.اگر کسی میدونه برام توضیح بده آخه تو هیچ کتابی طریقه چرخشو نگفته.HuhHuhHuhHuhHuhHuh

جواب گزینه ۳ است.


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

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

پس از درج عدد ۱۴ ، نودهای ۶۰ و ۲۰ فاکتور توازنشان به هم می خورد پایین ترین جدی که فاکتور توازنش به هم خورده را درست می کنیم .


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

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

۰
ارسال:
  

آنجلا پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

توی کتاب ساختمان داده هوروویتز صفحات ۴۹۷ تا ۵۰۱ نوشته کامل با مثال....نمیشه اینجا توضیح داد باید خودت بری شکل ها رو ببینی تا بشه توضیح داد.. ولی واسه این تست که شکلش رو بکش بعد می بینی که ۱۴ باید به زیر درخت راست ۱۲ اضافه بشه وقتی اضافه کردی حالا باید واسه تمام گره ها branch factor ش رو حساب کن.. bf برای هر گره اینجوری حساب میشه:
( ارتفاع زیر درخت راست گره -ارتفاع زیر درخت چپ گره) =bf
اگه حساب کنی می بینی که bf گره ها اعدادی توی بازه ی -۲و-۱و۰و۱و۲ خواهد بود... حالا از مسیر گره اضافه شده یعنی ۱۴ تا ریشه به اولین گره ای رسیدی که bf اش -۲ یا +۲ بود انتخاب کن حالا میبینی که فقط میشه ۱۲ رو جای این عدد انتخاب شده قرار داد تا درخت متوازن در بیاد در عین حال AVL هم باشه .... باید بری کتاب رو بخونی تا جزئیات دستت بیاد اینجوری نمیشه توضیح داد امیدوارم تا حدودی جوابت رو گرفته باشی...
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

tarane1992 پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

شما درست میگید ولی من اگر کتابی داشتم که توضیح داده بود این سوالو اینجا مطرح نمیکردم من کتاب مقسمی رو دارم اصلا توضیحی نداده و اون کتابو ندارم.Sad

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

۰
ارسال: #۱۰
  

tarane1992 پاسخ داده:

RE: سوال ساختمان داده آی تی ۹۱(پیمایش پیش ترتیب درAVL)

یاد گرفتم آقا مهرداد عالی و جامع توضیح دادید واقعا کیف کردم مشکلم حل شد.Smile

نمیدونم چی بگم....

فقط آرزو میکنه یکی از رتبه های خوب مانشت بشین....

خیلی خوشحالم

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۱,۳۰۳ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۹۶۶ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۱۸۵ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۳,۹۶۳ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۶,۱۳۶ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  منبع ساختمان داده RASPINA ۷ ۷,۲۳۶ ۱۶ آذر ۱۳۹۸ ۰۱:۳۰ ق.ظ
آخرین ارسال: Behnam‌
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۲,۶۲۰ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
Question فرادرس برای ساختمان داده marvelous ۷ ۵,۷۱۰ ۱۰ مرداد ۱۳۹۸ ۰۹:۳۷ ب.ظ
آخرین ارسال: marvelous
  معرفی منبع خوب برای ساختمان داده alireza9819 ۴ ۵,۱۷۰ ۱۰ مرداد ۱۳۹۸ ۰۲:۵۸ ب.ظ
آخرین ارسال: marvelous
  پیش نیاز هایی برای ارشد نرم افزار کامپیوتر mahsaabd ۳ ۲,۵۵۷ ۲۵ تیر ۱۳۹۸ ۰۹:۵۰ ب.ظ
آخرین ارسال: fo-eng

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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