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 p1, p2, ..., pm 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. [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 qx, i prima listu svih segmenata sačuvanih koji sadrže tačku qx.

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

  • Prijaviti sve intervale u I(v).
  • Ako v nije grana:
    • Ako qx 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(nlogd-1n) prostora, I odgovara za O(logdn).

Reference[уреди]

Literatura[уреди]

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