Интервал стабла

У рачунарству, интервал стабла је уређено стабло структуре података које садржи интервале. Прецизније, дозвољава да ефикасно нађе све интервале који се преклапају са било којим датим интервалима или тачкама. Често се користи за уоквирено испитивање, на пример, да би нашли све путеве на компјутеризованој мапи унутар правоугаоног невезаног прозора, или да би нашли све видљиве елементе унутар тродимензионалне сцене. Слична структура података је сегментно стабло.

Тривијално решење је посетити сваки интервал и тестирати да ли пресеца дату тачку или интервал, што захтева Θ(n) времена, где је n број интерваала у скупу. Како се питање може вратити на све интервале, на пример ако испитан је велики интервал који пресеца све интервале унутар скупа, ово је асимптотски оптимално; како год, можемо и боље имајући у виду излазно-осетљиве алгоритме, где је дужина трајања изражена у термину m, број интервала произведен испитивањем. Интервал стабла је динамичан, другим речима, он дозвољавају уметање и брисање интервала. Он садрже време испитивања O(log n) док је предпроцесорско време да коструише структуру података O(n log n) (али просторно је O(n)).

Наивни приступ

У простом случају, интервали се не преплићу и могу бити уметнути у просто бинарно стабло претраге и испитани у O(log n) времену. Како год, са произвољним преплитањем интервала, не постоји шанса поредити два интервала за уметање у стабло пошто је уређивање сортирано почетним тачкама или крајњим тачкама које могу бити другачије. Наивни приступ може бити да се направе два паралелна стабла, једно уређено почетним тачкама, друго крајњим тачкама сваког интервала. Ово дозвољава одбацивање пола стабла у O(log n) времену, али резултат мора бити спајање, које захтева O(n) време. Ово нам даје испитаност у O(n + log n) = O(n), што није боље од примитивне-силе.

Интервал стабла решава овај проблем. Овај чланак описује два алтернативна дизајна за интервал стабала, завани централизован интервал стабла и повећано стабло.

Централизован интервал стабла

Упити захтевају O(log n + m) времена, са n тоталним бројем интервала и m бројем пријављених резултата. Конструкција захтева O(n log n) времена, и складиштење O(n) простора.

Конструкција

Дат је сет од n интервала на бројној линији, а ми желимо да конструишемо структуру података тако да можемо ефикасно да вратимо све преклапајуће интервале или тачке.

Почињемо узимањем целог домета свих интервала и делимо га на пола у x_центру (у пракси, x_центар би требало да је биран да сачува стабло релативно балансираним). Ово даје 3 сета интервала, они скроз лево од x_центра које зовемо S_лево, они скроз десно од x_центра које зовемо S_десно, и они који се преклапају у x_центар које зовемо S_центар.

Интервали у S_лево и S_десно су рекурзивно подељени на исти начин све док не буде више интервала лево.

Интервали у S_центру који преклапају централну тачку су сачувани у одвојеној структури података повезани са чвором з интервалу стабла. Ова структура података се сатоји од две листе, једна садржи све интервале сортиране почетним тачкама, друга све интервале сортиране крајњим тачкама.

Резултат је тречестепено стабло са сваким чввором сортираним:

Централном тачком
Тачком до чвора који садржи све интервале лево од централне тачке
Тачком до чвора који садржи све интервале десно од централне тачке
Све интервале који преклапају централну тачку сортирану почетним тачкама
Све интервале који преклапају централну тачку сортирану крајњим тачкама

Укрштање

Дато структуром података коструисаном у пасусу изнад, добијамо упите који се садрже од домена и тачака, и враћа све домене у оригиналну колекцију улазних преклапања.

Са интервалом

Прво, можемо да смањимо случај где је интервал R дат као улаз сличном случају као што је дата за улаз једна тачка. Прво нађемо све домене са почетним или крајњим тачкама унутар улазног интервала R користећи одвојено конструисана стабла. У једно-димензионалном случају, можемо да користимо једноставно стабло које садржи све почетне и крајње тачке интервала, сваку са показивачем који одговара свом интервалу.

