Intervalli daraxt - Interval tree

Yilda Kompyuter fanlari, an intervalli daraxt a daraxt ma'lumotlari tuzilishi ushlamoq intervallar. Xususan, bu har qanday interval yoki nuqta bilan ustma-ust keladigan barcha intervallarni samarali topishga imkon beradi. Bu tez-tez^{[iqtibos kerak ]} so'rovlarni oynalashda, masalan, to'rtburchaklar ko'rinish oynasida kompyuterlashtirilgan xaritada barcha yo'llarni topish yoki uch o'lchovli sahna ichidagi barcha ko'rinadigan elementlarni topish uchun foydalaniladi. Shunga o'xshash ma'lumotlar tuzilishi segment daraxt.

Arzimas echim - har bir intervalga tashrif buyurib, uning kerakli nuqtani yoki oraliqni kesib o'tishini sinab ko'rish ${ displaystyle O (n)}$ vaqt, qayerda ${ displaystyle n}$ to'plamdagi intervallar soni. So'rov barcha intervallarni qaytarishi mumkin bo'lganligi sababli, masalan, so'rov to'plamdagi barcha intervallarni kesib o'tgan katta interval bo'lsa, bu asimptotik jihatdan maqbul; ammo, biz o'ylab yaxshiroq qilishimiz mumkin chiqishga sezgir algoritmlar, bu erda ish vaqti ifodalangan ${ displaystyle m}$ , so'rov tomonidan ishlab chiqarilgan intervallar soni. Intervalli daraxtlar so'rov vaqtiga ega ${ displaystyle O ( log n + m)}$ va boshlang'ich yaratilish vaqti ${ displaystyle O (n log n)}$ , xotira sarfini cheklash bilan birga ${ displaystyle O (n)}$ . Yaratgandan so'ng, intervalli daraxtlar dinamik bo'lishi mumkin, bu intervalni samarali kiritish va o'chirishga imkon beradi ${ displaystyle O ( log n)}$ vaqt. Agar intervallarning so'nggi nuqtalari kichik butun son oralig'ida bo'lsa (masalan., oralig'ida ${ displaystyle [1, ldots, O (n)]}$ ), tezroq va aslida optimal ma'lumotlar tuzilmalari mavjud^[1]^[2] oldindan ishlov berish vaqti bilan ${ displaystyle O (n)}$ va so'rov vaqti ${ displaystyle O (1 + m)}$ hisobot uchun ${ displaystyle m}$ berilgan so'rov nuqtasini o'z ichiga olgan intervallar (qarang^[1] juda oddiy uchun).

Sodda yondashuv

Oddiy holatda, intervallar bir-biriga mos kelmaydi va ularni oddiyga kiritish mumkin ikkilik qidiruv daraxti va so'ralgan ${ displaystyle O ( log n)}$ vaqt. Biroq, o'zboshimchalik bilan bir-birining ustiga chiqib ketadigan intervallar bilan, daraxtga kiritish uchun ikkita intervalni taqqoslashning imkoni yo'q, chunki boshlang'ich nuqtalar yoki tugash nuqtalari bo'yicha tartiblangan buyurtmalar boshqacha bo'lishi mumkin. Ikkala parallel daraxtlarni qurish uchun sodda yondashuv bo'lishi mumkin, ulardan biri boshlang'ich nuqtasi va har biri intervalning tugash nuqtasi bilan buyurtma qilingan. Bu har bir daraxtning yarmini tashlashga imkon beradi ${ displaystyle O ( log n)}$ vaqt, lekin natijalar birlashtirilishi kerak, talab qiladi ${ displaystyle O (n)}$ vaqt. Bu bizga so'rovlarni beradi ${ displaystyle O (n + log n) = O (n)}$ , bu qo'pol kuchdan yaxshiroq emas.

Intervalli daraxtlar bu muammoni hal qiladi. Ushbu maqolada intervalli daraxt uchun ikkita muqobil dizayn tasvirlangan markazlashtirilgan intervalli daraxt va kattalashtirilgan daraxt.

Markazlashtirilgan intervalli daraxt

So'rovlar talab qilinadi ${ displaystyle O ( log n + m)}$ vaqt, bilan ${ displaystyle n}$ intervallarning umumiy soni va ${ displaystyle m}$ hisobot qilingan natijalar soni. Qurilish talab qiladi ${ displaystyle O (n log n)}$ vaqt va saqlash talab qiladi ${ displaystyle O (n)}$ bo'sh joy.

Qurilish

