درخت بازه

در علوم کامپیوتر، درخت بازه‌ای یک داده ساختار مرتب درختی برای نگهداری و ذخیره‌سازی بازه‌ها می‌باشد. می‌توان گفت این از درخت این امکان را فراهم می‌سازد تا همۀ بازه‌هایی را که با یک بازه یا نقطۀ خاص اشتراک دارند پیدا کنیم. درخت بازه‌ای به‌طور معمول برای پنجره دار کردن پرس و جوها به کار می‌رود. برای مثال، یافتن تمام راه‌های موجود بر روی یک نقشۀ کامپیوتری درون یک دید مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این داده ساختار، از درخت بخشی است.
راه حل بدیهی این است که تمام بازه‌ها را ملاقات کرده و امتحان کنیم که آیا با نقطه یا بازه داده شده اشتراک دارند یا نه، که به theta(n) زمان نیاز دارد. (که n همان تعداد بازه‌های موجود در مجموعه است) از آنجایی که یک پرسش ممکن است تمام بازه‌ها را برگرداند، به‌طور مثال، اگر پرسش مورد نظر یک بازۀ بزرگ باشد که با همۀ بازه‌های موجود در مجموعه اشتراک داشته باشد، این به صورت مجانبی بهینه است؛ اگر که ما از الگوریتم‌های حساس به خروجی که در آن‌ها زمان اجرا بر اساس m (که همان تعداد بازه‌های تولید شده توسط پرس و جوست) بیان می‌شود استفاده کنیم می‌توانیم این فرایند را بهبود ببخشیم. درخت‌های بازه‌ای پویا هستند. آن‌ها اجازه درج و حذف بازه‌ها را می‌دهند. آن‌ها پرس و جو را در زمان O(logn) انجام می‌دهند. این در حالی است که زمان پیش پردازش برای ساخت این داده ساختار از O(nlogn) است (ولی فضای مصرف شده از O(n) است). اگر انتهای بازه‌ها در محدودۀ کوچکی قرار داشته باشند (مثلاً محدوده [1,...,O(n)])، داده ساختارهای سریع‌تری با زمان پیش پردازش O(n) و زمان پرس و جوی O(1+m) وجود دارند که m بازه (شامل یک نقطه پرس و جو) را گزارش می‌کنند.

دورنمای درخت بازه‌ی 1 بعدی

دورنمای درخت بازه‌ی چند بعدی

عملکرد ساده

در یک حالت ساده، بازه‌ها با هم هیچ گونه اشتراکی ندارند و می‌توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان O(logn) پرس و جو شوند. این در حالی است که با وجود اشتراک‌های دلخواه میان بازه‌ها، به هیچ عنوان امکان مقایسه دو بازه برای درج در درخت وجود ندارد. زیرا مرتب سازی‌ها بر حسب نقاط شروع یا پایان ممکن است متفاوت باشد. یک عملکرد ساده این خواهد بود که دو درخت موازی بسازیم. یکی مرتب شده بر حسب نقاط شروع و دیگری مرتب شده بر حسب نقاط انتهای هر بازه. این کار اجازۀ رها کردن نصف درخت را در O(logn) می‌دهد ولی نتیجه‌ها باید ادغام شوند که به O(n) زمان نیاز دارد. این راه حل به ما پرس و جوهایی در زمان O(n) = O(n + logn) می‌دهد که بهتر از راه حل بدیهی نیست.

درخت بازه‌ای مرکزی

پرس و جوها به زمان o(m + log(n)) نیاز دارند که در آن n تعداد کل بازه‌ها و m تعداد نتایج گزارش شده‌است. ساخت داده ساختار نیز به o(nlogn) زمان و O(n) فضا نیاز دارد.

ساختار

