دوستان لطفا به این سوال توجه کنید
داده ساختار یک درخت دودویی است که اعداد طبیعی دلخواه x1,...xn در برگها ذخیره می کند. هر گره داخلی درخت دودویی x حاوی بزرگترین مقدار کلید دو فرزندش می باشد کدام یک از اعمال زیر را می توان در
o(1)
انجام داد؟۱ ) حذف ریشه درخت
۲) کاهش مقدار کلید
۳) برگرداندن مقدار دومین بزرگترین عنصر
۴) هیچ کدام
طبق کلید پارسه گزینه ۳ هست به دلیل اینکه دومین بزرگترین حتما فرزند ریشه هست و به یک مقایسه بیشتر نیاز نداریم ..... ولی امکان داره دومین بزرگترین و بزرگترین در عمقهای پایین تر باهم همزاد باشند به نظر من هیچ کدام درسته نظر دوستان؟؟؟
سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
(۱۹ آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.
۷۰
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
(۱۹ آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:70این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
بله درسته ممنون از تذکرتون
، پس احتمالا هیچ کدام گزینه صحیح هست.
(۱۹ آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
(۲۰ آبان ۱۳۹۲ ۰۳:۴۲ ق.ظ)dzzv_13 نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
دوست عزیز احتمالا طراح منظورش این بوده که گره های برگ مرتب نباشن حالا چه بصورت صعودی و یا نزولی وبطور کلی اگه بزرگترین عنصر و دومین بزرگترین عنصر در سطح آخر کنار هم باشن دیگه نمیشه با زمان خطی بهش دسترسی داشت منم با شما هم عقیده هستم.
(۲۰ آبان ۱۳۹۲ ۰۳:۴۲ ق.ظ)dzzv_13 نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
ورودیها برگها هستند و تکراری نیستند
(۲۰ آبان ۱۳۹۲ ۰۹:۴۸ ق.ظ)amin222 نوشته شده توسط:ممنون دوست عزیز ولی حتی اگر نا مرتب در نظر بگیریم باز این جواب درست نیست فرض کنید مثلا ٦ سطح باشه گره برگ ٤٠ و ٧٠ همزاد باشن وبقیه نا مرتب و کوچکتر ٤٠(20 آبان ۱۳۹۲ ۰۳:۴۲ ق.ظ)dzzv_13 نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۵:۱۰ ب.ظ)friends نوشته شده توسط:(19 آبان ۱۳۹۲ ۰۴:۳۳ ب.ظ)misagh01 نوشته شده توسط: سلام اگر منظورتون را درست متوجه شده باشم نظر من هم روی همون گزینه ۳ هست چون اگر در سطوح پایینتر بزرگترین و دومین بزرگترین عنصر با هم همزاد باشند باز هم ما مطمینیم که دومین بزرگترین عنصر در سطح ۲ (فرزند ریشه) هست و نیازی نیست که به سطوح پایینتر نگاه کنیم.۷۰این درخت رو در نظر بگیرید ۴۰ دومین بزرگترین عنصر هست و فرزند ریشه هم نیست...
۲۰ ۷۰
۱۰ ۲۰ ۴۰ ۷۰
دو گره که نباید کلید یکسان داشته باشند
الان این گره های تکراری ۷۰ که گذاشتین چی هستند ؟؟
دوست عزیز احتمالا طراح منظورش این بوده که گره های برگ مرتب نباشن حالا چه بصورت صعودی و یا نزولی وبطور کلی اگه بزرگترین عنصر و دومین بزرگترین عنصر در سطح آخر کنار هم باشن دیگه نمیشه با زمان خطی بهش دسترسی داشت منم با شما هم عقیده هستم.
آخرش جواب چی شد؟
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
(۲۳ آبان ۱۳۹۲ ۱۰:۵۹ ب.ظ)zimenswall نوشته شده توسط: آخرش جواب چی شد؟
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
کلا سوال غلط هست
(۲۴ آبان ۱۳۹۲ ۰۳:۲۷ ق.ظ)friends نوشته شده توسط:(23 آبان ۱۳۹۲ ۱۰:۵۹ ب.ظ)zimenswall نوشته شده توسط: آخرش جواب چی شد؟
در ضمن اگر دو تا بزرگترین ها همزاد هم نباشند و فقط در زیر درخت راست یا چپ ریشه باشند بازهم این مشکل هست.
کلا سوال غلط هست
ممنون. یک سوال به سوالات بازهم غلط پارسه اضافه شد
طبق فرمول باید دومین بزرگترین کلید در محدوده ۱^۲ تا ۱- ۲^۲ (یعنی از گره ۲دوم تا گره سوم باشه) پس قطعا دومین بزرگترین کلید فرزند ریشه هست و نیازی به جست و جو نداره و در زمان( O(1 پیدا میشه
(۲۸ آذر ۱۳۹۲ ۰۳:۱۱ ق.ظ)۲۰۱۳محمد نوشته شده توسط: طبق فرمول باید دومین بزرگترین کلید در محدوده ۱^۲ تا ۱- ۲^۲ (یعنی از گره ۲دوم تا گره سوم باشه) پس قطعا دومین بزرگترین کلید فرزند ریشه هست و نیازی به جست و جو نداره و در زمان( O(1 پیدا میشه
این فرمولی که شما می گین مربوط به درخت heap هست این درخت heap نیست طبق صورت سوال دقت کنید گفته شده گره x1 تا xn برگها هستند پست ۳ رو نگاه کنید یه مثال ساده از این درخت رو نوشتم...بخوام دقیقتر بگم این درخت مثل الگوریتم تورمنت بازی عمل می کنه وبرای به دست اورد دومین max باید کل حریفهای (همزاد ها) max اول یا همون ریشه رو با هم مقایسه کنیم