To'plami berilgan ${ displaystyle n}$ raqamlar qatoridagi intervallar, biz boshqa interval yoki nuqta ustidagi barcha intervallarni samarali ravishda olishimiz uchun ma'lumotlar tuzilishini yaratmoqchimiz.

Biz barcha intervallarni butun diapazonini olib, ikkiga bo'linishni boshlaymiz ${ displaystyle x _ { textrm {center}}}$ (amalda, ${ displaystyle x _ { textrm {center}}}$ daraxtni nisbatan muvozanat saqlash uchun tanlanishi kerak). Bu uchta chap oraliqni beradi ${ displaystyle x _ { textrm {center}}}$ biz uni chaqiramiz ${ displaystyle S _ { textrm {left}}}$ , to'liq o'ng tomonda bo'lganlar ${ displaystyle x _ { textrm {center}}}$ biz uni chaqiramiz ${ displaystyle S _ { textrm {right}}}$ va bir-birining ustiga chiqadigan narsalar ${ displaystyle x _ { textrm {center}}}$ biz uni chaqiramiz ${ displaystyle S _ { textrm {center}}}$ .

Intervallari ${ displaystyle S _ { textrm {left}}}$ va ${ displaystyle S _ { textrm {right}}}$ intervallar qolmaguncha xuddi shu tarzda rekursiv ravishda bo'linadi.

Intervallari ${ displaystyle S _ { textrm {center}}}$ markaz nuqtasi bilan to'qnashgan interval daraxtidagi tugunga bog'langan alohida ma'lumotlar tarkibida saqlanadi. Ushbu ma'lumotlar tuzilishi ikkita ro'yxatdan iborat bo'lib, ulardan biri ularning boshlang'ich nuqtalari bo'yicha tartiblangan barcha intervallarni o'z ichiga oladi, boshqalari esa ularning so'nggi nuqtalari bo'yicha tartiblangan barcha intervallarni o'z ichiga oladi.

Natijada a ikkilik daraxt har bir tugunni saqlash bilan:

Markaziy nuqta
Barcha tugunlarni markaziy nuqtadan butunlay chap tomonga o'z ichiga olgan boshqa tugunga ko'rsatgich
Barcha tugunlarni markaziy nuqtadan to'liq o'ng tomonga o'z ichiga olgan boshqa tugunga ko'rsatgich
Markaziy nuqta ustma-ust keladigan barcha intervallar boshlanish nuqtalari bo'yicha tartiblangan
Markaziy nuqta ustma-ust keladigan barcha intervallar tugash nuqtasi bo'yicha saralangan

Kesish

Yuqorida tuzilgan ma'lumotlar strukturasini hisobga olgan holda, biz diapazonlardan yoki nuqtalardan iborat so'rovlarni qabul qilamiz va ushbu to'plam bilan ustma-ust keladigan barcha to'plamlarni qaytaramiz.

Bir nuqta bilan

Vazifa daraxtda berilgan nuqta bilan qoplanadigan barcha intervallarni topishdir ${ displaystyle x}$ . Daraxt an'anaviy ikkilik daraxtni bosib o'tishda ishlatilgandek o'xshash rekursiv algoritm bilan yuriladi, lekin har bir tugundagi "markaz" nuqtasi bilan mos keladigan intervallarni qidirishni qo'llab-quvvatlash uchun qo'shimcha mantiq bilan.

Har bir daraxt tuguni uchun, ${ displaystyle x}$ bilan taqqoslanadi ${ displaystyle x _ { textrm {center}}}$ , Yuqoridagi tugunni qurishda ishlatiladigan o'rta nuqta. Agar ${ displaystyle x}$ dan kam ${ displaystyle x _ { textrm {center}}}$ , eng chap oraliqlar to'plami, ${ displaystyle S _ { textrm {left}}}$ , hisobga olinadi. Agar ${ displaystyle x}$ dan katta ${ displaystyle x _ { textrm {center}}}$ , eng to'g'ri oraliqlar to'plami, ${ displaystyle S _ { textrm {right}}}$ , hisobga olinadi.

Barcha intervallar

{ displaystyle S _ { textrm {center}}}

oldin boshlanadi

{ displaystyle x}

bir-biriga to'g'ri kelishi kerak

{ displaystyle x}

agar

{ displaystyle x}

dan kam

{ displaystyle x _ { textrm {center}}}

.
Xuddi shunday, xuddi shu usul berilgan intervalni tekshirishda ham qo'llaniladi. Agar berilgan interval bilan tugasa y va y dan kam

{ displaystyle x _ { textrm {center}}}

, barcha intervallar

{ displaystyle S _ { textrm {center}}}

