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:
“I expect a time when, or rather an integrity by which, a man will get his coat as honestly and as perfectly fitting as a tree its bark. Now our garments are typical of our conformity to the ways of the world, i.e., of the devil, and to some extent react on us and poison us, like that shirt which Hercules put on.”
—Henry David Thoreau (1817–1862)