درخت بازه

در یک حالت ساده، بازه‌ها با هم هیچ گونه اشتراکی ندارند و می‌توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان 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 نیست، به عبارت دیگر، بازه‌هایی که آن را در بر می‌گیرند. برای پیدا کردن آن‌ها ما هر نقطه در درون را در نظر می‌گیریم و از الگوریتم زیر استفاده می‌کنیم تا همۀ بازه‌هایی را که با آن نقطه اشتراک دارند بیابیم. (دوباره مواظب باشید که تکرارها را حذف کنید)

این فرایند در واقع یافتن همه بازه‌های موجود در درخت است که با یک نقطه 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 باشد، تمام فواصل را می‌توان بدون پردازش بیشتر به نتایج اضافه کرد و پیمایش درخت می‌تواند متوقف شود.

ساختمان داده درخت را می‌توان با پرس و جو و زمان ساخت یکسان و فضای 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 d_i=\frac{b_i-a_i}{2}}$

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

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

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