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:
“The tree the tempest with a crash of wood
Throws down in front of us is not to bar
Our passage to our journey’s end for good,
But just to ask us who we think we are....”
—Robert Frost (1874–1963)