موضوع مقاله: درخت بازه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت بازه | مقدمه: می‌توان گفت این از درخت این امکان را فراهم می‌سازد تا همۀ بازه‌هایی را که با یک بازه یا نقطۀ خاص اشتراک دارند پیدا کنیم. | ## بخش 1: درخت بازه | برای مثال، یافتن تمام راه‌های موجود بر روی یک نقشۀ کامپیوتری درون یک دید مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. راه حل بدیهی این است که تمام بازه‌ها را ملاقات کرده و امتحان کنیم که آیا با نقطه یا بازه داده شده اشتراک دارند یا نه، که به theta(n) زمان نیاز دارد. (که n همان تعداد بازه‌های موجود در مجموعه است) از آنجایی که یک پرسش ممکن است تمام بازه‌ها را برگرداند، به‌طور مثال، اگر پرسش مورد نظر یک بازۀ بزرگ باشد که با همۀ بازه‌های موجود در مجموعه اشتراک داشته باشد، این به صورت مجانبی بهینه است؛ اگر که ما از الگوریتم‌های حساس به خروجی که در آن‌ها زمان اجرا بر اساس m (که همان تعداد بازه‌های تولید شده توسط پرس و جوست) بیان می‌شود استفاده کنیم می‌توانیم این فرایند را بهبود ببخشیم. این در حالی است که زمان پیش پردازش برای ساخت این داده ساختار از O(nlogn) است (ولی فضای مصرف شده از O(n) است). اگر انتهای بازه‌ها در محدودۀ کوچکی قرار داشته باشند (مثلاً محدوده [1,...,O(n ، داده ساختارهای سریع‌تری با زمان پیش پردازش O(n) و زمان پرس و جوی O(1+m) وجود دارند که m بازه (شامل یک نقطه پرس و جو) را گزارش می‌کنند. عملکرد ساده در یک حالت ساده، بازه‌ها با هم هیچ گونه اشتراکی ندارند و می‌توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان O(logn) پرس و جو شوند. این در حالی است که با وجود اشتراک‌های دلخواه میان بازه‌ها، به هیچ عنوان امکان مقایسه دو بازه برای درج در درخت وجود ندارد. این کار اجازۀ رها کردن نصف درخت را در O(logn) می‌دهد ولی نتیجه‌ها باید ادغام شوند که به O(n) زمان نیاز دارد. درخت بازه‌ای مرکزی پرس و جو ها به زمان o(m + log(n نیاز دارند که در آن n تعداد کل بازه‌ها و m تعداد نتایج گزارش شده‌است. ساختار به ما یک مجموعه n تایی از بازه‌ها در خط اعداد داده می‌شود و ما می خواهیم یک داده ساختار بسازیم که بتواند به صورت مؤثری همه بازه‌هایی را که با یک نقطه یا بازه اشتراک دارند بازیابی کند. بازه‌هایی از S_center که با نقطۀ مرکزی تلاقی دارند در یک داده ساختار جداگانه مرتب می‌شوند که به گره‌های درخت بازه‌ای پیوند داده شده‌است. این داده ساختار از دو لیست تشکیل شده‌است: یکی شامل همه بازه‌هایی که بر حسب نقاط شروع‌شان مرتب شده‌اند و دیگری شامل همۀ بازه‌هایی که برحسب نقاط پایانشان مرتب شده‌اند. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت چپ نقطۀ مرکزی قرار می‌گیرند. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت راست نقطۀ مرکزی قرار می‌گیرند. ما پرس و جوهایی را شامل بازه‌ها یا نقاط داده شده دریافت می‌کنیم و تمام بازه‌های موجود در بازه‌های اصلی و تمام بازه‌های موجود در مجموعۀ اصلی را که با این ورودی اشتراک دارند برمی‌گردانیم. با یک بازه اول می‌توانیم حالتی را که یک بازه R به عنوان ورودی داده می‌شود به حالت ساده‌تر که در آن یک نقطه به عنوان ورودی داده شده‌است کاهش دهیم. در ابتدا همۀ بازه‌هایی را که نقطۀ شروع یا پایان‌شان در درون بازۀ ورودی R قرار دارد، با استفاده از یک درخت جداگانه می‌یابیم. در حالت یک بعدی می‌توانیم از یک درخت ساده شامل همۀ نقاط شروع و پایان در مجموعۀ بازه‌ها استفاده کنیم که هرکدام شامل یک نشانه‌گر به بازۀ مربوط به آن است. یک جستجوی دودویی در زمان O(logn) برای شروع و پایان R، کمینه و بیشینۀ نقاطی را که باید در نظر گرفته شوند مشخص می‌کند. هر نقطه با این محدوده به تمام بازه‌هایی که با محدودۀ مورد نظر ما تلاقی دارند ارجاع می‌دهد و به لیست نتیجه اضافه می‌شود. باید توجه شود که از ایجاد تکرار جلوگیری شود، زیرا ممکن است هم شروع و هم پایان یک بازه با R باشد. این کار را می‌توان با استفاده از یک پرچم دودویی بر روی هر بازه برای مشخص کردن اینکه این بازه به مجموعۀ نتیجه اضافه شده‌است یا نه، انجام داد. | ## بخش 2: درخت بازه | تنها بازه‌هایی که هنوز در نظر گرفته نشده‌اند بازه‌هایی هستند که با R تلاقی دارند ولی نقاط پایان‌شان درون R نیست، به عبارت دیگر، بازه‌هایی که آن را در بر می‌گیرند. برای پیدا کردن آن‌ها ما هر نقطه در درون را در نظر می‌گیریم و از الگوریتم زیر استفاده می‌کنیم تا همۀ بازه‌هایی را که با آن نقطه اشتراک دارند بیابیم. درخت به همان شیوه پیمایش یک درخت مرسوم دودویی پیمایش می‌شود، ولی با کارآیی بیشتر برای بازه‌هایی که با نقطۀ مرکزی در هر گره تلاقی دارند. برای هر گره درخت، x با x_center مقایسه می‌شود، یعنی همان نقطۀ میانی که برای ساخت گره در بالا استفاده شده‌است. همین طور که هر گره پردازش می‌شود، وقتی ما درخت را از ریشه به یک برگ می‌پیماییم، محدوده‌های موجود در S_center آن پردازش می‌شوند. از آنجایی که ما در این سناریو تنها به شروع بازه‌ها اهمیت می‌دهیم، می‌توانیم در مورد لیست مرتب شده بر اساس شروع بازه‌ها بحث کنیم. تمام محدوده‌ها از شروع لیست تا آن نقطه یافته شده با x تلاقی دارند، چون قبل از x شروع شده و بعد از x تمام می‌شوند. (همان طور که می‌دانیم به علت این است که با x_center که بزرگ‌تر از x است تلاقی دارند) بنابراین می‌توانیم شروع به شماره‌گذاری بازه‌های موجود در لیست کنیم تا زمانی که مقدار نقطه پایانی از x بیشتر شود. همچنین اگر x از x_center بزرگ‌تر باشد، ما می‌دانیم که همۀ بازه‌های موجود در s_center باید قبل از x شروع شوند پس ما بازه‌هایی را که بعد از x پایان می‌یابند به وسیلۀ لیستی که بر اساس پایان بازه‌ها مرتب شده‌است می‌یابیم. اگر x دقیقاً منطبق بر x_center باشد، تمام فواصل را می‌توان بدون پردازش بیشتر به نتایج اضافه کرد و پیمایش درخت می‌تواند متوقف شود. اول یک درخت محدوده در ابعاد N ساخته شده‌است که اجازه بازیابی کارآمد از تمام فواصل با شروع و پایان نقاط در داخل منطقۀ پرس و جو Rرا می‌دهد. هنگامی که تمام بازه‌های مربوطه یافت شدند، تنها چیزی که باقی می‌ماند آن بازه‌هایی است که ناحیه را بعضی ابعاد در بر می‌گیرند. برای پیدا کردن این همپوشانی‌ها، N درخت بازه‌ای به وجود می‌آیند و یک محور متقاطع با R برای هرکدام پرس و جو می‌شود. برای مثال، در دو بعد، پایین مربع R (یا هر خط افقی متقاطع با R) در برابر درخت بازه‌ای ساخته شده برای محور افقی پرس و جو می‌شود. به همین ترتیب سمت چپی (یا هر خط عمودی متقاطع با R) در برابر درخت بازه‌ای ساخته شده بر محور عمودی پرس و جو می‌شود. به جای دو لیست مرتب شده از بازه‌ها که در حالت یک بعدی مورد استفاده قرار می‌گرفت یک درخت محدوده ساخته می‌شود. این امکان بازیابی کارآمد تمام بازه‌های موجود در s_center را (که با ناحیه R تلاقی دارند) فراهم می‌سازد. حذف اگر پس از حذف یک بازه از درخت، گره شامل آن بازه شامل هیچ بازه دیگری نباشد، آن گره ممکن است از درخت حذف شود. از آنجایی که هر گره بازه‌هایی را که با آن تلاقی دارند ذخیره می‌کند، به همراه تمام بازه‌های به‌طور کامل سمت چپ نقطۀ مرکز آن در زیر درخت سمت چپ و به‌طور مشابه برای زیر درخت راست. این نتیجه می‌دهد که هر بازه از بین بازه‌هایی که با مرکز آن‌ها تلاقی دارد در نزدیک‌ترین گره به ریشه ذخیره می‌شود. عملیات حذف عادی در یک درخت دودویی (برای حالتی که گره در حال حذف شدن دارای دو فرزند باشد) شامل ارتقاء یک گره دورتر از ریشه به جایگاه گره در حال حذف است (معمولاً چپ‌ترین درخت زیردرخت راست یا راست‌ترین درخت زیر درخت چپ). به عنوان یک نتیجه این ارتقاء، بعضی از گره‌هایی که بالای گره ارتقاء یافته بودند به نوادگان آن تبدیل خواهند شد. | ## بخش 3: درخت بازه | لازم است که این گره‌ها را برای بازه‌هایی که با گره ارتقاء یافته تلاقی دارند نیز جستجو کنیم و آن بازه‌ها را به داخل گره‌های ارتقاء یافته منتقل کنیم. در نتیجه این ممکن است باعث ایجاد گره‌های خالی جدیدی شود که دوباره طبق همان الگوریتم باید حذف شوند. برای مثال یک درخت جستجوی دودویی یا یک درخت خود-متعادل جستجوی دودویی، که درخت بر اساس نقاط پایین بازه‌ها مرتب شده‌است و یک توضیح اضافه به هر گره اضافه شده‌است که ماکزیمم نقاط بالای بازه‌ها را در زیر درخت‌های آن نگه می‌دارد. به دست آوردن این صفت در طی تنها O(h) مرحله هنگام حذف یا درج یک گره کار ساده‌ای است، که h همان ارتفاع گره درج یا حذف شده به وسیله به روز رسانی همۀ اجداد گره از پایین به بالا در درخت می‌باشد. به علاوه، چرخش‌های درخت که در حذف و درج مورد استفاده قرار می‌گرفت، ممکن است نیاز به به روز رسانی قسمت بالای گره‌های مورد تأثیر داشته باشد. هنگام جستجوی درخت‌ها برای یافتن گره‌هایی که با یک بازه تلاقی دارند، شما می‌توانید بلافاصله از موارد زیر صرف نظر کنید: همه گره‌هایی که در سمت راست گره‌هایی قرار دارند که مقدار پایین آن‌ها از پایان بازه داده شده گذشته‌است. همه گره‌هایی که ماکزیمم مقدار بالای آن‌ها زیر نقطه شروع بازه داده شده قرار دارد. با مرتب کردن بازه‌ها ابتدا بر اساس مقدار پایین و سپس مقدار بالا یک ترتیب کلی را می‌توان برای بازه‌ها تعریف کرد. این مرتب‌سازی برای جلوگیری از درج بازه‌های تکراری در درخت در O(logn) می‌تواند در مقابل زمان o(k + logn) لازم برای یافتن تکرارها هنگامی کهk بازه با یک بازه جدید تلاقی دارند، مورد استفاده قرار گیرد. برای مثال، برای دو بعد، سطوح فرد درخت باید شامل محدوده‌هایی برای مختصات x و سطوح زوج باید شامل محدوده‌هایی برای مختصات x باشند. البته خیلی واضح نیست که منطق چرخشی چگونه باید برای چنین حالت‌هایی گسترش یابد تا درخت متعادل بماند. حال برای هر گره درخت، برای همه عناصری که محدودۀ y آن‌ها با محدودۀ y آن گره اشتراک دارد، یک درخت بازه‌ای دیگر در محدودۀ x اضافه کنید. مزیت این راه حل این است که می‌تواند با یک کد پایه یکسان برای هر تعداد دلخواه از ابعاد گسترش یابد. زیرا با راه حل فوق شما نیاز به یک گره در هر مختصات x دارید پس این هزینه در هر دو راه حل یکسان است. (یک اشاره‌گر به گره ریشه به علاوه شاید تعداد گره‌ها و ارتفاع درخت) درخت میانی / طول‌گرا این درخت مشابه درخت افزوده است اما به صورت متقارن. در حالی که درخت جستجوی دودویی بر اساس نقطه میانی بازه‌ها مرتب شده‌است و یک heap دودویی حداکثر گرا در هر گره وجود دارد و بر اساس طول بازه‌ها (یا نصف طول آن) مرتب شده‌است. همچنین ما به علت تقارن، علاوه بر بیشترین مقدار ممکن، حداقل مقدار ممکن در زیر درخت را نیز در هر گره ذخیره می کنیم. ابتدا و انتهای این بازه‌ها نسبت به یکدیگر می‌توانند یکی از 4 حالت زیر را داشته باشند: OR OR OR اما با تعریف 2 متغیر زیر: تست هم‌پوشانی راحت‌تر خواهد شد: اضافه کردن بازه اضافه کردن یک بازه به درخت بازه‌ها شبیه اضافه کردن در درخت جستجوی دودویی است تنها با این تفاوت که از وسط بازه به عنوان کلید مقایسه برای پیدا کردن یا ساختن گره مناسب برای درج بازه diاستفاده می‌شود. باید diرا در پشته دودویی نظیرشده به گره درج کنیم و برای تمامی گره‌هایی که در درخت بازه‌ها بالاتر از گره مدنظر هستند، مقدار کمینه و بیشینه نظیر به آن‌ها را به روز رسانی کرد. جستجو برای یافتن تمامی بازه‌های هم‌پوشا از متغیرهای aq, bq, mq, dq برای بازۀ پرسش‌شده و از Mn برای کلید گره‌ای که (که با mi بازه‌ها مقایسه می‌شود) استفاده می کنیم.از گره ریشه شروع می کنیم. برای هر گره (که روی آن هستیم) ابتدا از طریق مقایسه کردن مقادیر ابتدا و انتهای بازۀ نظیر به گره بررسی می کنیم آیا بازهٔ پرس و جو شدۀ ما با گره‌های زیر درخت‌های گره فعلی می‌تواند هم‌پوشانی داشته باشد یا نه؟ | ## جمع‌بندی | سپس ما را برای بازه‌های درون گره فعلی (نه فرزندهایش) برای بررسی هم‌پوشانی محاسبه می کنیم: (می‌دانیم ) و برای ‌هایی که از بزرگتر باشند یک درخواست روی Binary Heap می‌زنیم.