تالار گفتمان مانشت

این تست از جمله سوالاتی هست که هم می تونه توی الگوریتم بیاد و هم ساختمان . این تست در واقع مقدمه ای بر شروع طراحی الگوریتم در ابتدای مهرماه هست:

[attachment=1218]

به نظر من گزینه 4 میشه چون بدترین حالت اینه که گره های u, v در زیر درخت های متفاوت ریشه( مثلا u چپ و v راست باشه) باشه
که با lg n میشه به ریشه رسید و با lg n از ریشه به گر ه مورد نظر

بله به نظر من هم همین جواب (4) صحیحه چون در بدترین حالت فاطله بین u و v در سمت راست ترین برگ زیر درخت سمت راست و سمت چپ ترین برگ زیر درخت سمت چپ هستند که برای رفتن از u به v باید یک بار به ریشه رفت و بار دیگر از آن به v که 2logn میشه و برابر (O(logn است.

به نظر من گزینه ۲ درسته فرض کنید گره u سمت چپ ترین برگ باشه و v ‌سمت راست ترین
حالا از u شروع میکنیم به پدر آن میرسیم بعد از بررسی پدر باید همزاد u را بررسی کنیم در واقع هر بار که به پدر گره مورد برسی میرسیم باید تمام زیر درخت همزاد را بررسی کنیم و این یعنی در بدترین حالت بررسی کل درخت

پست های قبلی گزینه 2 رو نقض می کنه.

دوست عزیز در پست های قبلی این رو در نظر نگرفته اند که درخت جستجوی دودیی نیست یعنی به راحتی نمیشه در ارتفاع درخت حرکت کرد و وقتی دنبال v میگردیم باید دانه دانه گره ها را بررسی کنیم

یک درخت دودویی کامل، الزاما یک BST نیست! پس برای یافتن مسیر بین دو گره دلخواه در بدترین حالت، کل درخت باید پیمایش شود که میشود گزینه 2!
اگر BST بود میشد 4!