====== سوال ۹ ======




**درخت جست‌وجوی دودویی** یک درخت ریشه‌دار $n$ رأسی با ویژگی‌های زیر است:

  * رأس‌ها با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند.
  * هر رأس  __حداکثر__ دو فرزند دارد که یکی ریشه‌ی زیردرخت سمت چپ و دیگری، ریشه‌ی زیردرخت سمت راست است.
  * به ازای هر رأس، شماره‌های تمام رأس‌های زیردرخت سمت چپ آن (در صورت وجود) از شماره‌ی خودش  کوچک‌تر و شماره‌ی تمام رأس‌های زیردرخت سمت راست آن (در صورت وجود) از شماره‌ی خودش بزرگ‌‌تر است.


برای مثال، یک درخت جست‌وجوی دودویی در زیر کشیده‌ایم:


{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۹:untitled104.png |}}


درخت زیر را در نظر بگیرید. در هر مرحله می‌توانیم یک یال در نظر گرفته و شماره‌ی دو رأس آن را جابه‌جا کنیم. کمینه‌ی تعداد مراحل لازم را بیابید، طوری که بتوانیم شکل را به یک درخت جست‌وجوی دودویی تبدیل کنیم.

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۹:untitled105.png |}}

  - 5
  - 6
  - 7
  - 8
  - 9
<راهنمایی>
مجموع فاصله اعداد از مکانی که باید در انتها باشند۱۲ یال است. پس دست کم ۶ جا به جایی نیاز است.  در صورتی می توان کار را با ۶ مرحله انجام داد که در هر مرحله هر دو راس جا به جا شونده به مکان نهایی خود نزدیک شوند
</راهنمایی>
<پاسخ>
 گزینه‌ی ۳ درست است.

ابتدا مثالی با هفت مرحله ارائه می دهیم
۲،۵

۱،۵

۱،۴

۳،۵

۳،۴

۲،۳

۵،۶
حال ثابت میکنیم با کمتر از هفت مرحله نمی شود، مجموع فاصله اعداد از مکانی که باید در انتها باشند۱۲ یال است. پس دست کم ۶ جا به جایی نیاز است. تنها در صورتی می توان کار را با ۶ مرحله انجام داد که در هر مرحله هر دو راس جا به جا شونده به مکان نهایی خود نزدیک شوند که هیچ جا به جایی در مرحله اول این خاصیت را ندارد پس حداقل هفت مرحله نیاز است



</پاسخ>

  * [[سوال ۸|سوال قبل]]
  * [[سوال ۱۰|سوال بعد]]