به ما یک مجموعه n تایی از بازه‌ها در خط اعداد داده می‌شود و ما می خواهیم یک داده ساختار بسازیم که بتواند به صورت مؤثری همه بازه‌هایی را که با یک نقطه یا بازه اشتراک دارند بازیابی کند.
ما با مشخص کردن محدوده کل بازه‌ها و تقسیم کردن آن در x_center (در عمل، x_center باید مشخص شود تا درخت را نسبتاً متعادل نگه داریم) شروع می کنیم. این فرایند سه مجموعه از بازه‌ها را تولید می‌کند: 1. بازه‌هایی که کاملاً در سمت چپ x_center قرار می‌گیرند که ما آن‌ها را S_left نام‌گذاری می‌کنیم.
2. بازه‌هایی که کاملاً در سمت راست x_center قرار می‌گیرند که ما آن‌ها را S_right نام‌گذاری می‌کنیم.
3. آنهایی که با x_center اشتراک دارند که ما آن‌ها را S_center می‌نامیم.
بازه‌های S_left و S_rightنیز به طریق مشابه به صورت بازگشتی تقسیم می‌شوند تا زمانی که هیچ بازه‌ای باقی نماند.
بازه‌هایی از S_center که با نقطۀ مرکزی تلاقی دارند در یک داده ساختار جداگانه مرتب می‌شوند که به گره‌های درخت بازه‌ای پیوند داده شده‌است. این داده ساختار از دو لیست تشکیل شده‌است:
یکی شامل همه بازه‌هایی که بر حسب نقاط شروع‌شان مرتب شده‌اند و دیگری شامل همۀ بازه‌هایی که برحسب نقاط پایانشان مرتب شده‌اند. نتیجه، یک درخت ثالث است که هر گره شامل موارد زیر است:
1. یک نقطه مرکزی
2. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت چپ نقطۀ مرکزی قرار می‌گیرند.
3. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت راست نقطۀ مرکزی قرار می‌گیرند.
4. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس نقطۀ شروع‌شان مرتب شده‌اند.
5. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس نقطۀ پایان‌شان مرتب شده‌اند.

اشتراکی

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

با یک بازه

اول می‌توانیم حالتی را که یک بازه R به عنوان ورودی داده می‌شود به حالت ساده‌تر که در آن یک نقطه به عنوان ورودی داده شده‌است کاهش دهیم. در ابتدا همۀ بازه‌هایی را که نقطۀ شروع یا پایان‌شان در درون بازۀ ورودی R قرار دارد، با استفاده از یک درخت جداگانه می‌یابیم. در حالت یک بعدی می‌توانیم از یک درخت ساده شامل همۀ نقاط شروع و پایان در مجموعۀ بازه‌ها استفاده کنیم که هرکدام شامل یک نشانه‌گر به بازۀ مربوط به آن است.
یک جستجوی دودویی در زمان O(logn) برای شروع و پایان R، کمینه و بیشینۀ نقاطی را که باید در نظر گرفته شوند مشخص می‌کند. هر نقطه با این محدوده به تمام بازه‌هایی که با محدودۀ مورد نظر ما تلاقی دارند ارجاع می‌دهد و به لیست نتیجه اضافه می‌شود. باید توجه شود که از ایجاد تکرار جلوگیری شود، زیرا ممکن است هم شروع و هم پایان یک بازه با R باشد. این کار را می‌توان با استفاده از یک پرچم دودویی بر روی هر بازه برای مشخص کردن اینکه این بازه به مجموعۀ نتیجه اضافه شده‌است یا نه، انجام داد.
تنها بازه‌هایی که هنوز در نظر گرفته نشده‌اند بازه‌هایی هستند که با R تلاقی دارند ولی نقاط پایان‌شان درون R نیست، به عبارت دیگر، بازه‌هایی که آن را در بر می‌گیرند. برای پیدا کردن آن‌ها ما هر نقطه در درون را در نظر می‌گیریم و از الگوریتم زیر استفاده می‌کنیم تا همۀ بازه‌هایی را که با آن نقطه اشتراک دارند بیابیم. (دوباره مواظب باشید که تکرارها را حذف کنید)

با یک نقطه

مثال یک درخت بازه‌ی 1 بعدی - هر راس غیربرگ ماکزیمم مقدار زیردرخت سمت چپ خود را ذخیره میکند.

