حل تشریحی سوال شماره 52 ساختمان داده‌ها

فرض کنید یک درخت دودویی جست و جو با n گره داریم. به ازای گره u از این درخت، وزن آن را تعداد گره‌ها در زیر درخت به ریشه u ( شامل u) در نظر بگیرید. میدانیم در درخت فوق به ازای هر گره داخلی u نسبت وزن فرزند چپ و فرزند راست حداقل 0/5 و حداکثر 2 است. بهترین کران بالا برای زمان جست و جو در این درخت در بدترین حالت، در بین گزینه‌ها کدام است؟ ( مبنای لگاریتم‌ها 2 است)