تالار گفتمان مانشت

نسخه‌ی کامل: آزمون نهم مدرسان شریف - درخت جست و جوی دودویی
شما در حال مشاهده‌ی نسخه‌ی متنی این صفحه می‌باشید. مشاهده‌ی نسخه‌ی کامل با قالب بندی مناسب.
با عرض سلام
دوستان یه راهنمایی در مورد سوال زیر می فرمایید لطفا؟
قسمت "ب" گفته یافتن تعداد عنصر x ! مگه توی BST کلید ها منحصر به فرد نیستند ؟ کلید تکراری که نداریم !
جواب گزینه ی ۱
با تشکر
تو سوال گفته برای هر گره تعداد عناصرشو ذخیره میکنیم. مثلا گره b کنارش یه عدد 5 گذاشته یعنی وقتی داشتیم درخت دودوییو میکشیدیم هردفعه یه b دیدیم یکی به این عدد اضافه کردیم. خب حالا تو ب گفته یافتن این عدد با چه مرتبه ایه؟! ما باید بریم اون گره x رو پیدا کنیم ،جستجو توی bst متوازن مثل avl از مرتبه log n هست.حالا وقتی گره رو پیدا کردیم عددشو برمیداریم. که همون تعداد عنصر x هست. در کل مرتبش شدlog n
واسه الف استدلالمو نمیدونم درسته یا نه.یکم روش فکر کنم اگه درست شد میگم.
(30 فروردین 1396 01:35 ب.ظ)*tarannom* نوشته شده توسط: [ -> ]تو سوال گفته برای هر گره تعداد عناصرشو ذخیره میکنیم. مثلا گره b کنارش یه عدد ۵ گذاشته یعنی وقتی داشتیم درخت دودوییو میکشیدیم هردفعه یه b دیدیم یکی به این عدد اضافه کردیم. خب حالا تو ب گفته یافتن این عدد با چه مرتبه ایه؟! ما باید بریم اون گره x رو پیدا کنیم ،جستجو توی bst متوازن مثل avl از مرتبه log n هست.حالا وقتی گره رو پیدا کردیم عددشو برمیداریم. که همون تعداد عنصر x هست. در کل مرتبش شدlog n

مرسی دوست عزیز
لطف می کنید قسمت "الف" رو هم بی زحمت توضیح بدید ؟
خیلی سپاسگزارم
لینک مرجع