این فرایند در واقع یافتن همه بازه‌های موجود در درخت است که با یک نقطه x داده شده اشتراک دارند. درخت به همان شیوه پیمایش یک درخت مرسوم دودویی پیمایش می‌شود، ولی با کارآیی بیشتر برای بازه‌هایی که با نقطۀ مرکزی در هر گره تلاقی دارند.
برای هر گره درخت، x با x_center مقایسه می‌شود، یعنی همان نقطۀ میانی که برای ساخت گره در بالا استفاده شده‌است. اگر x از x_center کوچک‌تر باشد، چپ‌ترین مجموعه از بازه‌ها S_left در نظر گرفته می‌شود. اگر x از x_center بزرگ‌تر باشد، راست‌ترین مجموعه از بازه‌ها S_right در نظر گرفته می‌شود.
همین طور که هر گره پردازش می‌شود، وقتی ما درخت را از ریشه به یک برگ می‌پیماییم، محدوده‌های موجود در S_center آن پردازش می‌شوند. اگر x از x_center کوچک‌تر باشد، ما می‌دانیم که تمام بازه‌های موجود s_center بعد x تمام می‌شوند یا اینکه اصلاً با x_center برخورد ندارند. بنابراین ما تنها به یافتن بازه‌هایی از s_centerنیاز داریم که قبل از x شروع می‌شود. ما توانیم در مورد لیست‌های s_center که تاکنون ساخته شده‌اند بحث کنیم. از آنجایی که ما در این سناریو تنها به شروع بازه‌ها اهمیت می‌دهیم، می‌توانیم در مورد لیست مرتب شده بر اساس شروع بازه‌ها بحث کنیم. فرض کنید ما در لیست نزدیک‌ترین عددی که بزرگ‌تر از x نیست را بیابیم. تمام محدوده‌ها از شروع لیست تا آن نقطه یافته شده با x تلاقی دارند، چون قبل از x شروع شده و بعد از x تمام می‌شوند. (همان طور که می‌دانیم به علت این است که با x_center که بزرگ‌تر از x است تلاقی دارند) بنابراین می‌توانیم شروع به شماره‌گذاری بازه‌های موجود در لیست کنیم تا زمانی که مقدار نقطه پایانی از x بیشتر شود.
همچنین اگر x از x_center بزرگ‌تر باشد، ما می‌دانیم که همۀ بازه‌های موجود در s_center باید قبل از x شروع شوند پس ما بازه‌هایی را که بعد از x پایان می‌یابند به وسیلۀ لیستی که بر اساس پایان بازه‌ها مرتب شده‌است می‌یابیم. اگر x دقیقاً منطبق بر x_center باشد، تمام فواصل را می‌توان بدون پردازش بیشتر به نتایج اضافه کرد و پیمایش درخت می‌تواند متوقف شود.

تفکر رایانشی

ابعاد بالاتر

مثال یک درخت بازه‌ی 3 بعدی

ساختمان داده درخت را می‌توان با پرس و جو و زمان ساخت یکسان و فضای O(nlogn) به ابعاد بالاتر n تعمیم داد.
اول یک درخت محدوده در ابعاد N ساخته شده‌است که اجازه بازیابی کارآمد از تمام فواصل با شروع و پایان نقاط در داخل منطقۀ پرس و جو Rرا می‌دهد. هنگامی که تمام بازه‌های مربوطه یافت شدند، تنها چیزی که باقی می‌ماند آن بازه‌هایی است که ناحیه را بعضی ابعاد در بر می‌گیرند. برای پیدا کردن این همپوشانی‌ها، N درخت بازه‌ای به وجود می‌آیند و یک محور متقاطع با R برای هرکدام پرس و جو می‌شود. برای مثال، در دو بعد، پایین مربع R (یا هر خط افقی متقاطع با R) در برابر درخت بازه‌ای ساخته شده برای محور افقی پرس و جو می‌شود. به همین ترتیب سمت چپی (یا هر خط عمودی متقاطع با R) در برابر درخت بازه‌ای ساخته شده بر محور عمودی پرس و جو می‌شود.
هر درخت بازه‌ای به یک چیز اضافه در ابعاد بالاتر نیز نیاز دارد. در هر گره که ما آن را در درخت پیمایش می‌کنیم برای پیدا کردن تلاقی‌ها x با s_center مقایسه می‌شود. به جای دو لیست مرتب شده از بازه‌ها که در حالت یک بعدی مورد استفاده قرار می‌گرفت یک درخت محدوده ساخته می‌شود. این امکان بازیابی کارآمد تمام بازه‌های موجود در s_center را (که با ناحیه R تلاقی دارند) فراهم می‌سازد.

