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:

$(-\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.

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).

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:

• 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.

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.

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).

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