فرض کنید صد کلید یک تا صد را به یک درخت جستجوی دودویی اضافه کردیم . ترتیب اضافه شدن کلیدها معلوم نیست اما احتمال تمام حالات ترتیبهای اضافه شدن کلیدها باهم برابر است. با چه احتمالی در روند اضافه شدن کلیدها به درخت کلیدهای ۴ و ۹ باهم مقایسه می شوند. درصورتیکه اولین کلید اضافه شده ۴۳ باشد؟
اینجا باید دنبال حالتی بگردیم که کلید های ۴و ۹ با هم مقایسه نشوند(از احتمالات کمک میگیریم )و اون وقتی هستش که کلید ۴ فرزند چپ گره و ۹ فرزند راست همان گره باشد(چون bst است)حالا باید دنبال پدر این دو گره گشت این گره‌ها ۵و۶و۷و۸ هستند از ۴ بزرگتر ولی از ۹ کوچکترند خب حالا ۴ عدد داریم دوتا هم ۴و ۹ هستند در کل میشه ۶ تا عدد و بقیه از احتمال
فرض میکنیم انتخاب ۴ =a
انتخاب ۹=b
a=1/6
b=1/6
چون a, b ناسازگارند پس احتمال اشتراک آنها ۰ است
داریم:
p(a+b)=a(a)+p(b)
۱/۶+۱/۶=۱/۳
منم این سوال رو متوجه نشدم
دوستی اومدن و درست و مفصل هم توضیح دادن
بعد کلی دعوا به کردن و بعد از درگیری با یک عضو دیگه پاسخ شون رو پاک کردن
لطفا دوستانی که متوجه شدن کمی واضح‌تر توضیح بدن
رویکرد حل رو متوجه شدم.
باید حالاتی رو پیدا کنیم که ۴ در زیردرخت چپ و ۹ در زیر درخت راست قرار بگیره و احتمال اش رو از ۱ کم کنیم.
اما توضیحاتی که دوستمون این بالا دادن به نظر من کل حالات رو دربرنمی گیره
خوب ما باید دنبال حالتهایی باشیم که ۴و۹ بعد از ۵و۶و۷و۸ وارد نشن.(طبق توضیحی که دوستمون delta دادن)
یعنی باید ۴و۹ قبل از ۵و۶و۷و۸ وارد بشن و این میشه ۱/۳ کل حالات.
دلیلش رو هم دوستی که قبلا پاسخ داده بودند گفتند که به خاطر اینه که ۲ عدد میخوان قبل از ۴ عدد وارد بشن میشه ۱/۳ و ربطی به تعداد کل اعداد یعنی ۴۲ عددی که در سمت چپ ریشه هستند نداره.
و این که گفته ریشه ۴۳ است فقط برای این است که بدانیم ریشه عددی است که ۴و۹ هر دو در یک طرف آن میافتند.
در ضمن نیازی نیست که ۴و۹ بلافاصله بعد از هم ظاهر شوند و مثلا ۴و۱۰و۹ قابل قبول است و به خاطر همین نمیتوانیم بگوییم ۴و۹ را با هم در نظر میگیریم چون لزومی ندارد که کنار هم باشند.
امیدوارم متوجه شده باشید.
(۱۶ بهمن ۱۳۸۹ ۰۹:۳۶ ب.ظ)afagh1389 نوشته شده توسط: خوب ما باید دنبال حالتهایی باشیم که ۴و۹ بعد از ۵و۶و۷و۸ وارد نشن.(طبق توضیحی که دوستمون delta دادن)
قبلش چطور؟ اگر هردو قبل از ۵-۶-۷-۸ هم وارد بشن مث اینه که هردو بعدش وارد بشن. نه؟
نقل قول: یعنی باید ۴و۹ قبل از ۵و۶و۷و۸ وارد بشن و این میشه ۱/۳ کل حالات.
دلیلش رو هم دوستی که قبلا پاسخ داده بودند گفتند که به خاطر اینه که ۲ عدد میخوان قبل از ۴ عدد وارد بشن میشه ۱/۳ و ربطی به تعداد کل اعداد یعنی ۴۲ عددی که در سمت چپ ریشه هستند نداره.
و این که گفته ریشه ۴۳ است فقط برای این است که بدانیم ریشه عددی است که ۴و۹ هر دو در یک طرف آن میافتند.
در ضمن نیازی نیست که ۴و۹ بلافاصله بعد از هم ظاهر شوند و مثلا ۴و۱۰و۹ قابل قبول است و به خاطر همین نمیتوانیم بگوییم ۴و۹ را با هم در نظر میگیریم چون لزومی ندارد که کنار هم باشند.
امیدوارم متوجه شده باشید.
بقیه اش واضح بود ممنونم آفاق
(۱۶ بهمن ۱۳۸۹ ۱۰:۰۱ ب.ظ)bijibuji نوشته شده توسط:منظورتون رو نفهمیدم خوب اگه هر دو بعد از ۵و۶و۷و۸ وارد بشن مثلا فرض کنیم هر دو بعد از ۷ وارد بشن(16 بهمن ۱۳۸۹ ۰۹:۳۶ ب.ظ)afagh1389 نوشته شده توسط: خوب ما باید دنبال حالتهایی باشیم که ۴و۹ بعد از ۵و۶و۷و۸ وارد نشن.(طبق توضیحی که دوستمون delta دادن)
قبلش چطور؟ اگر هردو قبل از ۵-۶-۷-۸ هم وارد بشن مث اینه که هردو بعدش وارد بشن. نه؟
اونوقت ۹ سمت راست ۷ قرار میگیره و ۴ سمت چپ ۷ و دیگه با هم مقایسه نمیشن.
البته من فکر میکنم که اگه یکی قبل از ۵و۶و۷و۸ بیاد و دیگری بعد از ۵و۶و۷و۸ بیاد باز هم مشکلی پیش نمیاد. چون مثلا اگه ۴ قبل از ۷ و ۹ بعد از ۷ بیاد ۷و۹ هر دو سمت راست ۴ قرار میگیرند و باز هم ۴و۹ با هم مقایسه میشوند.
پس تنها حالتی که مشکل ساز است این است که ۹و۴ هر دو بعد از ۵و۶و۷و۸ وارد شوند.
حیف که خودشون نیستند توضیح بدن!