oldin boshlanadi y shuningdek berilgan interval bilan qoplanishi kerak.

Daraxtni ildizdan barggacha o'tayotganda har bir tugunni qayta ishlash jarayonida uning oralig'i ${ displaystyle S _ { textrm {center}}}$ qayta ishlanadi. Agar ${ displaystyle x}$ dan kam ${ displaystyle x _ { textrm {center}}}$ , biz hamma intervallarni bilamiz ${ displaystyle S _ { textrm {center}}}$ keyin tugaydi ${ displaystyle x}$ , yoki ular ham bir-birini qoplay olmadi ${ displaystyle x}$ . Shuning uchun biz faqat shu intervallarni topamiz ${ displaystyle S _ { textrm {center}}}$ oldin boshlanadi ${ displaystyle x}$ . Biz ro'yxatlariga murojaat qilishimiz mumkin ${ displaystyle S _ { textrm {center}}}$ allaqachon qurilgan. Ushbu stsenariyda biz faqat intervalli boshlanishlar haqida qayg'uradigan bo'lsak, biz boshlanishlar bo'yicha saralangan ro'yxat bilan maslahatlashishimiz mumkin. Deylik, biz eng katta raqamni kattaroq kattaroq deb topdik ${ displaystyle x}$ ushbu ro'yxatda. Ro'yxat boshidan tortib to topilgan nuqtagacha bo'lgan barcha oraliqlar ${ displaystyle x}$ chunki ular oldin boshlanadi ${ displaystyle x}$ va keyin tugaydi ${ displaystyle x}$ (biz bilamizki, chunki ular bir-biriga to'g'ri keladi ${ displaystyle x _ { textrm {center}}}$ bu kattaroqdir ${ displaystyle x}$ ). Shunday qilib, biz boshlang'ich nuqtasi qiymati oshib ketguncha ro'yxatdagi intervallarni sanashni boshlashimiz mumkin ${ displaystyle x}$ .

Xuddi shunday, agar ${ displaystyle x}$ dan katta ${ displaystyle x _ { textrm {center}}}$ , biz hamma intervallarni bilamiz ${ displaystyle S _ { textrm {center}}}$ oldin boshlash kerak ${ displaystyle x}$ , shuning uchun biz keyin tugaydigan intervallarni topamiz ${ displaystyle x}$ intervalli tugatish bo'yicha tartiblangan ro'yxat yordamida.

Agar ${ displaystyle x}$ to'liq mos keladi ${ displaystyle x _ { textrm {center}}}$ , barcha intervallar ${ displaystyle S _ { textrm {center}}}$ natijalarga qo'shimcha ishlov bermasdan qo'shilishi mumkin va daraxtlarni kesib o'tishni to'xtatish mumkin.

Interval bilan

Natija oralig'i uchun ${ displaystyle r}$ bizning so'rovlar oralig'ini kesish uchun ${ displaystyle q}$ quyidagilardan biri bajarilishi kerak:

ning boshlanish va / yoki tugash nuqtasi ${ displaystyle r}$ ichida ${ displaystyle q}$ ; yoki
${ displaystyle r}$ to'liq qamrab oladi ${ displaystyle q}$ .

Dastlab ichidagi boshlanish va / yoki tugash nuqtalari bo'lgan barcha intervallarni topamiz ${ displaystyle q}$ alohida qurilgan daraxt yordamida. Bir o'lchovli holatda, biz intervallar to'plamidagi barcha boshlang'ich va tugash nuqtalarini o'z ichiga olgan qidirish daraxtidan foydalanishimiz mumkin, ularning har biri mos keladigan intervalgacha ko'rsatgichga ega. Ikkilik qidiruv ${ displaystyle O ( log n)}$ boshlanish va tugash vaqti ${ displaystyle q}$ e'tiborga olinadigan minimal va maksimal fikrlarni ochib beradi. Ushbu oraliqdagi har bir nuqta bir-biriga mos keladigan intervalga ishora qiladi ${ displaystyle q}$ va natijalar ro'yxatiga qo'shiladi. Ikki nusxadagi nusxalardan qochish uchun ehtiyot bo'lish kerak, chunki interval ham boshlanishi, ham tugashi mumkin ${ displaystyle q}$ . Bu natijalar to'plamiga qo'shilgan yoki qo'shilmaganligini belgilash uchun har bir intervalda ikkilik bayroq yordamida amalga oshirilishi mumkin.

