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:
“What I want to say, Linda,
is that there is nothing in your body that lies.
All that is new is telling the truth.
I’m here, that somebody else,
an old tree in the background.”
—Anne Sexton (1928–1974)