با سلام
امسال دروس مشترک ناجوانمردانه سخت بود!!
دوستان گزینه هایی که زدن رو بگن تا چک کنیم.
آخه باید بریم استراحت کنیم واسه کنکور فردا.ایشاله فردا ظهر میام
ساختمان داده :
1 - یا 1 زدم یا 2!
2- 1 زدم
3- 1 زدم
4- 4 زدم
5 - 3 زدم
6 - نزدم
در کل اگه وقت بیشتری داشتم و دانشگاه اذیت نمی کرد میشد تست های داده و الگوریتم رو زد
ولی در مورد شبکه بعید می دونم 1 دونه فقط زدم
2-1
درج باید در انتها صورت گیرد پس زمان (1)O
کاهش کلید چون درخت دلخواه است و هیپ نیست (فقط در سوال مثال هیپ را برای نشان دادن کامل بودن آورده) پس زمان (1)O
چون حذف ممکن است از هر جایی اتفاق افتد و کامل بودن بهم می ریزد پس زمان O(logn
1-2 (کدوم از چهار تا رو باز باید امتحان کنم یادم نیست D
3-??
2-4
3-5
4-6 (kامین کوچکترین عنصر رو تو زمان (n) پیدا می کنیم و kتا عنصر رو مرتب می کنیم و قسمت دوم فقط هزینه مرتب کردن رو داریم.
دوست عزیز برای حذف درسته میشه 1 ولی بعدازحذف حتماباید مرتب بشه وگرنه هیپ نیس
پس میشه logn
میشدبرای هر سه
(20 بهمن 1391 03:14 ق.ظ)IT86 نوشته شده توسط: [ -> ]دوست عزیز برای حذف درسته میشه ۱ ولی بعدازحذف حتماباید مرتب بشه وگرنه هیپ نیس
پس میشه logn
میشدبرای هر سه
واسه حذف که حتما میشه o n
واسه درج میشه olog n
واسه تغییر شک دارم من اینم o n در نظرگرفتم چون مکان هیچ گره ای مشخص نیس.
فکر کنم یا یک میشه یا دو
اگه دقت کنید این درخت هیپ نیست بلکه درخت انتخابیست. به نظر من واسه حذف چون باید اول بین برگ ها که تعدادشون n تاست جستجو کنی و بعد حذف دوباره مرتب کاری کنی میشه nlog n ولی واسه درج فقط کافیه به اخر اضافه و بعد مرتب کنی که میشه log n واسه تغییر هم که میشه log n .
(20 بهمن 1391 09:15 ق.ظ)ali123321 نوشته شده توسط: [ -> ]اگه دقت کنید این درخت هیپ نیست بلکه درخت انتخابیست. به نظر من واسه حذف چون باید اول بین برگ ها که تعدادشون n تاست جستجو کنی و بعد حذف دوباره مرتب کاری کنی میشه nlog n ولی واسه درج فقط کافیه به اخر اضافه و بعد مرتب کنی که میشه log n واسه تغییر هم که میشه log n .
واسه تغییر مکانه گره مشخص اگه نباشه که نیست میشه o n
چون باید همه گره ها رو بررسی کرد.
(20 بهمن 1391 09:15 ق.ظ)ali123321 نوشته شده توسط: [ -> ]اگه دقت کنید این درخت هیپ نیست بلکه درخت انتخابیست. به نظر من واسه حذف چون باید اول بین برگ ها که تعدادشون n تاست جستجو کنی و بعد حذف دوباره مرتب کاری کنی میشه nlog n ولی واسه درج فقط کافیه به اخر اضافه و بعد مرتب کنی که میشه log n واسه تغییر هم که میشه log n .
کاملا باهاتون موافقم.چون وقتی برگی حذف میشه دیگه درخت متوازن نیست.پس نمیشه با log n درستش کرد!دو حالت دیگه هم شبیه heap میشه log n.
من می گم تنها درج میشه با logn و برای حذف یک عنصر و تغییر اون باید اول مکان عنصر پیدا شه که در این نوع درخت میشه on
(20 بهمن 1391 03:18 ب.ظ)mahdiii نوشته شده توسط: [ -> ]من می گم تنها درج میشه با logn و برای حذف یک عنصر و تغییر اون باید اول مکان عنصر پیدا شه که در این نوع درخت میشه on
اره بنظرمنم فقط درج درسته
دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
برای کاهش فک کنم بشه بازم log n آخه گفته شده کوچکترین فرزند در ریشه هستش ااگرکاهش بدیم یک مقداررو ممکنه اون مقدارازریشه کمترشه و باید جابه جابشه
ازطرفیم ممکنه باز پدراون ریشه هم بزرگترباشه و بازهم جابه جامیشه
بازم میشه log n
پس هرشه بازم میشه اگرهیپ درنظرنگیریم
هیپ درنظربگیریمم میشه هرسه
مگر اینکه درخت انتخابی بگیریم ک بستگی داره به تعداد آرایه ها که باتوجه به سوال ک ذکرنکرده از ارایه پس انتخابی نمیشه
(20 بهمن 1391 04:36 ب.ظ)IT86 نوشته شده توسط: [ -> ]دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
برای کاهش فک کنم بشه بازم log n آخه گفته شده کوچکترین فرزند در ریشه هستش ااگرکاهش بدیم یک مقداررو ممکنه اون مقدارازریشه کمترشه و باید جابه جابشه
ازطرفیم ممکنه باز پدراون ریشه هم بزرگترباشه و بازهم جابه جامیشه
بازم میشه log n
پس هرشه بازم میشه اگرهیپ درنظرنگیریم
هیپ درنظربگیریمم میشه هرسه
مگر اینکه درخت انتخابی بگیریم ک بستگی داره به تعداد آرایه ها که باتوجه به سوال ک ذکرنکرده از ارایه پس انتخابی نمیشه
شما داری رو سوال 37 بحث می کنی؟ کجا گفته AVL کجا اصلا گفته درخت دودویی؟!!!
37-2
38-1
40-2
41-3
42-2
44-3
(20 بهمن 1391 05:05 ب.ظ)IT86 نوشته شده توسط: [ -> ]بله همون سوال ۳۷ خود سوال گفته درخته دودویی یکی از دوستانم گفته avl منظورشه یکی هم گفته درخت انتخابی
این درخت اصلا شبیه به درخت دودویی متوازن AVL نیست. درخت AVL که یک درخت جسجوی دودویی متوازن است، درختی است که هر گره از فرزند راستش کوچکتر و از فرزند چپش بزرگتر باشد که این درخت این مساله این ویژگی را ندارد. درخت AVL لازم نیست که کامل باشد. این همه تفاوت با این درخت صورت مساله.
شما برای پیدا کردن گره ای که می خواهید آن را حذف کنید باید با on تمام برگها رو چک کنید.
بله این درخت شبیه به درخت انتخابی است.