Va nihoyat, biz o'z ichiga oladigan intervallarni topishimiz kerak ${ displaystyle q}$ . Ularni topish uchun ichkaridagi istalgan nuqtani tanlaymiz ${ displaystyle q}$ va yuqoridagi algoritmdan foydalanib, ushbu nuqtani kesib o'tadigan barcha intervallarni toping (yana takrorlang, ehtiyot bo'ling).

Yuqori o'lchamlar

Daraxtlar orasidagi intervalli tuzilishni yuqori o'lchamlarga umumlashtirish mumkin ${ displaystyle N}$ bir xil so'rov va qurilish vaqti bilan va ${ displaystyle O (n log n)}$ bo'sh joy.

Birinchidan, a oraliq daraxt yilda ${ displaystyle N}$ o'lchovlar so'rov hududida boshlanish va tugash nuqtalari bilan barcha intervallarni samarali olish imkonini beradigan tarzda qurilgan ${ displaystyle R}$ . Tegishli diapazonlar topilgandan so'ng, faqatgina mintaqani ba'zi o'lchamlarga qamrab oladigan diapazonlar qoladi. Ushbu o'xshashliklarni topish uchun, ${ displaystyle N}$ intervalli daraxtlar yaratiladi va bitta o'qni kesib o'tadi ${ displaystyle R}$ har biri uchun so'raladi. Masalan, ikki o'lchamda kvadratning pastki qismi ${ displaystyle R}$ (yoki kesishgan boshqa gorizontal chiziq) ${ displaystyle R}$ ) gorizontal o'q uchun qurilgan intervalli daraxtga nisbatan so'raladi. Xuddi shu tarzda, chap (yoki boshqa har qanday vertikal chiziq kesishadi ${ displaystyle R}$ ) vertikal o'qda qurilgan intervalli daraxtga nisbatan so'raladi.

Har bir intervalli daraxtga yuqori o'lchamlar uchun qo'shimcha kerak. Har bir tugunda biz daraxt bo'ylab o'tamiz, ${ displaystyle x}$ bilan taqqoslanadi ${ displaystyle S _ { textrm {center}}}$ ustma-ust tushishlarni topish uchun. Bir o'lchovli holatda ishlatilgan ikkita tartiblangan ro'yxat o'rniga, oraliq daraxti qurilgan. Bu barcha nuqtalarni samarali ravishda olish imkonini beradi ${ displaystyle S _ { textrm {center}}}$ bir-birini qoplaydigan mintaqa ${ displaystyle R}$ .

O'chirish

Agar daraxtdan intervalni o'chirib tashlaganingizdan so'ng, o'sha oraliqni o'z ichiga olgan tugun ko'proq intervallarni o'z ichiga olmasa, u tugun daraxtdan o'chirilishi mumkin. Bu oddiy ikkilik daraxtlarni yo'q qilish operatsiyasidan ko'ra murakkabroq.

Interval daraxtdagi bir nechta tugunlarning markaziy nuqtasi bilan qoplanishi mumkin. Har bir tugun, xuddi shu o'ng daraxt uchun xuddi shu chap daraxtda, uning markaziy nuqtasidan butunlay chap tomoniga, barcha intervallarni o'zaro tutib turadigan intervallarni saqlaganligi sababli, har bir oraliq to'plamdan ildizga eng yaqin tugunda saqlanadi. markazini bir-biriga bog'laydigan tugunlar.

Ikkilik daraxtdagi normal o'chirish operatsiyalari (tugun o'chirilganida ikkita bola bo'lganligi uchun) tugunni bargdan o'chiriladigan tugun holatiga ko'tarishni o'z ichiga oladi (odatda o'ng pastki daraxtning eng chap bolasi yoki eng o'ng bola chap pastki daraxt).

Ikkala bolali tugunni tartibli oldingisidan foydalanib, ikkilik qidiruv daraxtidan o'chirish (chap pastki daraxtdagi o'ng tugun, etiketli 6).

Ushbu targ'ibot natijasida, ko'tarilgan tugundan yuqori bo'lgan ba'zi tugunlar uning avlodlariga aylanadi; ushbu tugunlarni ilgari surilgan tugunga mos keladigan intervallarni qidirish va ushbu intervallarni ko'tarilgan tugunga o'tkazish kerak. Natijada, bu yana bitta algoritmga binoan o'chirilishi kerak bo'lgan yangi bo'sh tugunlarga olib kelishi mumkin.

Balanslash

O'chirishga ta'sir qiladigan bir xil muammolar aylanish operatsiyalariga ham ta'sir qiladi; aylanish tugunlarni iloji boricha ildizga yaqinroq saqlanadigan o'zgarmasligini saqlab turishi kerak.

