انجمنصفحه اولجستجوی انجمن

[ali.majed.ha]

با عرض سلام
دوستان یه راهنمایی در مورد سوال زیر می فرمایید لطفا؟
قسمت "ب" گفته یافتن تعداد عنصر x ! مگه توی BST کلید ها منحصر به فرد نیستند ؟ کلید تکراری که نداریم !
جواب گزینه ی ۱
با تشکر

[*tarannom*]

تو سوال گفته برای هر گره تعداد عناصرشو ذخیره میکنیم. مثلا گره b کنارش یه عدد ۵ گذاشته یعنی وقتی داشتیم درخت دودوییو میکشیدیم هردفعه یه b دیدیم یکی به این عدد اضافه کردیم. خب حالا تو ب گفته یافتن این عدد با چه مرتبه ایه؟! ما باید بریم اون گره x رو پیدا کنیم ،جستجو توی bst متوازن مثل avl از مرتبه log n هست.حالا وقتی گره رو پیدا کردیم عددشو برمیداریم. که همون تعداد عنصر x هست. در کل مرتبش شدlog n
واسه الف استدلالمو نمیدونم درسته یا نه.یکم روش فکر کنم اگه درست شد میگم.

[ali.majed.ha]

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

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