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:
“Even when seen from near, the olive shows
A hue of far away. Perhaps for this
The dove brought olive back, a tree which grows
Unearthly pale, which ever dims and dries,
And whose great thirst, exceeding all excess,
Teaches the South it is not paradise.”
—Richard Wilbur (b. 1921)