Kattalashtirilgan daraxt

Kalit sifatida past qiymati va qo'shimcha izoh sifatida maksimal darajada kattalashtirilgan daraxt.

Masalan, berilgan intervalni tekshirishda [40 ,60) yuqorida ko'rsatilgan daraxtdagi intervallarni qoplaydi, biz uning oralig'iga to'g'ri kelmasligini ko'ramiz [20, 36) ildizda, lekin ildizning past qiymati (20) qidirilgan yuqori qiymatdan (60) kamroq bo'lganligi sababli, biz to'g'ri subtree qidirishimiz kerak. Chap pastki daraxtning maksimal balandligi 41, qidirilayotgan past qiymatdan (40) oshib ketadi, shuning uchun biz ham chap daraxtni qidirishimiz kerak. Biroq, ikkala avlod ham [3, 41) tugunning maksimal balandligi 40 dan kam, shuning uchun chap subtree qidiruvi shu erda tugaydi va ularni qidirish shart emas.

Intervallarni namoyish qilishning yana bir usuli tasvirlangan Kormen va boshq. (2009 yil, 14.3-bo'lim: Intervalli daraxtlar, 348-354 betlar).

Ham qo'shish, ham o'chirish talab qilinadi ${ displaystyle O ( log n)}$ vaqt, bilan ${ displaystyle n}$ qo'shish yoki o'chirish operatsiyasidan oldin daraxtdagi intervallarning umumiy soni.

Kattalashtirilgan daraxtni oddiy buyurtma qilingan daraxtdan qurish mumkin, masalan a ikkilik qidiruv daraxti yoki o'z-o'zini muvozanatlashtiradigan ikkilik qidiruv daraxti, intervallarning "past" qiymatlari bilan tartiblangan. Keyin har bir tugunga qo'shimcha izoh qo'shiladi va ushbu tugundan pastga tushgan barcha intervallar orasida maksimal yuqori qiymat qayd etiladi. Ushbu atributni saqlab qolish tugun qo'shilganda yoki o'chirilganda tugunning barcha ajdodlarini pastdan yuqoriga yangilashni o'z ichiga oladi. Bu faqat O (h) tugunni qo'shish yoki olib tashlash bo'yicha qadamlar, qaerda h daraxtga qo'shilgan yoki olib tashlangan tugunning balandligi. Agar mavjud bo'lsa daraxtlarning aylanishi kiritish va o'chirish paytida ta'sirlangan tugunlarni ham yangilash kerak bo'lishi mumkin.

Endi, ma'lumki, ikkita interval ${ displaystyle A}$ va ${ displaystyle B}$ faqat ikkalasi ham bir-biriga mos keladi ${ displaystyle A _ { textrm {low}} leq B _ { textrm {high}}}$ va ${ displaystyle A _ { textrm {high}} geq B _ { textrm {low}}}$ . Daraxtlarni ma'lum bir oraliq bilan bir-biriga mos keladigan tugunlarni qidirishda siz darhol o'tishingiz mumkin:

tugunlarning o'ng tomonidagi barcha tugunlar, ularning qiymati past bo'lgan oraliq tugagan.
berilgan interval boshlanishidan pastda maksimal yuqori qiymatga ega bo'lgan barcha tugunlar.

A'zolik so'rovlari

Agar daraxt keraksiz o'tish joylaridan qochsa, ba'zi ko'rsatkichlarga erishish mumkin. Ular mavjud bo'lgan intervallarni qo'shganda yoki mavjud bo'lmagan intervallarni olib tashlashda paydo bo'lishi mumkin.

Umumiy tartibni avval pastki chegaralari, so'ngra yuqori chegaralari bo'yicha tartiblash orqali intervallarda aniqlash mumkin. Keyin, a'zolikni tekshirish amalga oshirilishi mumkin ${ displaystyle O ( log n)}$ vaqtga nisbatan ${ displaystyle O (k + log n)}$ agar dublikatlarni topish uchun vaqt kerak bo'lsa ${ displaystyle k}$ kiritiladigan yoki olib tashlanadigan interval bilan intervallar ustma-ust tushadi. Ushbu echim qo'shimcha tuzilmalarni talab qilmaydigan afzalliklarga ega. O'zgarish qat'iy algoritmikdir. Kamchilik shundaki, a'zolik so'rovlari olinadi ${ displaystyle O ( log n)}$ vaqt.

Shu bilan bir qatorda, darajasi bo'yicha ${ displaystyle O (n)}$ kutilgan doimiy vaqt ichida xotira, a'zolik so'rovlari xesh jadvali bilan amalga oshirilishi mumkin, interval daraxti bilan bloklangan qadamda yangilanadi. Agar intervallar qiymat bo'yicha emas, balki mos yozuvlar orqali saqlansa, bu xotira umumiy talabini ikki baravar oshirishi mumkin emas.

Java misoli: Daraxtga yangi interval qo'shish

Har bir tugunning kaliti bu intervalning o'zi, shuning uchun tugunlar avval past qiymat bilan, nihoyat yuqori qiymat bilan tartiblanadi va har bir tugunning qiymati intervalning so'nggi nuqtasidir:

 jamoat bekor qo'shish(Interval men) {     qo'yish(men, men.getEnd()); }

