زود، تند، حساب کن: حاصل جمع چند است؟

یادآوری: در این نوشته درخت جستجوی دودویی را به اختصار دِرَجد می خوانیم.

پرسش: یک درجد و دو عدد L و R (که L<=R) داده شده اند. برنامه ای بنویسید که مجموع تمام مقادیر درون درخت بین L و R (شامل خود این مقادیر در صورت وجود) را محاسبه نماید.

پاسخ: کار را با یک مثال شروع می کنیم تا مطمین شویم که آن را خوب درک کرده ایم. فرض کنیم که درجد زیر و مقادیر L=19 و R=60 داده شده اند.

آنگاه برنامه باید مقدار 153 (مجموع 25, 30, 45, 53) را برگرداند.

حل مساله را با ارایه یک الگوریتم جستجوی کامل شروع می کنیم. در این پرسش الگوریتم جستجوی دودویی به معنای آن است که کل درخت را پیمایش کنیم و برای هر گره چک کنیم که آیا مقدار در بازه بین L و R می باشد.

اشکال این روش آن است که بسیاری از زیر درخت ها که شامل پاسخ نمی باشند را نیز در آن می پیماییم. درحالیکه مثالا وقتی به گره با مقدار 80 می رسیم می دانیم که عنصری با مقدار بین 19 و 60 در سمت راست آن وجود ندارد. این خاصیت درجد است زیرا تمام عناصر زیر درخت راست یک گره از آن بزرگتر می باشند. این مشاهده ایده یک الگوریتم بهینه را می دهد.

در یک الگوریتم بهینه سه حالت برای مقدار یک گره در نظرمی گیریم:

(۱) مقدار گره کوچکتر از L می باشد. در این صورت از زیر درخت سمت چپ آن صرفنظر می کنیم چون هیچ عنصری بزرگتر از L در آن وجود ندارد. بنابر این کافی است زیر درخت سمت راست آن را برای یافتن مقادیر در بازه بین L و R جستجو کنیم.

(۲) در صورتی که مقدار ریشه بزرگتر از R باشد تنها باید زیر درخت سمت چپ آن را بجوییم و از زیر درخت سمت راست صرفنظر می کنیم.

(۳) چنانچه مقدار ریشه در بازه L  و R باشد آن را به مجموع اعداد بازه L و R اضافه می کنیم و هر دو زیر درخت سمت چپ و راست را برای یافتن مابقی عناصر در بازه داده شده جستجو می کنیم.

این الگوریتم یک تعریف بازگشتی دارد و بنابر این می تواند بصورت بازگشتی پیاده شود. در یک مصاحبه واقعی، با اجرای الگوریتم روی مثال بالا مطمین می شویم که بدرستی عمل می کند. سپس شروع به پیاده سازی می کنیم.

ابتدا برای تابع نام و پارامترهای مناسب انتخاب می کنیم (خط 1). چنانچه مقدار ریشه نال (null) باشد آنگاه مقدار 0 را برمی گردانیم (خطوط 2 و 3). اگر مقدار ریشه بزرگتر از R باشد زیر درخت سمت چپ آن را جستجو می کنیم (خط 4 و 5). در صورتی که مقدار ریشه کمتر از L باشد زیر درخت سمت راست آن را جستجو می کنیم (خط 6 و 7). در غیر این صورت مقدار ریشه را به حاصل محاسبه شده از هر دو زیر درخت سمت چپ اضافه و آن را برمی گردانیم (خطوط 8 و 9).  

این الگوریتم را می توان بصورت غیر بازگشتی، با استفاده از ساختمان داده صف نیز پیاده سازی کنیم. از ساختمان داده صف برای دنبال کردن ریشه زیر درخت هایی که ممکن است مقادیری در بازه مناسب داشته باشند استفاده می شود. تکه کد زیر این کار را انجام می دهد.

در هر دو الگوریتم فوق، با توجه با اینکه حداکثر به اندازه ارتفاع درخت گره نامرتبط را پیمایش می کنیم و مابقی گره ها در بازه R تا L می باشند، در صورتی که L و R خود در بازه مقادیر درخت باشند، پیچیدگی محاسباتی این الگوریتم ((O(log(n) + (R-L می باشد. در بدترین حالت پیچیدگی محاسباتی (O(n می باشد.