Бинарна претрага у O(log n) времену за почетак и крај R открива минимум и максимум тачака. Свака тачка у овом домену референцира интервал који се преклапа са нашим доменом и убацује се у листу резултата. Мора се обратити пажња на дуплирање, како интервал може да почне и да се заврши унутар R. Ово може бити урађено користећи бинарни флег за сваки интервал да би означили да ли јесте или није убачен у резултат.

Интервали који нису укључени су они који преклапају R који немају крајње тачке унутар R, другим речима, интервали који га затварају. Да би нашли ове, бирамо било које тачке унутар R и користимо алгоритам испод да нађемо све интервале који се укрштају у тој тачки (поново, пазећи на дуплирање).

Са тачкама

Задатак је да нађемо све интервале у стаблу који преклапају дату тачку x. Дрво је пропраћено са сличним рекурзивним алгоритмом као што би било коршћено обилажење традиционалног бинарног стабла, али са додатним дозвољавањем преклапања итервала у "центру" тачке сваког чвора.

За сваки чвор стабла, x се пореди са x_центром, средишна тачка се користи у конструкцији чвора изнад. Ако x је мања од x_center, крајња лева група интервала, S_лево, се узимају у обзир. Ако x је веће од x_центра, крајњи десни интервали, S_десно, се узимају у обзир.

Како је сваки чвор обрађен док ми обилазимо стабло од корена до листа, домен у њему је S_ценатр обрађен. Ако x је мање од x_центра, знамо да сви интервали у S_центру се завршавају после x, и да такође не могу да се преклапају у x_центру. Тако да, треба да нађемо само оне интервале у S_центру који почињу пре x. Можемо да консултујемо листу од S_центра коју смо већ направили. С обзиром да овде бринемо само о почетним интервалима, можемо да консултујемо листу сортирану од почетка. И да нађемо најближи број не већи од x у овој листи. Сви домени од почетка листе до нађене тачке преклапања x зато што почињу од x и завршавају се после x. Можемо једноставно да почнемо да енумеришемо интервале у листи док крајња вредност не пређе x.

Исто тако, ако x је веће од x_центра, знамо да сви интервали у S_центру морају да почну пре x, налазимо интервале који се завршавају после x користећи листу сортирану крајњим интервалима.

Ако x тачно одговара x_центру, сви интервали у S_центру могу бити додати у резултате без даљег обрађивања и обилазак стабла може престати.

Више димензије

Интервал стабла структуре података може бити генерализован на више димензије N са идентичним испитивањем и кострукционим временом и O(n log n) простором.

Прво, просторно стабло димензије N је направљено тако да дозвољава ефикасан повраћај свих интервала са почетним и крајњим тачкама унутар региона упита R. Када су одговарајући домети нађени, једино што је остало су домети који ограђују домет у некој димензији. Да бисмо нашли ова преклапања, N интервал стабла је креиран, и један отац пресецајући R је упит за сваки. На пример, у две димензије, дно квадрата R био би испитан против интервала стабла конструкције за хоризонталног оца. Исто тако, био би испитан против интервала стабла конструкције за вертикалног оца.

Сваком интервалу стабла такође треба допуна за више димензије. Код сваког чвора у обилажењу стабла, x је поређено са S_центром да би нашли преклапања. Уместо две сортиране листе тачака као што је коришћено у једно-димензионалним случајевима, домен стабла је конструисан. Ово могућава ефикасан повратак свих тачака у S_центру који преклапа регион R.

Брисање

Ако после брисања интервала из стабла, чвор који садржи тај интервал више не, онда може бити обрисан из стабла. Ово је много сложеније него брисање код нормалног бинарног стабла.

