المپدیا

درخت بازه ای

درخت بازه‌ای یک نوع داده ساختار درختی است که از آن برای ذخیره سازی بازه‌ها استفاده می شود. از قابلیت های این درخت می توان به این اشاره کرد که اشتراک یک بازه را با تمام بازه هایی که داریم به دست می آورد. برای مثال، یافتن تمام راه‌های موجود بر روی یک نقشۀ کامپیوتری درون یک مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این درخت بازه ای است. هدف این داده ساختار این است اگر تعداد بازه های اشتراک $m$ باشد از $O(m+1)$ جواب را به دست آوریم.

نحوه ساخت

فرض کنید مجموعه ای از $n$ بازه داشته باشیم و بخواهیم بر روی آن ها این داده ساختار را پیاده سازی کنیم. برای این کار ابتدا نقطه ای میانی را در نظر می گیریم تا بازه ها به صورت متوازن پخش شوند. حال بازه ها ۳ حالت دارند:

1. بازه کامل در سمت راست نقطه ما قرار دارد.
2. بازه کامل در سمت چپ نقطه ما قرار دارد.
3. بازه نقطه ما را شامل می شود.

در دو حالت اول برای هر طرف به صورت بازگشتی این داده ساختار را می سازیم. برای حالت سوم بازه ها را در یک داده ساختار مانند لیست یک بار به صورت صعودی بر اساس نقطه چپ آن ها قرار می دهیم یک بار هم بر اساس نقطه راست آن ها قرار می دهیم. در نتیجه هزینه ساخت این درخت برابر $O(nlogn)$ است.

جست و جوی یک نقطه در بازه ها

برای این که بازه هایی را که با یک نقطه اشتراک دارند را پیدا کنیم کافی است که از ریشه درخت بازه ای شروع کنیم. اگر نقطه در سمت چپ بازه بود به فرزند سمت چپ می رویم و اگر سمت راست بود به فرزند سمت راست می رویم. همچنین به هر راسی که می رسیم باید اشتراک نقطه با بازه هایی را که در حالت سوم بودند به دست آوریم. برای این قسمت اگر نقطه در چپ محور قرار داشت با استفاده از لیستی که بر اساس نقطه شروع ها پر شده بود می توان یکی یکی بر روی آن ها حرکت کرد تا جایی که دیگر اشتراک نداشته باشند. اگر نقطه در سمت راست بود همین کار را یر روی لیست دوم انجام می دهیم. در نتیجه در زمان اجرای $O(m+1)$ می توان خروجی را پیدا کرد.

جست و جوی یک بازه در بازه ها

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