Սեգմենտ ծառ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Սեգմենտ ծառ

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

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

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

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

Կառուցվածքի նկարագրություն[խմբագրել | խմբագրել կոդը]

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

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

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

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

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

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. (de Berg et al. 2000, էջ 224)
  2. (de Berg et al. 2000, էջեր 225–226)

Գրականություն[խմբագրել | խմբագրել կոդը]