Segmentno stablo

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.

U informatici, segmentno stablo je data struktura za čuvanje intervala ili segmenata. Dozvoljava upitivanje koji od sačuvanih segmenata sadrži zadatu tačku. To je u principu statička struktura; njen sadržaj ne može biti modifikovan kada je struktura napravljena.

Segmentno drvo za I od n intervala koristi O(n log n) memorije i može biti napravljeno za O(n log n) vremena.Segmentna drva podržavaju pretraživanje za sve intervale koji sadrže upitnu tačku u O(log n + k), k broj primljenih intervala ili segmenata.

Opis strukture

Ovaj odeljak opisuje strukturu segmentnog drveta u jednodimentionalnom prostoru

Neka S bude set intervala ili segmenata. Neka p₁, p₂, ..., p_m bude lista različitih intervala krajnjih tačaka, sortiranih od leva na desno. Regije ovog particionisanja se zovu elementarni intervali. Elementarni intervali sa leva na desno su:

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

Grafički prikaz strukture segmentnog drveta. Ova instanca je pravljena za segmente prikazane na dnu.

Dato je I od intervala ili segmenata, segmentnog drveta T za I je:

• T je binarno drvo.
• Njegove grane odgovaraju elementarnim intervalima indukovani krajnjum tačkama u I, u poretku: leva grana odgovara levom intervalu, i tako dalje.
• Unutrašnji čvorovi T odgovaraju intervalima koji su unuja unutrašnjih intervala: interval Int(N) odgovara čvoru N je unija intervala koja odgovara granama drveta korena N. To implicira da je Int(N) unija intervala svoje dvoje dece.
• Svaki čvor grane v u T čuva interval Int(v) i set intervala, u nekim data strukturama.^[1]

Zahtevi memorje

Ova sekcija analizira memorijske zahteve segmentnog deveta u jednodimenzionalnom prostoru.

Segmentno drvo T na I od n intervala koristi O(nlogn) memorije.

Dokaz:

Lema: Bilo koji interval [x, x′] od I se čuva u kanonskom sklopu najviše za dva čvora iste dubine.

I ima najviše 4n + 1 elementarnih intervala. Zato što je T binarno balansirano drvo sa najviše 4n + 1 grana, visine O(logn). Since any interval is stored at most twice at a given depth of the tree, that the total amount of storage is O(nlogn).^[2]

Konstrukcija

Ova sekcija opisuje konstrukciju segmentnog drveta u jednodimenzionalnom prostoru.

Segmentno drvo od seta segmenata I, može biti napravljeno na sledeći način:Prvo, krajnje tačke intervala u I su sortirane. Elementarni intervali su preuzeti odatle. Onda, balansirano binarno drvo se pravi na elementarnim intervalima i za svaki čvor v determinisan je interval Int(v) koji predstavlja. Preostaje da se izračunaju kanonske substance za čvorove. Da bismo postigli ovo, intervali u I su ubačeni jedan po jedan u segmentno drvo. Interval X = [x, x′] može biti ubačen u pod drvo sa korenom T, koristeći sledeću proceduru:^[3]

• Ako Int(T) postoji u X onda sačuvati X u T i kraj.
• Inače:
• Ako X se preseca sa kanonskim subsetom levog deteta od T, onda ubaci X u to dete, rekurzivno.
• Ako X se preseca sa kanonskim subsetom desnog deteta od T, onda ubaci X u to dete, rekurzivno.

Kompletna konstrukcija operacija uzima O(nlogn) vremena, n broj segmenata u I. ^[4]

Upit

Ova sekcija opisuje upitne operacije segmentnog drveta u jednodimenzionalnom prostoru.

Upit za segmentno drvo, prima tačku q_x, i prima listu svih segmenata sačuvanih koji sadrže tačku q_x.

Formalno rečeno; dat je čvor (subtree) v i upitna tačka q_x, upit može biti izvede koristeći sledeći algoritam:

• Prijaviti sve intervale u I(v).
• Ako v nije grana:
  • Ako q_x je u Int(levo dete od v) onda
    • Izvršiti upit levog deteta od v.
  • Inače
    • Izvršiti upint desnog deteta od v.

U segmentnom drvetu koje sadrži n intervala, koji sadrže dati upit, tačka može biti reportovana za O(logn + k) vremena, gde je k broj prijavljenih intervala.^[2]

Generalizacija za više dimenzije

Segmentno drvo može biti generalizovano za više dimenzione prostore u formi segmentnih drveta sa više nivoa. U verzijama više dimenzije, segmenta drva čuvaju kolekciju axis-paralelnih hiperuglova, i vraćaju uglove koji sadrže datu upitnu tačku. Struktura koristi O(nlog^d-1n) prostora, I odgovara za O(log^dn).

Reference

1. de Berg, van Kreveld, Overmars, Schwarzkopf 2000, стр. 225–226 harv грешка: no target: CITEREFde_Berg,_van_Kreveld,_Overmars,_Schwarzkopf2000 (help)
2. de Berg, van Kreveld, Overmars, Schwarzkopf 2000, стр. 226 harv грешка: no target: CITEREFde_Berg,_van_Kreveld,_Overmars,_Schwarzkopf2000 (help)
3. de Berg, van Kreveld, Overmars, Schwarzkopf 2000, стр. 226–227 harv грешка: no target: CITEREFde_Berg,_van_Kreveld,_Overmars,_Schwarzkopf2000 (help)
4. de Berg, van Kreveld, Overmars, Schwarzkopf 2000, стр. 227 harv грешка: no target: CITEREFde_Berg,_van_Kreveld,_Overmars,_Schwarzkopf2000 (help)

Literatura

• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Computational Geometry: algorithms and applications (2nd изд.), Springer-Verlag Berlin Heidelberg New York, 3-540-65620-0