In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.
A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.
Applications of the segment tree are in the areas of computational geometry, and geographic information systems.
The segment tree can be generalized to higher dimension spaces as well.
Read more about Segment Tree: Structure Description, Storage Requirements, Construction, Query, Generalization For Higher Dimensions, Notes, History
Famous quotes containing the word tree:
“On a tree by a river a little tom-tit
Sang “Willow, titwillow, titwillow!”
And I said to him, “Dicky-bird, why do you sit
Singing, ‘Willow, titwillow, titwillow’?
Is it a weakness of intellect, birdie?” I cried,
“Or a rather tough worm in your little inside?””
—Sir William Schwenck Gilbert (1836–1911)