دوستان لطفا به این سوال توجه کنید
داده ساختار یک درخت دودویی است که اعداد طبیعی دلخواه x1,...xn در برگها ذخیره می کند. هر گره داخلی درخت دودویی x حاوی بزرگترین مقدار کلید دو فرزندش می باشد کدام یک از اعمال زیر را می توان در
o(1)
انجام داد؟
۱ ) حذف ریشه درخت
۲) کاهش مقدار کلید
۳) برگرداندن مقدار دومین بزرگترین عنصر
۴) هیچ کدام
طبق کلید پارسه گزینه ۳ هست به دلیل اینکه دومین بزرگترین حتما فرزند ریشه هست و به یک مقایسه بیشتر نیاز نداریم ..... ولی امکان داره دومین بزرگترین و بزرگترین در عمقهای پایین تر باهم همزاد باشند به نظر من هیچ کدام درسته نظر دوستان؟؟؟
سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه 3 هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح 2 (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
(19 آبان 1392 04:33 ب.ظ)misagh01 نوشته شده توسط: [ -> ]سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
70
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
(19 آبان 1392 05:10 ب.ظ)friends نوشته شده توسط: [ -> ] 70
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
بله درسته ممنون از تذکرتون
، پس احتمالا هیچ کدام گزینه صحیح هست.
(19 آبان 1392 05:10 ب.ظ)friends نوشته شده توسط: [ -> ] (19 آبان 1392 04:33 ب.ظ)misagh01 نوشته شده توسط: [ -> ]سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
70
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری 70 که گذاشتین چی هستند ؟؟
(20 آبان 1392 03:42 ق.ظ)dzzv_13 نوشته شده توسط: [ -> ] (19 آبان 1392 05:10 ب.ظ)friends نوشته شده توسط: [ -> ] (19 آبان 1392 04:33 ب.ظ)misagh01 نوشته شده توسط: [ -> ]سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
70
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
دوست عزیز احتمالا طراح منظورش این بوده که گره های برگ مرتب نباشن حالا چه بصورت صعودی و یا نزولی وبطور کلی اگه بزرگترین عنصر و دومین بزرگترین عنصر در سطح آخر کنار هم باشن دیگه نمیشه با زمان خطی بهش دسترسی داشت منم با شما هم عقیده هستم.
(20 آبان 1392 03:42 ق.ظ)dzzv_13 نوشته شده توسط: [ -> ] (19 آبان 1392 05:10 ب.ظ)friends نوشته شده توسط: [ -> ] (19 آبان 1392 04:33 ب.ظ)misagh01 نوشته شده توسط: [ -> ]سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
70
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
ورودیها برگها هستند و تکراری نیستند
(20 آبان 1392 09:48 ق.ظ)amin222 نوشته شده توسط: [ -> ] (20 آبان 1392 03:42 ق.ظ)dzzv_13 نوشته شده توسط: [ -> ] (19 آبان 1392 05:10 ب.ظ)friends نوشته شده توسط: [ -> ] (19 آبان 1392 04:33 ب.ظ)misagh01 نوشته شده توسط: [ -> ]سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
70
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
دوست عزیز احتمالا طراح منظورش این بوده که گره های برگ مرتب نباشن حالا چه بصورت صعودی و یا نزولی وبطور کلی اگه بزرگترین عنصر و دومین بزرگترین عنصر در سطح آخر کنار هم باشن دیگه نمیشه با زمان خطی بهش دسترسی داشت منم با شما هم عقیده هستم.
ممنون دوست عزیز ولی حتی اگر نا مرتب در نظر بگیریم باز این جواب درست نیست فرض کنید مثلا ٦ سطح باشه گره برگ ٤٠ و ٧٠ همزاد باشن وبقیه نا مرتب و کوچکتر ٤٠
آخرش جواب چی شد؟
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
(24 آبان 1392 03:27 ق.ظ)friends نوشته شده توسط: [ -> ] (23 آبان 1392 10:59 ب.ظ)zimenswall نوشته شده توسط: [ -> ]آخرش جواب چی شد؟
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
کلا سوال غلط هست
ممنون. یک سوال به سوالات بازهم غلط پارسه اضافه شد
طبق فرمول باید دومین بزرگترین کلید در محدوده 1^2 تا 1- 2^2 (یعنی از گره 2دوم تا گره سوم باشه) پس قطعا دومین بزرگترین کلید فرزند ریشه هست و نیازی به جست و جو نداره و در زمان( O(1 پیدا میشه
(28 آذر 1392 03:11 ق.ظ)2013محمد نوشته شده توسط: [ -> ]طبق فرمول باید دومین بزرگترین کلید در محدوده ۱^۲ تا ۱- ۲^۲ (یعنی از گره ۲دوم تا گره سوم باشه) پس قطعا دومین بزرگترین کلید فرزند ریشه هست و نیازی به جست و جو نداره و در زمان( O(1 پیدا میشه
این فرمولی که شما می گین مربوط به درخت heap هست این درخت heap نیست طبق صورت سوال دقت کنید گفته شده گره x1 تا xn برگها هستند پست 3 رو نگاه کنید یه مثال ساده از این درخت رو نوشتم...بخوام دقیقتر بگم این درخت مثل الگوریتم تورمنت بازی عمل می کنه وبرای به دست اورد دومین max باید کل حریفهای (همزاد ها) max اول یا همون ریشه رو با هم مقایسه کنیم