Interval Tree

In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree.

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires Θ(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of m, the number of intervals produced by the query. Interval trees are dynamic, i.e., they allow insertion and deletion of intervals. They obtain a query time of O(log n) while the preprocessing time to construct the data structure is O(n log n) (but the space consumption is O(n)).

Read more about Interval Tree:  Naive Approach, Centered Interval Tree, Augmented Tree, Medial/length Oriented Tree

Famous quotes containing the words interval and/or tree:

    [I have] been in love with one princess or another almost all my life, and I hope I shall go on so, till I die, being firmly persuaded, that if ever I do a mean action, it must be in some interval betwixt one passion and another.
    Laurence Sterne (1713–1768)

    Like to the tree of Tantalus she fled,
    And seeming lavish, sav’de her maydenhead.
    Ne’re king more sought to keepe his diademe;
    Than Hero this inestimable gemme.
    Christopher Marlowe (1564–1593)