حذف

اگر پس از حذف یک بازه از درخت، گره شامل آن بازه شامل هیچ بازه دیگری نباشد، آن گره ممکن است از درخت حذف شود. این فرایند پیچیده‌تر از عملیات حذف در یک درخت معمولی دودویی است. یک بازه ممکن است با مرکز چند گره در درخت تلاقی داشته باشد. از آنجایی که هر گره بازه‌هایی را که با آن تلاقی دارند ذخیره می‌کند، به همراه تمام بازه‌های به‌طور کامل سمت چپ نقطۀ مرکز آن در زیر درخت سمت چپ و به‌طور مشابه برای زیر درخت راست. این نتیجه می‌دهد که هر بازه از بین بازه‌هایی که با مرکز آن‌ها تلاقی دارد در نزدیک‌ترین گره به ریشه ذخیره می‌شود.
عملیات حذف عادی در یک درخت دودویی (برای حالتی که گره در حال حذف شدن دارای دو فرزند باشد) شامل ارتقاء یک گره دورتر از ریشه به جایگاه گره در حال حذف است (معمولاً چپ‌ترین درخت زیردرخت راست یا راست‌ترین درخت زیر درخت چپ). به عنوان یک نتیجه این ارتقاء، بعضی از گره‌هایی که بالای گره ارتقاء یافته بودند به نوادگان آن تبدیل خواهند شد. لازم است که این گره‌ها را برای بازه‌هایی که با گره ارتقاء یافته تلاقی دارند نیز جستجو کنیم و آن بازه‌ها را به داخل گره‌های ارتقاء یافته منتقل کنیم. در نتیجه این ممکن است باعث ایجاد گره‌های خالی جدیدی شود که دوباره طبق همان الگوریتم باید حذف شوند.

حذف گره به همراه دو فرزند از یک درخت جستجوی باینری با استفاده از عملیات میانترتیبی

ایجاد تعادل

همان مسائلی که بر روی عملیات حذف تأثیر می‌گذارند، بر روی عملیات چرخش نیز تأثیر می‌گذارند. چرخش باید ثابتی را که بازه‌ها ذخیره شده‌اند تا حد امکان نزدیک به ریشه نگه دارد.

درخت افزوده

هم درج و هم حذف از O(logn) زمان می‌برند، که n همان تعداد کل بازه‌هاست.
از یک درخت ساده مرتب استفاده کنید. برای مثال یک درخت جستجوی دودویی یا یک درخت خود-متعادل جستجوی دودویی، که درخت بر اساس نقاط پایین بازه‌ها مرتب شده‌است و یک توضیح اضافه به هر گره اضافه شده‌است که ماکزیمم نقاط بالای بازه‌ها را در زیر درخت‌های آن نگه می‌دارد. به دست آوردن این صفت در طی تنها O(h) مرحله هنگام حذف یا درج یک گره کار ساده‌ای است، که h همان ارتفاع گره درج یا حذف شده به وسیله به روز رسانی همۀ اجداد گره از پایین به بالا در درخت می‌باشد. به علاوه، چرخش‌های درخت که در حذف و درج مورد استفاده قرار می‌گرفت، ممکن است نیاز به به روز رسانی قسمت بالای گره‌های مورد تأثیر داشته باشد.
در حال حاضر مشخص است که دو بازه A و B تلاقی دارند اگر و تنها اگر A.low ≤ B.high و A.high ≥ B.low. هنگام جستجوی درخت‌ها برای یافتن گره‌هایی که با یک بازه تلاقی دارند، شما می‌توانید بلافاصله از موارد زیر صرف نظر کنید:

