Սեգմենտ ծառ

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

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

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

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

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

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

$(-\mathrm{\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,+\mathrm{\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))-ն։

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

• Կաղապար:Cite book
• http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf