با سلام
امسال دروس مشترک ناجوانمردانه سخت بود!!
دوستان گزینه هایی که زدن رو بگن تا چک کنیم.
آخه باید بریم استراحت کنیم واسه کنکور فردا.ایشاله فردا ظهر میام
ساختمان داده :
۱ - یا ۱ زدم یا ۲!
۲- ۱ زدم
۳- ۱ زدم
۴- ۴ زدم
۵ - ۳ زدم
۶ - نزدم
در کل اگه وقت بیشتری داشتم و دانشگاه اذیت نمی کرد میشد تست های داده و الگوریتم رو زد
ولی در مورد شبکه بعید می دونم ۱ دونه فقط زدم
۲-۱
درج باید در انتها صورت گیرد پس زمان (۱)O
کاهش کلید چون درخت دلخواه است و هیپ نیست (فقط در سوال مثال هیپ را برای نشان دادن کامل بودن آورده) پس زمان (۱)O
چون حذف ممکن است از هر جایی اتفاق افتد و کامل بودن بهم می ریزد پس زمان O(logn
۱-۲ (کدوم از چهار تا رو باز باید امتحان کنم یادم نیست D
۳-??
۲-۴
۳-۵
۴-۶ (kامین کوچکترین عنصر رو تو زمان (n) پیدا می کنیم و kتا عنصر رو مرتب می کنیم و قسمت دوم فقط هزینه مرتب کردن رو داریم.
سوال ۴۰ در کلید D گزینه ۲ میشه
اینم شکل درخت
[attachment=9437]
دوست عزیز برای حذف درسته میشه ۱ ولی بعدازحذف حتماباید مرتب بشه وگرنه هیپ نیس
پس میشه logn
میشدبرای هر سه
(۲۰ بهمن ۱۳۹۱ ۰۳:۱۴ ق.ظ)IT86 نوشته شده توسط: دوست عزیز برای حذف درسته میشه ۱ ولی بعدازحذف حتماباید مرتب بشه وگرنه هیپ نیسواسه حذف که حتما میشه o n
پس میشه logn
میشدبرای هر سه
واسه درج میشه olog n
واسه تغییر شک دارم من اینم o n در نظرگرفتم چون مکان هیچ گره ای مشخص نیس.
فکر کنم یا یک میشه یا دو
اگه دقت کنید این درخت هیپ نیست بلکه درخت انتخابیست. به نظر من واسه حذف چون باید اول بین برگ ها که تعدادشون n تاست جستجو کنی و بعد حذف دوباره مرتب کاری کنی میشه nlog n ولی واسه درج فقط کافیه به اخر اضافه و بعد مرتب کنی که میشه log n واسه تغییر هم که میشه log n .
(۲۰ بهمن ۱۳۹۱ ۰۹:۱۵ ق.ظ)ali123321 نوشته شده توسط: اگه دقت کنید این درخت هیپ نیست بلکه درخت انتخابیست. به نظر من واسه حذف چون باید اول بین برگ ها که تعدادشون n تاست جستجو کنی و بعد حذف دوباره مرتب کاری کنی میشه nlog n ولی واسه درج فقط کافیه به اخر اضافه و بعد مرتب کنی که میشه log n واسه تغییر هم که میشه log n .
واسه تغییر مکانه گره مشخص اگه نباشه که نیست میشه o n
چون باید همه گره ها رو بررسی کرد.
(۲۰ بهمن ۱۳۹۱ ۰۹:۱۵ ق.ظ)ali123321 نوشته شده توسط: اگه دقت کنید این درخت هیپ نیست بلکه درخت انتخابیست. به نظر من واسه حذف چون باید اول بین برگ ها که تعدادشون n تاست جستجو کنی و بعد حذف دوباره مرتب کاری کنی میشه nlog n ولی واسه درج فقط کافیه به اخر اضافه و بعد مرتب کنی که میشه log n واسه تغییر هم که میشه log n .
کاملا باهاتون موافقم.چون وقتی برگی حذف میشه دیگه درخت متوازن نیست.پس نمیشه با log n درستش کرد!دو حالت دیگه هم شبیه heap میشه log n.
من می گم تنها درج میشه با logn و برای حذف یک عنصر و تغییر اون باید اول مکان عنصر پیدا شه که در این نوع درخت میشه on
(۲۰ بهمن ۱۳۹۱ ۰۳:۱۸ ب.ظ)mahdiii نوشته شده توسط: من می گم تنها درج میشه با logn و برای حذف یک عنصر و تغییر اون باید اول مکان عنصر پیدا شه که در این نوع درخت میشه onاره بنظرمنم فقط درج درسته
دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
برای کاهش فک کنم بشه بازم log n آخه گفته شده کوچکترین فرزند در ریشه هستش ااگرکاهش بدیم یک مقداررو ممکنه اون مقدارازریشه کمترشه و باید جابه جابشه
ازطرفیم ممکنه باز پدراون ریشه هم بزرگترباشه و بازهم جابه جامیشه
بازم میشه log n
پس هرشه بازم میشه اگرهیپ درنظرنگیریم
هیپ درنظربگیریمم میشه هرسه
مگر اینکه درخت انتخابی بگیریم ک بستگی داره به تعداد آرایه ها که باتوجه به سوال ک ذکرنکرده از ارایه پس انتخابی نمیشه
(۲۰ بهمن ۱۳۹۱ ۰۴:۳۶ ب.ظ)IT86 نوشته شده توسط: دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
برای کاهش فک کنم بشه بازم log n آخه گفته شده کوچکترین فرزند در ریشه هستش ااگرکاهش بدیم یک مقداررو ممکنه اون مقدارازریشه کمترشه و باید جابه جابشه
ازطرفیم ممکنه باز پدراون ریشه هم بزرگترباشه و بازهم جابه جامیشه
بازم میشه log n
پس هرشه بازم میشه اگرهیپ درنظرنگیریم
هیپ درنظربگیریمم میشه هرسه
مگر اینکه درخت انتخابی بگیریم ک بستگی داره به تعداد آرایه ها که باتوجه به سوال ک ذکرنکرده از ارایه پس انتخابی نمیشه
شما داری رو سوال ۳۷ بحث می کنی؟ کجا گفته AVL کجا اصلا گفته درخت دودویی؟!!!
بله همون سوال ۳۷ خود سوال گفته درخته دودویی یکی از دوستانم گفته avl منظورشه یکی هم گفته درخت انتخابی