Интервал може да преклапа централну тачку неколико чворова у стаблу. Пошто сваки чвор садржи интервал који је преклапа, са свим интервалима скроз лево од центра тачке у левом подстаблу, слично и за десно под стабло, прати да сваки интервал је сортиран у чвору најближем корену из групе чворова коме је централна тачка преклапање.

Нормално брисање у бинарном стабу укључује унапређивање чвора даље од корена до позиције обрисаног чвора. Као резултат овог унапређења, неки чворови који су били изнад унапређеног чвора постаће његови потомци; неопходно је тражити ове чворове за интервале који такође преклапају унапређен чвор, и помера те интервале у унапређени чвор. као последица, ово може резултовати празним чвором, који мора бити обрисан, пратећи исти алгоритам.

Балансирање

Исте проблем који прати брисање такође утиче на ротирање; ротирање мора сачувати инваријанте у којима су интервали складиштени што је ближе могуће корену.

Повећано стабло

Још један начин да се презентују интервали је да се опишу у Cormen et al. 2001, Section 14.3: Interval trees. стр. 311-317.

И уметање и брисање захтева O(log n) времена, са n тоталним бројем интервала.

Користећи једноставно уређено стабло, на пример, бинарно стабло претраге или самобалансирајуће бинарно стабло претраге, где је стабло уређено са 'слабом' вредношћу интервала, и са додатном анотацијом је додато сваком чвору забележавање максималне вредности подстабла. Овај атрибут је једноставан за одржавање само са O(h) корака током сваког додатног или уклоњеног чвора, где h је висина додатог или укоњеног чвора у стаблу, унапређујући све претке чвора одоздо на горе. Додатно, ротација стабла коришћена током уметања брисања може да захтева дорађивање високе вредност задешених чворова.

Сад, познато је да два интервала A и B се преклапају само кад оба A.мање ≤ B.веће и A.веће ≥ B.мање. Када претражујемо стабло за чворове који се преклапају са датим интервалима, мозете одма прескочити:

сви чворови десно од чворова чија је доња вредност прошла крај датог интервала.
сви чворови који имају свој максималну 'високу' вредост испод почетка датог интервала.

Тотални ред може бити дефинисан на интервалима уређујучи их прво према њиховој 'ниској' вредности и коначни и њиховој „високој” вредности. Ово уређивање може бити коришћено да спречи дуплирање интервала од уметања у стабло у O(log n) времену, уместо O(k + log n) време потребо за проналажење дупликата ако k интервали преклапају нови интервал.

Java Пример: Додавање нових интервала у стабло

Кључ сваког чвора је сам интервал и вредност сваког чвора је крајња тачка интервала:

 public void add(Interval i) {
     put(i, i.getEnd());
 }

Java Пример: Претрага тачки или интервала у стаблу

Да би тражили интервале, петамо по стаблу, изостављајући оне гране које не могу да садрже оно што се тражи. Једноставан начин је да се тражи тачка:

 // Нађи све интервале који садрже "p", почећи од
 // чвора "n" и додајући подударајуће интервале у листу "result"
 public void search(IntervalNode n, Point p, List<Interval> result) {
     // Don't search nodes that don't exist
     if (n == null)
         return;
 
     // Ако p је десно од најдешњије тачке било ког интервала
     // у овом чвору и свој деци, неће бити подударања.
     if (p.compareTo(n.getValue()) > 0)
         return;
 
     // Претражи десну децу
     if (n.getLeft() != null)
         search(IntervalNode (n.getLeft()), p, result);
 
     // Провери овај чвор
     if (n.getKey().contains(p))
         result.add(n.getKey());
 
     // Ако p је лево од почетка интервала,
     // онда не може бити ни у једној деци десно.
     if (p.compareTo(n.getKey().getStart()) < 0)
         return;
 
     // Иначе, претражи десну децу
     if (n.getRight() != null)
         search(IntervalNode (n.getRight()), p, result);
 }