Java misoli: Daraxtda nuqta yoki intervalni qidirish

Intervalni qidirish uchun (n.getKey ()) va yuqori qiymat (n.getValue ()) so'rov bilan bir-birining ustiga chiqa olmaydigan filiallarni tashlab qo'yish. Eng oddiy holat - bu nuqta so'rovi:

 // "p" harfini o'z ichiga olgan barcha intervallarni qidiring // "n" tuguni va "natija" ro'yxatiga mos keladigan intervallarni qo'shish jamoat bekor qidirmoq(IntervalNode n, Nuqta p, Ro'yxat<Interval> natija) {     // Mavjud bo'lmagan tugunlarni qidirmang     agar (n == bekor)         qaytish;     // Agar p har qanday intervalning eng o'ng nuqtasidan o'ng tomonda bo'lsa     // ushbu tugunda va barcha bolalar, hech qanday mos kelmaydi.     agar (p.taqqoslash(n.getValue()) > 0)         qaytish;     // Chap bolalarni qidirish     qidirmoq(n.getLeft(), p, natija);     // Ushbu tugunni tekshiring     agar (n.getKey().o'z ichiga oladi(p))         natija.qo'shish(n.getKey());     // Agar p bu interval boshlanishining chap tomonida bo'lsa,     // keyin u biron bir bolada o'ng tomonda bo'lishi mumkin emas.     agar (p.taqqoslash(n.getKey().getStart()) < 0)         qaytish;     // Aks holda, to'g'ri bolalarni qidiring     qidirmoq(n.getRight(), p, natija); }

qayerda

a.compareTo (b) a

a.compareTo (b) a = b bo'lsa, nolni qaytaradi

a.compareTo (b) a> b bo'lsa, ijobiy qiymatni qaytaradi

Intervalni qidirish uchun kod o'xshash, o'rtadagi chek bundan mustasno:

 // Ushbu tugunni tekshiring agar (n.getKey().ustma-ust tushadi(men))     natija.qo'shish (n.getKey());

ketma-ket () quyidagicha aniqlanadi:

 jamoat mantiqiy ustma-ust tushadi(Interval boshqa) {     qaytish boshlang.taqqoslash(boshqa.getEnd()) <= 0 &&            oxiri.taqqoslash(boshqa.getStart()) >= 0; }

Yuqori o'lchamlar

Kattalashtirilgan daraxtlar daraxtning har bir sathidagi o'lchamlar bo'ylab velosipedda yurish orqali yuqori o'lchamlarga kengaytirilishi mumkin. Masalan, ikkita o'lcham uchun daraxtning toq sathlari uchun oraliqlarni o'z ichiga olishi mumkin xkoordinatali, juft darajalar esa uchun oraliqlarni o'z ichiga oladi y- muvofiqlashtirish. Ushbu yondashuv ma'lumotlar strukturasini kengaytirilgan ikkilik daraxtdan kengaytirilganga samarali ravishda o'zgartiradi kd-daraxt, shuning uchun qo'shimchalar va o'chirishlar uchun balanslash algoritmlarini sezilarli darajada murakkablashtirmoqda.

Oddiy echim - ichki oraliq daraxtlardan foydalanish. Birinchidan, qatorlari yordamida daraxt yarating y- muvofiqlashtirish. Endi daraxtdagi har bir tugun uchun ustiga yana bir oraliq daraxt qo'shing xbarcha elementlar uchun tartibga soladi y- bu tugun bilan bir xil y- oraliq.

Ushbu echimning afzalligi shundaki, uni bir xil kod bazasi yordamida o'zboshimchalik bilan o'lchamlarga etkazish mumkin.

