زمان کنونی: ۲۲ آبان ۱۴۰۳, ۰۱:۱۵ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن میتوانید عضو شوید. گزینههای شما (ورود — ثبت نام)
ارسالها: ۱۵۶
تاریخ عضویت: تیر ۱۳۸۹
پاسخهای درست:۱۵ گرایش: سایر وضعیت: پشت کنکوری ارشد مقبولیت: ۱۰۰/۳+ امتیاز تاریخ مانشت: ۵۴۴ رتبه: ۳۳۰
تست ۳: طراحی الگوریتم مهندسی کامپیوتر ۸۹
به نظر من گزینه ۴ میشه چون بدترین حالت اینه که گره های u, v در زیر درخت های متفاوت ریشه( مثلا u چپ و v راست باشه) باشه
که با lg n میشه به ریشه رسید و با lg n از ریشه به گر ه مورد نظر
بله به نظر من هم همین جواب (۴) صحیحه چون در بدترین حالت فاطله بین u و v در سمت راست ترین برگ زیر درخت سمت راست و سمت چپ ترین برگ زیر درخت سمت چپ هستند که برای رفتن از u به v باید یک بار به ریشه رفت و بار دیگر از آن به v که ۲logn میشه و برابر (O(logn است.
من اگر چه بندگی را به خدا رسانده باشم
همه بنده ام خدایا به تو می رسد خدایی
بکشان به عاشقانت که کشی به جرم عشقم
مگرم نه وعده دادی که کشی و بر سر آیی
به نظر من گزینه ۲ درسته فرض کنید گره u سمت چپ ترین برگ باشه و v سمت راست ترین
حالا از u شروع میکنیم به پدر آن میرسیم بعد از بررسی پدر باید همزاد u را بررسی کنیم در واقع هر بار که به پدر گره مورد برسی میرسیم باید تمام زیر درخت همزاد را بررسی کنیم و این یعنی در بدترین حالت بررسی کل درخت
دوست عزیز در پست های قبلی این رو در نظر نگرفته اند که درخت جستجوی دودیی نیست یعنی به راحتی نمیشه در ارتفاع درخت حرکت کرد و وقتی دنبال v میگردیم باید دانه دانه گره ها را بررسی کنیم
یک درخت دودویی کامل، الزاما یک BST نیست! پس برای یافتن مسیر بین دو گره دلخواه در بدترین حالت، کل درخت باید پیمایش شود که میشود گزینه ۲!
اگر BST بود میشد ۴!