«Սեգմենտ ծառ»–ի խմբագրումների տարբերություն
Նոր էջ «Համակարգչային գիտությունում սեգմենտ ծառը տվյալների կառուցվածք է միջակայքեր կամ հատվածներ պահել...»: |
(Տարբերություն չկա)
|
06:20, 30 Հունիսի 2017-ի տարբերակ
Համակարգչային գիտությունում սեգմենտ ծառը տվյալների կառուցվածք է միջակայքեր կամ հատվածներ պահելու համար։ Այս ծառը ստատիկ կառուցվածք է, որը կառուցվելուց հետո չի ենթարկվում փոփոխության։ Այդպիսի ծառ է նաև միջակայքերի ծառը։
I բազմության և n միջակայքերի համար օգտագործում է հիշողություն և կառուցվում է ժամանակում։
Սեգմենտ ծառերը օգտագործվում են հաշվողական երկրաչափության և աշխարհագրության տեղեկատվական տեխնոլոգիանների ոլորտներում։
Այս բաժինը նկարագրում է սեգմենտ ծառի կառուցվածքը միաչափ տարածությունում։
Կառուցվածքի նկարագրություն
Ենթադրենք S-ը միջակայքերի կամ սեգմենտների բազմություն է։ p1, p2, ..., pm հստակ միջակայքերի վերջնակետերն են(դասավորված են ըստ աճման կարգի)։ Հաշվենք, որ գիծը բաժանված է այդ կետերով։ Այդ բաժանման մասերը կոչվում են հասարակ միջակայքեր։
Տրված է միջակայքերի I բազմություն և T սեգմենտ ծառը I բազմությամբ կառուցվում է հետևյալ կերպ՝
- T երկուական ծառ է։
- Տերևները համապատասխանում են վերջնակետերի միջակայքերին սկզբնական կարգով․ ձախ ծայրի տերևը համապատասխանում է ձախ ծայրի միջակայքին և այդպես շարունակ։ Հասարակ միջակայքի, որը համապատասխանում է v նշվում է Int(v)։
- T ներքին գագաթները համապատասխանում են հասարակ միջակայքերի միացմանը։ Int(N)-ը իր երկու երեխաների միջակայքերի միացումն է։
- Յուրաքանչյուր v գագաթ կամ տերև պահում է Int(v) միջակայքը: Այս կանոնական ենթաբազմությունը պարունակում է [x, x′] միջակայքը I-ից այնպես,որ այն պարունակի Int(v)-ն և չպարունակի Int(parent(v))-ն։