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:

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

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 
 

Стабла (структуре података)
Бинарна стабла
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 : 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 +elementarnih intervala . Zato što je T binarno balansirano drvo sa najviše +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 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 . 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 Стабла ( структуре података ) Бинарна стабла