سوال ۹
درخت جستوجوی دودویی یک درخت ریشهدار $n$ رأسی با ویژگیهای زیر است:
- رأسها با اعداد ۱ تا $n$ شمارهگذاری شدهاند.
- هر رأس حداکثر دو فرزند دارد کهیکی ریشهی زیردرخت سمت چپ و دیگری، ریشهی زیردرخت سمت راست است.
- به ازای هر رأس، شمارههای تمام رأسهای زیردرخت سمت چپ آن (در صورت وجود) از شمارهی خودش کوچکتر و شمارهی تمام رأسهای زیردرخت سمت راست آن (در صورت وجود) از شمارهی خودش بزرگتر است.
برای مثال، یک درخت جستوجوی دودویی در زیر کشیدهایم:
درخت زیر را در نظر بگیرید. در هر مرحله میتوانیم یک یال در نظر گرفته و شمارهی دو رأس آن را جابهجا کنیم. کمینهی تعداد مراحل لازم را بیابید، طوری که بتوانیم شکل را بهیک درخت جستوجوی دودویی تبدیل کنیم.
- 5
- 6
- 7
- 8
- 9
راهنمایی
مجموع فاصله اعداد از مکانی که باید در انتها باشند۱۲ یال است. پس دست کم ۶ جا به جایی نیاز است. در صورتی میتوان کار را با ۶ مرحله انجام داد که در هر مرحله هر دو راس جا به جا شونده به مکان نهایی خود نزدیک شوند
پاسخ
گزینهی ۳ درست است.
ابتدا مثالی با هفت مرحله ارائه میدهیم ۲،۵
۱،۵
۱،۴
۳،۵
۳،۴
۲،۳
۵،۶ حال ثابت میکنیم با کمتر از هفت مرحله نمی شود، مجموع فاصله اعداد از مکانی که باید در انتها باشند۱۲ یال است. پس دست کم ۶ جا به جایی نیاز است. تنها در صورتی میتوان کار را با ۶ مرحله انجام داد که در هر مرحله هر دو راس جا به جا شونده به مکان نهایی خود نزدیک شوند که هیچ جا به جایی در مرحله اول این خاصیت را ندارد پس حداقل هفت مرحله نیاز است