Avvaliga uyali daraxtlarning qo'shimcha narxi juda katta bo'lib tuyulishi mumkin, ammo bu odatda bunday emas. Oldindan ichki bo'lmagan echimdagi kabi, bitta tugun kerak x- ikkala echim uchun bir xil miqdordagi tugunlarni beradigan koordinatali. Yagona qo'shimcha xarajat - bu vertikal oraliqda bittadan joylashtirilgan daraxt tuzilmalari. Ushbu tuzilish odatda ahamiyatsiz o'lchamga ega, faqat ildiz tuguniga ko'rsatgichdan va ehtimol tugunlar sonidan va daraxtning chuqurligidan iborat.

Medial yoki uzunlikka yo'naltirilgan daraxt

Medial yoki uzunlikka yo'naltirilgan daraxt kattalashtirilgan daraxtga o'xshaydi, ammo nosimmetrik bo'lib, ikkilik qidiruv daraxti intervallarning medial nuqtalari bilan buyurtma qilingan. Maksimal yo'naltirilganlik mavjud ikkilik uyum interval uzunligi (yoki uzunlikning yarmi) bo'yicha buyurtma qilingan har bir tugunda. Shuningdek, biz har bir tugunda kichik daraxtning mumkin bo'lgan maksimal va maksimal qiymatini saqlaymiz (shunday qilib simmetriya).
Qatlamli sinov
Ikki intervalning faqat boshlang'ich va oxirgi qiymatlaridan foydalanish ${ displaystyle chap (a_ {i}, b_ {i} o'ng)}$ , uchun ${ displaystyle i = 0,1}$ , takrorlash testi quyidagicha bajarilishi mumkin:
${ displaystyle a_ {0}$ va ${ displaystyle a_ {1}> b_ {0}}$
Bu summa va farq yordamida soddalashtirilishi mumkin:
${ displaystyle s_ {i} = a_ {i} + b_ {i}}$
${ displaystyle d_ {i} = b_ {i} -a_ {i}}$
Qaysi takroriy sinovni kamaytiradi:
${ displaystyle left | s_ {1} -s_ {0} right |$
Interval qo'shilmoqda
Daraxtga yangi intervallarni qo'shish, kalit sifatida medial qiymatdan foydalangan holda, ikkilik qidiruv daraxti bilan bir xil. Biz itaramiz ${ displaystyle d_ {i}}$ tugun bilan bog'langan ikkilik yig'indiga va barcha yuqori tugunlar bilan bog'liq minimal va maksimal qiymatlarni yangilang.
Barcha mos keladigan intervallarni qidirish
Keling, foydalanamiz ${ displaystyle a_ {q}, b_ {q}, m_ {q}, d_ {q}}$ so'rovlar oralig'i uchun va ${ displaystyle M_ {n}}$ tugunning kaliti uchun (bilan taqqoslaganda ${ displaystyle m_ {i}}$ intervalgacha)
Ildiz tugunidan boshlab, har bir tugunda, avval bizning so'rovlar oralig'imiz tugunning pastki va eng yuqori qiymatlaridan foydalangan holda tugun pastki daraxtiga to'g'ri kelishi mumkinligini tekshiramiz (agar u bo'lmasa, biz ushbu tugunni davom ettirmaymiz).
Keyin hisoblaymiz ${ displaystyle min left {d_ {i} right }}$ ushbu tugun ichidagi intervallar uchun (uning farzandlari emas) so'rovlar oralig'iga (bilish bilan) to'g'ri keladi ${ displaystyle m_ {i} = M_ {n}}$ ):
${ displaystyle min left {d_ {i} right } = left | m_ {q} -M_ {n} right | -d_ {q}}$
va uning ikkilik yig'indisida so'rovni bajaring ${ displaystyle d_ {i}}$ dan kattaroq ${ displaystyle min left {d_ {i} right }}$
Keyin biz xuddi shu narsani bajarib, tugunning ikkala chap va o'ng bolalari orqali o'tamiz.
Eng yomon holatda, biz ikkitomonlama qidiruv daraxtining barcha tugunlarini skanerlashimiz kerak, ammo ikkilik yig'ish so'rovi maqbul bo'lgani uchun, bu qabul qilinadi (ikki o'lchovli muammo ikkala o'lchovda ham maqbul bo'lolmaydi)
Ushbu algoritm qidiruv operatsiyalari uchun an'anaviy intervalli daraxtdan (kengaytirilgan daraxtdan) tezroq bo'lishi kutilmoqda. Elementlarni qo'shish amalda biroz sekinroq, garchi o'sish tartibi bir xil.
Adabiyotlar

^ ^a ^b Jens M. Shmidt. Kichik tamsayı oralig'ida pichoqlashning intervalli muammolari. DOI. ISAAC'09, 2009 yil
^ # Semigroup operatorlari
Mark de Berg, Mark van Kreveld, Mark Overmars va Otfrid Shvartskopf. Hisoblash geometriyasi, Ikkinchi qayta ishlangan nashr. Springer-Verlag 2000. 10.1-bo'lim: Intervalli daraxtlar, 212-217-betlar.
Kormen, Tomas H.; Leyzerson, Charlz E.; Rivest, Ronald L.; Shteyn, Klifford (2009), Algoritmlarga kirish (3-nashr), MIT Press va McGraw-Hill, ISBN 978-0-262-03384-8
Franko P. Preparata va Maykl Yan Shamos. Hisoblash geometriyasi: kirish. Springer-Verlag, 1985 yil
Tashqi havolalar

CGAL: C ++ da hisoblash geometriyasi algoritmlari kutubxonasi oralig'idagi daraxtlarni mustahkam amalga oshirishni o'z ichiga oladi
Boost.Icl intervalli to'plamlar va xaritalarning C ++ dasturlarini taklif qiladi.
IntervalTree (Python) - belgilangan intervallarga mos AVL balansi bilan markazlashtirilgan intervalli daraxt
Intervalli daraxt (C #) - kengaytirilgan intervalli daraxt, AVL balansi bilan
Intervalli daraxt (yoqut) - markazlashtirilgan intervalli daraxt, o'zgarmas, belgilangan intervallarga mos keladi
IntervalTree (Java) - kengaytirilgan intervalli daraxt, AVL balansi bilan, bir-birini qoplashni qo'llab-quvvatlaydi, topadi, yig'ish interfeysi, id bilan bog'liq intervallar
Daraxtlar ma'lumotlari tuzilmalari
Daraxtlarni qidirish
(dinamik to'plamlar /assotsiativ massivlar )
2–3
2–3–4
AA
(a, b)
AVL
B
B +
B *
B^x
(Optimal ) Ikkilik qidiruv
Raqs
HTree
Interval
Buyurtma statistikasi
(Chapga burilish ) Qizil-qora
Qo'rqoq echki
Splay
T
Treap
UB
Og'irligi muvozanatli
Vayronalar
Ikkilik
Binomial
Brodal
Fibonachchi
Solchi
Ulanish
Nishab
van Emde Boas
Zaif
Harakatlar
Ktri
C-trie (siqilgan ADT)
Xash
Radix
Qo'shimcha
Uchinchi qidiruv
Tezkor
Y-tez
Mekansal ma'lumotlarni ajratish daraxtlari
To'p
BK
BSP
Kartezyen
Hilbert R
k-d (yashirin k-d )
M
Metrik
MVP
Oktri
Priority R
To'rtlik
R
R +
R *
Segment
VP
X
Boshqa daraxtlar
Muqova
Eksponent
Fenvik
Barmoq
Fraktal daraxtlari indeksi
Birlashma
Hash kalendar
iDistance
K-ari
Chap bolaning o'ng ukasi
Bog'lanish / kesish
Kundalik tuzilgan birlashma
Merkle
PQ
Oraliq
SPQR
Yuqori

[Schmidt2009-1] Jens M. Shmidt. Kichik tamsayı oralig'ida pichoqlashning intervalli muammolari. DOI. ISAAC'09, 2009 yil

[2] # Semigroup operatorlari

[1]

[2]

Daraxtlar ma'lumotlari tuzilmalari
Daraxtlarni qidirish (dinamik to'plamlar /assotsiativ massivlar )	2–3 2–3–4 AA (a, b) AVL B B + B * B^x (Optimal ) Ikkilik qidiruv Raqs HTree Interval Buyurtma statistikasi (Chapga burilish ) Qizil-qora Qo'rqoq echki Splay T Treap UB Og'irligi muvozanatli
Vayronalar	Ikkilik Binomial Brodal Fibonachchi Solchi Ulanish Nishab van Emde Boas Zaif
Harakatlar	Ktri C-trie (siqilgan ADT) Xash Radix Qo'shimcha Uchinchi qidiruv Tezkor Y-tez
Mekansal ma'lumotlarni ajratish daraxtlari	To'p BK BSP Kartezyen Hilbert R k-d (yashirin k-d ) M Metrik MVP Oktri Priority R To'rtlik R R + R * Segment VP X
Boshqa daraxtlar	Muqova Eksponent Fenvik Barmoq Fraktal daraxtlari indeksi Birlashma Hash kalendar iDistance K-ari Chap bolaning o'ng ukasi Bog'lanish / kesish Kundalik tuzilgan birlashma Merkle PQ Oraliq SPQR Yuqori