با عرض سلام
دوستان یه راهنمایی در مورد سوال زیر می فرمایید لطفا؟
قسمت "ب" گفته یافتن تعداد عنصر 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
مرسی دوست عزیز
لطف می کنید قسمت "الف" رو هم بی زحمت توضیح بدید ؟
خیلی سپاسگزارم