心脏供血不足是什么原因引起的

百度 未来美军一旦将相关概念在F-35、F-15、F-16等型战机乃至盟军战机上推广运用，其针对突发事件和地区危机的应急作战能力将大幅提升。

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

Триви?ално реше?е ?е посетити сваки интервал и тестирати да ли пресеца дату тачку или интервал, што захтева Θ(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)