• همه گره‌هایی که در سمت راست گره‌هایی قرار دارند که مقدار پایین آن‌ها از پایان بازه داده شده گذشته‌است.
• همه گره‌هایی که ماکزیمم مقدار بالای آن‌ها زیر نقطه شروع بازه داده شده قرار دارد.

با مرتب کردن بازه‌ها ابتدا بر اساس مقدار پایین و سپس مقدار بالا یک ترتیب کلی را می‌توان برای بازه‌ها تعریف کرد. این مرتب‌سازی برای جلوگیری از درج بازه‌های تکراری در درخت در O(logn) می‌تواند در مقابل زمان o(k + logn) لازم برای یافتن تکرارها هنگامی کهk بازه با یک بازه جدید تلاقی دارند، مورد استفاده قرار گیرد.
مثال Java :
اضافه کردن یک بازه به درخت
public void add(Interval i) {

    put(i, i.getEnd());

}
مثال Java : جستجو کردن یک نقطه یا بازه در درخت برای جستجو کردن یک بازه، باید درخت را پیمایش کرده و شاخه‌هایی را که نمی‌توانند شامل چیزهایی که شما به دنبال آن هستید باشند حذف کنید. حالت ساده جستجوی یک نقطه است:
// Search for all intervals which contain "p", starting with the

// node "n" and adding matching intervals to the list "result"
public void search(IntervalNode n, Point p, List<Interval> result) {
    // Don't search nodes that don't exist
    if (n == null)
        return;

    // If p is to the right of the rightmost point of any interval
    // in this node and all children, there won't be any matches.
    if (p.compareTo(n.getValue())> 0)
        return;

    // Search left children
    if (n.getLeft() != null)
        search(IntervalNode (n.getLeft()), p, result);

    // Check this node
    if (n.getKey().contains(p))
        result.add(n.getKey());

    // If p is to the left of the start of this interval,
    // then it can't be in any child to the right.
    if (p.compareTo(n.getKey().getStart()) <0)
        return;

    // Otherwise, search right children
    if (n.getRight() != null)
        search(IntervalNode (n.getRight()), p, result);
}

کد جستجوی یک بازه هم مشابه است به جز چک کردن قسمت میانی: // Check this node

if (n.getKey().overlapsWith(i))
    result.add (n.getKey());
overlapswith() این‌گونه تعریف شده‌است:

public boolean overlapsWith(Interval other) {

    return start.compareTo(other.getEnd()) <= 0 &&
           end.compareTo(other.getStart())>= 0;

}

ابعاد بالاتر

این را می‌توان با چرخیدن در ابعاد مختلف در هر سطح از درخت به ابعاد بالاتر گسترش داد!!! برای مثال، برای دو بعد، سطوح فرد درخت باید شامل محدوده‌هایی برای مختصات x و سطوح زوج باید شامل محدوده‌هایی برای مختصات x باشند. البته خیلی واضح نیست که منطق چرخشی چگونه باید برای چنین حالت‌هایی گسترش یابد تا درخت متعادل بماند.
یک راه حل خیلی ساده‌تر استفاده از درخت‌های بازه‌ای تودرتو می‌باشد. ابتدا با استفاده از محدوده‌های y یک درخت بازه‌ای بسازید. حال برای هر گره درخت، برای همه عناصری که محدودۀ y آن‌ها با محدودۀ y آن گره اشتراک دارد، یک درخت بازه‌ای دیگر در محدودۀ x اضافه کنید. مزیت این راه حل این است که می‌تواند با یک کد پایه یکسان برای هر تعداد دلخواه از ابعاد گسترش یابد.
در ابتدا هزینۀ درختان اضافی ممکن است سنگین به نظر برسد اما معمولاً چنین نیست. زیرا با راه حل فوق شما نیاز به یک گره در هر مختصات x دارید پس این هزینه در هر دو راه حل یکسان است. تنها تفاوت این است که شما نیاز به یک ساختار درختی اضافی در هر بازه عمودی دارید. این ساختار به‌طور معمول بسیار کوچک است. (یک اشاره‌گر به گره ریشه به علاوه شاید تعداد گره‌ها و ارتفاع درخت)

