درخت بازه ای
درخت بازهای یک نوع داده ساختار درختی است که از آن برای ذخیره سازی بازهها استفاده میشود. از قابلیتهای این درخت میتوان به این اشاره کرد که اشتراک یک بازه را با تمام بازه هایی که داریم به دست میآورد. برای مثال، یافتن تمام راههای موجود بر روی یک نقشۀ کامپیوتری درون یک مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این درخت بازه ای است. هدف این داده ساختار این است اگر تعداد بازههای اشتراک $m$ باشد از $O(m+1)$ جواب را به دست آوریم.
نحوه ساخت
فرض کنید مجموعه ای از $n$ بازه داشته باشیم و بخواهیم بر روی آن ها این داده ساختار را پیاده سازی کنیم. برای این کار ابتدا نقطه ای میانی را در نظر میگیریم تا بازه ها به صورت متوازن پخش شوند. حال بازه ها ۳ حالت دارند:
- بازه کامل در سمت راست نقطه ما قرار دارد.
- بازه کامل در سمت چپ نقطه ما قرار دارد.
- بازه نقطه ما را شامل میشود.
در دو حالت اول برای هر طرف به صورت بازگشتی این داده ساختار را میسازیم. برای حالت سوم بازه ها را در یک داده ساختار مانند لیست یک بار به صورت صعودی بر اساس نقطه چپ آن ها قرار میدهیم یک بار هم بر اساس نقطه راست آن ها قرار میدهیم. در نتیجه هزینه ساخت این درخت برابر $O(nlogn)$ است.
جست و جوی یک نقطه در بازه ها
برای این که بازه هایی را که با یک نقطه اشتراک دارند را پیدا کنیم کافی است که از ریشه درخت بازه ای شروع کنیم. اگر نقطه در سمت چپ بازه بود به فرزند سمت چپ میرویم و اگر سمت راست بود به فرزند سمت راست میرویم. همچنین به هر راسی که میرسیم باید اشتراک نقطه با بازه هایی را که در حالت سوم بودند به دست آوریم. برای این قسمت اگر نقطه در چپ محور قرار داشت با استفاده از لیستی که بر اساس نقطه شروع ها پر شده بود میتوان یکی یکی بر روی آن ها حرکت کرد تا جایی که دیگر اشتراک نداشته باشند. اگر نقطه در سمت راست بود همین کار را یر روی لیست دوم انجام میدهیم. در نتیجه در زمان اجرای $O(m+1)$ میتوان خروجی را پیدا کرد.
جست و جوی یک بازه در بازه ها
ابتدا بازه هایی را پیدا میکنیم که نقطه پایان یا نقطه شروعشان در بازه مورد نظر قرار میگیرد. برای این کار همهی بازه ها را اگر در یک داده ساختار درخت دودویی قرار دهیم میتوانیم اشتراک ها را به دست آوریم. حال کافی است بازه هایی را پیدا کنیم که شامل این نقطه میشوند. این قسمت هم مانند حالت پیدا کردن اشتراک نقطه با بازه ها است.