Segment träd

Den här artikeln handlar om datastrukturen som används för att lagra segment. För en annan datastruktur som endast används för att effektivt beräkna prefixsummor, se Fenwick-trädet .

Grafiskt exempel på strukturen av segmentträdet. Denna instans är byggd för segmenten som visas längst ner.

Inom datavetenskap är ett segmentträd, även känt som ett statistikträd , en träddatastruktur som används för att lagra information om intervaller eller segment. Det gör det möjligt att fråga vilka av de lagrade segmenten som innehåller en given punkt. Det är i princip en statisk struktur och kan inte modifieras när den väl är byggd. En liknande datastruktur är intervallträdet .

Ett segmentträd för en uppsättning I med n intervall använder O ( n log n ) lagring och kan byggas in i O ( n log n ) tid. Segmentträd stöder sökning efter alla intervall som innehåller en frågetidpunkt O (log n + k ), där k är antalet hämtade intervall eller segment.

Tillämpningar av segmentträdet är inom områdena beräkningsgeometri , geografiska informationssystem och maskininlärning .

Segmentträdet kan generaliseras till utrymmen med högre dimensioner .

Definition

Beskrivning

Låt S vara en uppsättning intervall eller segment. Låt p ₁ , p ₂ , ..., p _m vara listan över distinkta intervallslutpunkter, sorterade från vänster till höger. Tänk på uppdelningen av den verkliga linjen som induceras av dessa punkter. Regionerna för denna partitionering kallas elementära intervall . Således är de elementära intervallen, från vänster till höger:

$(-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{ 2},p_{2}],\dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )$

Det vill säga, listan med elementära intervall består av öppna intervall mellan två på varandra följande slutpunkter pi _alternerade och pi _{+ 1 ,} med slutna intervall som består av en enda slutpunkt. Enstaka punkter behandlas själva som intervall eftersom svaret på en fråga inte nödvändigtvis är detsamma i det inre av ett elementärt intervall och dess slutpunkter.

Givet en uppsättning I av intervall, eller segment, är ett segmentträd T för I strukturerat enligt följande:

• T är ett binärt träd .
• Dess blad motsvarar de elementära intervallen som induceras av ändpunkterna i I , på ett ordnat sätt: bladet längst till vänster motsvarar intervallet längst till vänster, och så vidare. Det elementära intervallet som motsvarar ett blad v betecknas Int( v ).
• De interna noderna i T motsvarar intervall som är föreningen av elementära intervall: intervallet Int( N ) som motsvarar nod N är föreningen av intervallen som motsvarar bladen på trädet med rötter på N . Det innebär att Int( N ) är föreningen av intervallen för dess två barn.
• Varje nod eller blad v i T lagrar intervallet Int( v ) och en uppsättning intervall, i någon datastruktur. Denna kanoniska delmängd av nod v innehåller intervallen [ x , x′ ] från I så att [ x , x′ ] innehåller Int( v ) och inte innehåller Int(parent( v )). Det vill säga att varje nod i T lagrar segmenten som sträcker sig genom dess intervall, men inte sträcker sig genom intervallet för dess förälder.

Konstruktion

Ett segmentträd från uppsättningen av segment I kan byggas enligt följande. Först sorteras ändpunkterna för intervallen i I. De elementära intervallen erhålls från det. Sedan byggs ett balanserat binärt träd på de elementära intervallen, och för varje nod v bestäms intervallet Int( v ) det representerar. Det återstår att beräkna de kanoniska delmängderna för noderna. För att uppnå detta infogas intervallen i I ett efter ett i segmentträdet. Ett intervall X = [ x , x′ ] kan infogas i ett underträd med rötter vid T , med följande procedur:

• Om Int( T ) finns i X , lagra X vid T och avsluta.
• Annan:
  • Om X skär intervallet för det vänstra barnet av T , infoga X i det barnet, rekursivt.
  • Om X skär intervallet för det högra barnet av T , infoga X i det barnet, rekursivt.

Den fullständiga konstruktionsoperationen tar O ( n log n ) tid, n är antalet segment i I.

Bevis

Att sortera ändpunkterna tar O ( n log n ). Att bygga ett balanserat binärt träd från de sorterade ändpunkterna tar linjär tid på n .

Införandet av ett intervall X = [ x , x′ ] i trädet kostar O(log n ).

Bevis

Att besöka varje nod tar konstant tid (förutsatt att kanoniska delmängder lagras i en enkel datastruktur som en länkad lista ). När vi besöker nod v lagrar vi antingen X vid v eller så innehåller Int( v ) en slutpunkt av X . Som visats ovan lagras ett intervall högst två gånger på varje nivå i trädet. Det finns också högst en nod på varje nivå vars motsvarande intervall innehåller x och en nod vars intervall innehåller x′ . Så, högst fyra noder per nivå besöks. Eftersom det finns O (log n ) nivåer är den totala kostnaden för infogningen O (log n ).

Fråga

En fråga för ett segmentträd får en punkt q _x (ska vara ett av trädets blad) och hämtar en lista över alla lagrade segment som innehåller punkten q _x .

Formellt uttalat; givet en nod (underträd) v och en frågepunkt q _x , kan frågan göras med hjälp av följande algoritm:

1. Rapportera alla intervallen i I ( v ) .
2. Om v inte är ett löv:
   • Om q _x är i Int(vänster underordnad av v )
     • utför du en fråga i det vänstra underordnade av v .
   • Om q _x är i Int (höger underordnade av v ) så
     • utför en fråga i det högra underordnade av v .

I ett segmentträd som innehåller n intervall kan de som innehåller en given frågepunkt rapporteras i O (log n + k ) tid, där k är antalet rapporterade intervall.

Bevis

Frågealgoritmen besöker en nod per nivå i trädet, så O (log n ) noder totalt. Å andra sidan, vid en nod kv _v , kv _rapporteras segmenten i I i O (1 + ) tid, där är antalet rapporterade intervall vid nod v . Summan av alla k _v för alla besökta noder v är k , antalet rapporterade segment.

Förvaringskrav

Ett segmentträd T på en uppsättning I med n intervall använder O ( n log n ) lagring.

Lemma — Varje intervall [ x , x′ ] av I lagras i den kanoniska uppsättningen för högst två noder på samma djup.

Bevis

Låt v ₁ , v ₂ , v ₃ vara de tre noderna på samma djup, numrerade från vänster till höger; och låt p( v ) vara modernoden för vilken given nod v som helst . Antag att [ x , x′ ] lagras vid v ₁ och v ₃ . Detta betyder att [ x , x′ ] spänner över hela intervallet från den vänstra slutpunkten för Int( v ₁ ) till den högra slutpunkten för Int( v ₃ ). Observera att alla segment på en viss nivå är icke-överlappande och ordnade från vänster till höger: detta är sant genom konstruktion för nivån som innehåller bladen, och egenskapen går inte förlorad när man flyttar från någon nivå till den ovanför den genom att kombinera par av angränsande segment. Nu är antingen parent( v ₂ ) = parent( v ₁ ), eller den förra till höger om den senare (kanterna i trädet korsar inte). I det första fallet är Int(parent( v ₂ ))s punkt längst till vänster densamma som Int( v ₁ )s punkt längst till vänster; i det andra fallet är Int(parent( v ₂ ))s punkt längst till vänster till höger om Int(parent( v ₁ ))s punkt längst till höger, och därför även till höger om Int( v ₁ ) längst till höger punkt. I båda fallen börjar Int(parent( v ₂ )) vid eller till höger om Int( v ₁ )s punkt längst till vänster. Liknande resonemang visar att Int(parent( v ₂ )) slutar vid eller till vänster om Int( v ₃ )s punkt längst till höger. Int(parent( v ₂ )) måste därför finnas i [ x , x′ ]; därför kommer [ x , x′ ] inte att lagras vid v ₂ .

Uppsättningen I har som mest 4 n + 1 elementära intervall. Eftersom T är ett binärt balanserat träd med högst 4 n + 1 löv, är dess höjd O(log n ). Eftersom vilket intervall som helst lagras högst två gånger på ett givet djup av trädet, är den totala mängden lagring O ( n log n ).

Generalisering för högre dimensioner

Segmentträdet kan generaliseras till utrymmen med högre dimension, i form av segmentträd med flera nivåer. I versioner med högre dimensioner lagrar segmentträdet en samling axelparallella (hyper)rektanglar och kan hämta de rektanglar som innehåller en given frågepunkt. Strukturen använder O ( n log ^d n ) lagring och svarar på frågor i O ( log ^d n ) tid.

Användningen av fraktionerad kaskad sänker frågetiden bunden av en logaritmisk faktor. Användningen av intervallträdet på den djupaste nivån av associerade strukturer sänker lagringsbunden av en logaritmisk faktor.

Anteckningar

En fråga som frågar efter alla intervall som innehåller en given punkt kallas ofta för en stickande fråga .

Segmentträdet är mindre effektivt än intervallträdet för intervallfrågor i en dimension, på grund av dess högre lagringskrav: O ( n log n ) mot O( n ) i intervallträdet. Vikten av segmentträdet är att segmenten inom varje nods kanoniska delmängd kan lagras på vilket godtyckligt sätt som helst.

För n intervall vars ändpunkter ligger i ett litet heltalsintervall (t.ex. i intervallet [1,..., O ( n )]), optimala datastrukturer existerar med en linjär förbehandlingstid och frågetid O (1 + k ) för att rapportera alla k intervall som innehåller en given frågepunkt.

En annan fördel med segmentträdet är att det enkelt kan anpassas till att räkna frågor; det vill säga att rapportera antalet segment som innehåller en given punkt, istället för att rapportera själva segmenten. Istället för att lagra intervallen i de kanoniska delmängderna kan den helt enkelt lagra antalet av dem. Ett sådant segmentträd använder linjär lagring och kräver en O (log n ) frågetid, så det är optimalt.

Högdimensionella versioner av intervallträdet och prioritetssökningsträdet finns inte; det vill säga det finns ingen tydlig förlängning av dessa strukturer som löser det analoga problemet i högre dimensioner. Men strukturerna kan användas som tillhörande struktur av segmentträd.

Historia

Segmentträdet uppfanns av Jon Bentley 1977; i "Lösningar på Klees rektangelproblem".

Angivna källor

•   de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). "Fler geometriska datastrukturer". Computational Geometry: Algoritms and applications (2nd ed.). Springer-Verlag Berlin Heidelberg New York. doi : 10.1007/978-3-540-77974-2 . ISBN 3-540-65620-0 .
• http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

externa länkar

• Segmentträd – CP-algoritmer