درخت میانی / طول‌گرا

این درخت مشابه درخت افزوده است اما به صورت متقارن. در حالی که درخت جستجوی دودویی بر اساس نقطه میانی بازه‌ها مرتب شده‌است و یک heap دودویی حداکثر گرا در هر گره وجود دارد و بر اساس طول بازه‌ها (یا نصف طول آن) مرتب شده‌است. همچنین ما به علت تقارن، علاوه بر بیشترین مقدار ممکن، حداقل مقدار ممکن در زیر درخت را نیز در هر گره ذخیره می کنیم.

آزمون همپوشانی

فرض کنیم دو بازه (a0, b0) , (a1, b1) را داریم. ابتدا و انتهای این بازه‌ها نسبت به یکدیگر می‌توانند یکی از 4 حالت زیر را داشته باشند:
${\displaystyle a_{0}\leqslant a_{1}<b_{0}}$    OR    ${\displaystyle a_{0}<b_{1}\leqslant b_{0}}$    OR    ${\displaystyle a_{1}\leqslant a_{0}<b_{1}}$    OR    ${\displaystyle a_{1}<b_{0}\leqslant b_{1}}$
اما با تعریف 2 متغیر زیر:
${\displaystyle m_{i}={\frac {a_{i}+b_{i}}{2}}}$

${\displaystyle d_{i}={\frac {b_{i}-a_{i}}{2}}}$
تست هم‌پوشانی راحت‌تر خواهد شد:
${\displaystyle \left|m_{1}-m_{0}\right|<d_{0}+d_{1}}$

اضافه کردن بازه

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

جستجو برای یافتن تمامی بازه‌های هم‌پوشا

از متغیرهای aq, bq, mq, dq برای بازۀ پرسش‌شده و از Mn برای کلید گره‌ای که (که با mi بازه‌ها مقایسه می‌شود) استفاده می کنیم.از گره ریشه شروع می کنیم. برای هر گره (که روی آن هستیم) ابتدا از طریق مقایسه کردن مقادیر ابتدا و انتهای بازۀ نظیر به گره بررسی می کنیم آیا بازهٔ پرس و جو شدۀ ما با گره‌های زیر درخت‌های گره فعلی می‌تواند هم‌پوشانی داشته باشد یا نه؟ اگر جواب منفی بود این روش را برای گره‌های زیر درخت‌های گره فعلی ادامه نمی‌دهیم.
سپس ما را برای بازه‌های درون گره فعلی (نه فرزندهایش) برای بررسی هم‌پوشانی محاسبه می کنیم: (می‌دانیم )

و برای ‌هایی که از بزرگتر باشند یک درخواست روی Binary Heap می‌زنیم. سپس همین عمل را برای فرزندان راست و چپ گره انجام می‌دهیم. در بدترین حالت ما مجبور به دیدن تمامی گره‌های BST هستیم اما از آنجایی که درخواست روی Binary Heap بهینه است نباید نگران مرتبه الگوریتم باشیم. (یک مسئله دو بعدی نمی‌تواند در هر دو بعد بهینه باشد) انتظار می‌رفت که این الگوریتم از than traditional Interval Tree (Augmented tree) در عملیات جستجو سریعتر باشد درحالی که تنها کمی‌کندتر است و این اختلاف تأثیری در مرتبه زمانی ندارد. (مرتبه زمانی هر دو یکی است و تفاوت در ضرایب آن است)

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Interval tree». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۰ آذر ۱۳۹۲.