با عرض سلام
دوستان یه راهنمایی در مورد سوال زیر می فرمایید لطفا؟
قسمت "ب" گفته یافتن تعداد عنصر x ! مگه توی BST کلید ها منحصر به فرد نیستند ؟ کلید تکراری که نداریم !
جواب گزینه ی ۱
با تشکر
تو سوال گفته برای هر گره تعداد عناصرشو ذخیره میکنیم. مثلا گره b کنارش یه عدد ۵ گذاشته یعنی وقتی داشتیم درخت دودوییو میکشیدیم هردفعه یه b دیدیم یکی به این عدد اضافه کردیم. خب حالا تو ب گفته یافتن این عدد با چه مرتبه ایه؟! ما باید بریم اون گره x رو پیدا کنیم ،جستجو توی bst متوازن مثل avl از مرتبه log n هست.حالا وقتی گره رو پیدا کردیم عددشو برمیداریم. که همون تعداد عنصر x هست. در کل مرتبش شدlog n
واسه الف استدلالمو نمیدونم درسته یا نه.یکم روش فکر کنم اگه درست شد میگم.
(۳۰ فروردین ۱۳۹۶ ۰۱:۳۵ ب.ظ)*tarannom* نوشته شده توسط: تو سوال گفته برای هر گره تعداد عناصرشو ذخیره میکنیم. مثلا گره b کنارش یه عدد ۵ گذاشته یعنی وقتی داشتیم درخت دودوییو میکشیدیم هردفعه یه b دیدیم یکی به این عدد اضافه کردیم. خب حالا تو ب گفته یافتن این عدد با چه مرتبه ایه؟! ما باید بریم اون گره x رو پیدا کنیم ،جستجو توی bst متوازن مثل avl از مرتبه log n هست.حالا وقتی گره رو پیدا کردیم عددشو برمیداریم. که همون تعداد عنصر x هست. در کل مرتبش شدlog n
مرسی دوست عزیز
لطف می کنید قسمت "الف" رو هم بی زحمت توضیح بدید ؟
خیلی سپاسگزارم