Код за тражење интервала је потпуно исти само има проверу у средини:

 // Провери овај чвор
 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 координате, парни нивои стабла могу да садрже домен за y координате. Како год, није сасвим очигледно да ће логика ротације да буде продужена за такве случајеве да би задржала стабло балансираним.

Много једноставније решење је да се користе уметнути интервали стабла. Прво, креирај стабло користећи домен за y координате. Сад, за сваки чвор стабла, додај још један интервал на x домене, за све елементе чији y домен пресеца чворове је y домен.

Предност овог решења је та да може бити продужено на произвољну димензију користећи исти базни код.

У почетку, цена за додатна стабла би изгледала превисоком али то обично није случај. Са решењем горе, треба ти само један чвор по x координати, цена је онда иста у оба случаја. Једина разлика је та да ти треба додатно структуирано стабло по вертикали интервала. Ова структура је обично јако мала.

Медијски/дужински оријентисано стабло

Слично Увећаном стаблу, али на симетричан начин, где Бинарно стабло претраге је уређено Медијским тачкама интервала. И постоји Максимум-оријентисаних Бинарни хипова у сваком чвору, уређено по дужини интервала (или пола дужине). Такође смештамо минималну могућу вредност подстабла у сваком чвору, додатно максималној могућој вредности (зато је симетрично).

Тест преклапања

Користећи само почетне и крајње вредности два интервала $\left(a_{i},b_{i}\right)$ , за $i=0,1$ , тест преклапања може бити изведен:

$a_{0}\leqslant a_{1}<b_{0}$ OR $a_{0}<b_{1}\leqslant b_{0}$ OR $a_{1}\leqslant a_{0}<b_{1}$ OR $a_{1}<b_{0}\leqslant b_{1}$

Али са дефинисањем:

$m_{i}={\frac {a_{i}+b_{i}}{2}}$

$d_{i}={\frac {b_{i}-a_{i}}{2}}$

Тест преклапања је сличан:

$\left|m_{1}-m_{0}\right|<d_{0}+d_{1}$

Додавање интервала

Додавање нових интервала у стабо је исто као БСП, само користимо медијуску вредност као кључ, и кад нађемо/направимо чвор да ставимо интервал. Требало би да избацимо $d_{i}$ до Бинарног хипа повезаног са чвором и да унапредимо минималне и максималне могуће вредности повезане са свим вишим чворовима.

Тражење свих преклапајућих интервала

Да користимо $a_{q},b_{q},m_{q},d_{q}$ за упит интервала, и $M_{n}$ за кључ чвора (у поређењу са $m_{i}$ од интервала)

Крећући са кореном, у сваком чвору, прво проверимо да ли је могуће да се наш испитиван интервал преклапа са чвором подстабла користећи минималне и максималне вредности чвора (ако не, не идемо даље за овај чвор).

Онда израчунамо $\min \left\{d_{i}\right\}$ за интервал унутар овог чвора (не за његову децу) да ли се преклапа са испитаним интервалом (знајући $m_{i}=M_{n}$ ):

$\min \left\{d_{i}\right\}=\left|m_{q}-M_{n}\right|-d_{q}$ И изводећи испитивање Бинарни хип за $d_{i}$ већи од $\min \left\{d_{i}\right\}$

Онда прођемо кроз оба лева и десна детета чвора, радећи исто. У најгорем случају, морамо да скенирамо све чворове БСП-а, али пошто Бинарни хип испитује оптимум, нема много бриге.

За овај алгоритам је очекивано да буде бржи од традиционалног Интервала стабла (Увећано стабло) у претрагама, додавање је само нешто спорије (уређење расте је исто).

Референце

Литература

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 10.1: Interval Trees. стр. 212–217.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd изд.), MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3
Franco P. Preparata and Michael Ian Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985

Спољашње везе

CGAL : Computational Geometry Algorithms Library in C++ contains a robust implementation of Range Trees
Interval Tree (an augmented self balancing avl tree implementation)