- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
گاندولف سال‌های زیادی بود که در جنگل تاریک و دوردست تارایوس زندگی می‌کرد. او همیشه به دنبال ایجاد ساختاری بود که اکتشافات و مشاهده‌های خود از جنگل را بتواند در آن قرار دهد، به‌طوری که علاوه بر قابلیت ذخیره‌سازی، انواع مختلف داده‌هایی که می‌یافت امکان دسترسی راحت‌تر به آنها را بدهد.
سال‌ها جست‌وجوی او بی‌نتیجه بود تا اینکه در سفری کوتاه در جنگل به درختی عجیب برخورد که که هر شاخه آن حداکثر دو زیر شاخه داشتند و این مشاهده کوتاه کافی بود تا ایده‌ای را در ذهن او بپروراند.
پس از این مشاهده او به فکر ایجاد ساختاری افتاد که بتواند انواع داده‌ها را در خود ذخیره کند و افزون بر آن امکان دسترسی سریع‌تر به داده‌ها را به او بدهد.
در یادداشت‌های به‌جای مانده از او ساختار مذکور - که او آنها را درخت دودویی نامید - به صورت زیر توصیف شده است:
درخت دودویی: درخت دودویی یک ساختار داده سلسله‌مراتبی است که از گره‌ها تشکیل شده است. هر گره در یک درخت دودویی می‌تواند حداکثر دو گره فرزند داشته باشد که به نام فرزند چپ و فرزند راست شناخته می‌شوند. این ساختار شبیه الگوی انشعاب یک درخت در دنیای واقعی می‌باشد و برای سازماندهی داده‌ها ایده‌آل است. در اینجا برخی از اصطلاحات ضروری مرتبط با درختان دودویی آورده شده است:
- ریشه: بالاترین گره درخت است که نشان‌دهنده نقطه شروع برای تمام گره‌های دیگر می‌باشد.
- گره والد: هر گره‌ای است که یک یا چند گره فرزند از آن نشأت می‌گیرد.
- گره فرزند: گره‌هایی که به‌طور مستقیم به یک گره والد متصل می‌شوند و شاخه‌های درخت را تشکیل می‌دهند.
- گره برگ: گره‌هایی که فرزند ندارند و به‌عنوان نقاط انتهایی درخت عمل می‌کنند.
خواص درخت دودویی: ساختار درختی دودویی گاندولف به‌عنوان یک پایگاه داده جامع برای موجودات و آیتم‌های جنگل جادویی عمل می‌کند و به این ویژگی‌ها پایبند است:
- حداکثر دو فرزند: هر گره در درخت حداکثر می‌تواند دو فرزند داشته باشد، یکی در سمت چپ و دیگری در سمت راست. این ویژگی تضمین می‌کند که درخت متعادل و کارآمد باقی بماند.
- سازمان سلسله‌مراتبی: گره‌ها به‌صورت سلسله‌مراتبی مرتب شده‌اند و گره ریشه در اوج ساختار قرار دارد. این سازمان امکان ناوبری و دسته‌بندی آسان اطلاعات را فراهم می‌کند.
- ذخیره‌سازی داده‌ها: گره‌های درون درخت دودویی اطلاعات ارزشمندی در مورد اکتشافات جنگل جادویی ذخیره می‌کنند. این اطلاعات معمولاً شامل یک شناسه منحصربه‌فرد، نام و توضیحاتی است که امکان مستندسازی دقیق موجودات و اقلام را فراهم می‌کند. با اجرای این ساختار درختی دوتایی، گاندولف می‌تواند به‌طور موثری شگفتی‌های جنگل جادویی را مدیریت و کشف کند. او به‌راحتی می‌تواند اکتشافات جدید را وارد کند، اطلاعات قدیمی را حذف کند و موجودات یا آیتم‌های خاصی را جست‌وجو کند و تحقیقات خود را در جنگل تاریک بسیار سازماندهی و قابل دسترس‌تر کند.
او برای اینکه داده‌های درون این ساختار منظم‌تر باشند و قرارگیری داده جدید نیز ساده‌تر باشد، یک قانون ساده قرار داد، به این‌گونه که: پس از انتخاب ریشه برای جایگذاری داده جدید در درخت، این شرط برای هر گره چک می‌شود که اگر داده جدید کوچک‌تر از گره مورد بررسی بود، در سمت چپ آن قرار می‌گیرد، و در صورتی که بزرگ‌تر از آن بود، در سمت راست آن قرار می‌گیرد. این شرط تا زمانی که هیچ گره‌ای برای مقایسه وجود نداشته باشد بررسی می‌شود.
برای درک بهتر، در تصویر زیر یک درخت دودویی با اندازه ۹ (تعداد گره‌های درخت) و ارتفاع ۳، با یک گره ریشه که مقدار آن ۸ است، آورده شده است:
به گاندولف برای ایجاد این ساختار کمک کنید تا بتواند داده‌های خود را بهتر و بهینه‌تر ذخیره کند.
در اینجا شرایط لازم برای برنامه شما وجود دارد:
- یک ساختار داده درختی دودویی را پیاده‌سازی کنید که می‌تواند اشیا از انواع مختلف (int یا float یا long long یا string) را ذخیره کند. شما باید از struct برای گره‌ها استفاده کنید.
- تعریف یک تابع جست‌وجو برای یافتن موجودات یا اقلام بر اساس شناسه‌های منحصر به‌فرد آنها.
- ایجاد یک تابع نمایش برای چاپ محتویات درخت به‌ترتیب از سمت چپ‌ترین داده تا سمت راست‌ترین داده.
- برای اینکه بتوانید از داده‌هایی با انواع مختلف استفاده کنید باید از template استفاده کنید.
- در صورتی که داده ورودی از نوع string باشد برای مقایسه بزرگ بودن دو string از مقایسه ASCII CODE حرف اول آنها استفاده می‌شود. در صورت برابر بودن حرف اول، حرف بعدی مقایسه می‌شود. اگر شرایطی ایجاد شد که یک کلمه پیشوند کلمه دیگر باشد، کلمه پیشوند کوچک‌تر در نظر گرفته می‌شود.
- در خط اول ورودی نوع داده‌هایی که در ساختار قرار خواهند گرفت آورده می‌شود.
- در خط بعدی داده ریشه و تعداد داده‌های ورودی داده می‌شود.
- در خط سوم داده‌هایی که قرار است در درخت قرار بگیرند به‌ترتیب داده می‌شوند.
- در هر یک از خط‌های بعدی یکی از دستورات Find value یا Print داده می‌شود.
- در صورت دریافت دستور Exit برنامه تمام می‌شود.
- در خط‌های خروجی در صورت دریافت دستور Print محتویات درخت به‌ترتیب از سمت چپ‌ترین داده تا سمت راست‌ترین داده نمایش داده می‌شود.
- در صورت دریافت دستور Find value اگر value در ساختار یافت شود
Foundو اگر یافت نشودNot Foundبه‌عنوان خروجی داده می‌شود.
int
8 9
10 3 6 14 13 7 4 1
Find 6
Find 5
Print
Exit
Found
Not Found
1 3 4 6 7 8 10 13 14