Սեգմենտ ծառ

Սեգմենտ ծառ
Տեսակ	tree data structure?

Սեգմենտ ծառ, տվյալների կառուցվածք համակարգչային գիտությունում միջակայքեր կամ հատվածներ պահելու համար։ Այս ծառը ստատիկ կառուցվածք է, որը կառուցվելուց հետո չի ենթարկվում փոփոխության։ Այդպիսի ծառ է նաև միջակայքերի ծառը։

I բազմության և n միջակայքերի համար օգտագործում է $O(nlogn)$ հիշողություն և կառուցվում է $O(nlogn)$ ժամանակում։

Սեգմենտ ծառերը օգտագործվում են հաշվողական երկրաչափության և աշխարհագրության տեղեկատվական տեխնոլոգիանների ոլորտներում։

Այս բաժինը նկարագրում է սեգմենտ ծառի կառուցվածքը միաչափ տարածությունում։

Կառուցվածքի նկարագրություն

Ենթադրենք S-ը միջակայքերի կամ սեգմենտների բազմություն է։ p₁, p₂, ..., p_m հստակ միջակայքերի վերջնակետերն են (դասավորված են ըստ աճման կարգի)։ Հաշվենք, որ գիծը բաժանված է այդ կետերով։ Այդ բաժանման մասերը կոչվում են հասարակ միջակայքեր։

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

Վերևում նշված է հասարակ միջկայքերի ցուցակ, որոնք պարունակում են երկու հարևան կետերի p_i և p_i+1 բաց միջակայք, հաջորդելով, փակ միջակայք մեկ կետով։

Սեգմենտ ծառի գրաֆիկական ներկայացումը

Տրված է միջակայքերի I բազմություն և T սեգմենտ ծառը I բազմությամբ կառուցվում է հետևյալ կերպ՝

• T երկուական ծառ է։
• Տերևները համապատասխանում են վերջնակետերի միջակայքերին սկզբնական կարգով․ ձախ ծայրի տերևը համապատասխանում է ձախ ծայրի միջակայքին և այդպես շարունակ։ Հասարակ միջակայքի, որը համապատասխանում է v նշվում է Int(v)։
• T ներքին գագաթները համապատասխանում են հասարակ միջակայքերի միացմանը։ Int(N)-ը իր երկու երեխաների միջակայքերի միացումն է։
• Յուրաքանչյուր v գագաթ կամ տերև պահում է Int(v) միջակայքը։ Այս կանոնական ենթաբազմությունը պարունակում է [x, x′] միջակայքը I-ից այնպես,որ այն պարունակի Int(v)-ն և չպարունակի Int(parent(v))-ն։

Գրականություն

• de Berg Mark, van Kreveld Marc, Overmars Mark, Schwarzkopf Otfried (2000)։ «More Geometric Data Structures»։ Computational Geometry: algorithms and applications (2nd ed.)։ Springer-Verlag Berlin Heidelberg New York։ ISBN 3-540-65620-0։ doi:10.1007/978-3-540-77974-2 
• http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf