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

Из Википедије, слободне енциклопедије

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

Тривијално решење је посетити сваки интервал и тестирати да ли пресеца дату тачку или интервал, што захтева Θ(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, pp. 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\}

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

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

Литература[уреди]

Спољашње везе[уреди]