Սեգմենտ ծառ

Սեգմենտ ծառ, տվյալների կառուցվածք համակարգչային գիտությունում միջակայքեր կամ հատվածներ պահելու համար։ Այս ծառը ստատիկ կառուցվածք է, որը կառուցվելուց հետո չի ենթարկվում փոփոխության։ Այդպիսի ծառ է նաև միջակայքերի ծառը։
I բազմության և n միջակայքերի համար օգտագործում է 
  
    
      
        O
        (
        n
        l
        o
        g
        n
        )
      
    
    {\displaystyle O(nlogn)}
   հիշողություն և կառուցվում է 
  
    
      
        O
        (
        n
        l
        o
        g
        n
        )
      
    
    {\displaystyle O(nlogn)}
   ժամանակում։
Սեգմենտ ծառերը օգտագործվում են հաշվողական երկրաչափության և աշխարհագրության տեղեկատվական տեխնոլոգիանների ոլորտներում։
Այս բաժինը նկարագրում է սեգմենտ ծառի կառուցվածքը միաչափ տարածությունում։


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

  
    
      
        (
        −
        ∞
        ,
        
          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
          
        
        ,
        +
        ∞
        )
      
    
    {\displaystyle (-\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 )}
  Վերևում նշված է հասարակ միջկայքերի ցուցակ, որոնք պարունակում են երկու հարևան կետերի pi և pi+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