«Սեգմենտ ծառ»–ի խմբագրումների տարբերություն

Ավելացվել է 1406 բայտ ,  4 տարի առաջ
(Նոր էջ «Համակարգչային գիտությունում սեգմենտ ծառը տվյալների կառուցվածք է միջակայքեր կամ հատվածներ պահել...»:)
 
 
:<math>(-\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)</math>
 
Վերևում նշված է հասարակ միջկայքերի ցուցակ, որոնք պարունակում են երկու հարևան կետերի ''p<sub>i</sub>'' և ''p''<sub>''i''+1</sub> բաց միջակայք, հաջորդելով, փակ միջակայք մեկ կետով<ref>{{Harv |de Berg|van Kreveld|Overmars|Schwarzkopf|2000|p=224}}</ref>։
That is, the list of elementary intervals consists of open intervals between two consecutive endpoints pi and pi+1, alternated with closed intervals consisting of a single endpoint. Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints.[2]
 
[[Image:Segment tree instance.gif|frame|Սեգմենտ ծառի գրաֆիկական ներկայացումը։]]
* Տերևները համապատասխանում են վերջնակետերի միջակայքերին սկզբնական կարգով․ ձախ ծայրի տերևը համապատասխանում է ձախ ծայրի միջակայքին և այդպես շարունակ։ Հասարակ միջակայքի, որը համապատասխանում է ''v'' նշվում է Int(''v'')։
* ''T'' ներքին գագաթները համապատասխանում են հասարակ միջակայքերի միացմանը։ Int(N)-ը իր երկու երեխաների միջակայքերի միացումն է։
*Յուրաքանչյուր ''v'' գագաթ կամ տերև պահում է Int(v) միջակայքը: Այս կանոնական ենթաբազմությունը պարունակում է [x, x′] միջակայքը ''I''-ից այնպես,որ այն պարունակի Int(v)-ն և չպարունակի Int(parent(v))-ն։ն<ref>{{Harv |de Berg|van Kreveld|Overmars|Schwarzkopf|2000|pp=225&ndash;226}}</ref>։
 
== Ծանոթագրություններ ==
{{ծանցանկ}}
 
== Գրականություն ==
* {{cite book
| last1=de Berg
| first1=Mark
| last2=van Kreveld
| first2=Marc
| last3=Overmars
| first3=Mark
| last4=Schwarzkopf
| first4=Otfried
| publication-date=2000
| year=2000
| title=Computational Geometry: algorithms and applications
| edition=2nd
| publisher=Springer-Verlag Berlin Heidelberg New York
| isbn=3-540-65620-0
| chapter = More Geometric Data Structures
| doi = 10.1007/978-3-540-77974-2
| ref=harv
}}
* http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf
 
[[Կատեգորիա:Երկուական ծառեր]]
[[Կատեգորիա:Ծառեր (Տվյալների կառուցվածք)]]
505

edits