Segment tree

Segment tree

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. Using the segment tree, it can be reported all the intervals that contain a query point in O(log"n" + "k"), being "k" the amount of retrieved intervals or segments. Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|p=227] .

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.

tructure description

"This section describes the structure of a segment tree in a one-dimensional space."

Let "S" be a set of intervals, or segments. Let "p"1, "p"2, ..., "pm" be the list of distinct interval endpoints, sorted from left to right. Consider the partitioning of the real line induced by those points. The regions of this partitioning are called "elementary intervals". Thus, the elementary intervals are, from left to right:

:(-infty, p_1), [p_1,p_1] , (p_1, p_2), [p_2, p_2] , ..., (p_{m-1}, p_m), [p_m, p_m] , (p_m, +infty)

That is, the list of elementary intervals consists of open intervals between two consecutive endpoints "pi" and "p""i"+1, alternated with closed intervals consisting of a single endpoint. Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints [Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|p=224] .

Given a set "I" of intervals, or segments, a segment tree "T" for "I" is structured as follows:
* "T" is a binary tree.
* Its leafs correspond to the elementary intervals induced by the endpoints in "I", in an ordered way: the leftmost leaf corresponds to the leftmost interval, and so on. The elementary intervals corresponding to a leaf "v" is denoted Int("v").
* The internal nodes of "T" corresponds to intervals that are the union of elementary intervals: the interval Int("N") corresponding to node "N" is the union of the intervals corresponding to the leafs of the tree rooted at "N". That implies that Int("N") is the union of the intervals of its two children.
* Each node or leaf "v" in "T" stores the interval Int("v") and a set of intervals, in some data structure. This canonical subset of node "v" contains the intervals ["x", "x′"] from "I" such that ["x", "x′"] contains Int("v") and does not contain Int(parent("v")). That is, each segment in "I" stores the segments that span through its interval, but does not span through the interval of any parent [Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|pp=225–226] .

torage requirements

"This section analyzes the storage cost of a segment tree in a one-dimensional space."

A segment tree "T" on a set "I" of "n" intervals uses O("n"log"n") storage.

:"Proof:"

:"Lemma": Any interval ["x", "x′"] of "I" is stored in the canonical set for at most two nodes at the same depth.

::"Proof": Let "v"1, "v"2, "v"3 be the three nodes at the same depth, numbered from left to right; and let "w" be the parent node of "v"2. Suppose ["x", "x′"] is stored at "v"1 and "v"3. This means that ["x", "x′"] spans the whole interval from the left endpoint of Int("v"1) to the right endpoint of Int("v"3). Because "v"2 lies between "v"1 and "v"3, Int("w") must be contained in ["x", "x′"] . Hence, ["x", "x′"] will not be stored at "v"2.

:The set "I" has at most 4"n" + 1 elementary intervals. Because "T" is a binary balanced tree with at most 4"n" + 1 leaves, its height is O(log"n"). Since any interval is stored at most twice at a given depth of the tree, that the total amount of storage is O("n"log"n") Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|p=226] .

Construction

"This section describes the construction of a segment tree in a one-dimensional space."

A segment tree from the set of segments "I", can be built as follows. First, the endpoints of the intervals in "I" are sorted. The elementary intervals are obtained from that. Then, a balanced binary tree is built on the elementary intervals, and for each node "v" it is determined the interval Int("v") it represents. It remains to compute the canonical subsets for the nodes. To achieve this, the intervals in "I" are inserted one by one into the segment tree. An interval "X" = ["x", "x′"] can be inserted in a subtree rooted at "T", using the following procedure [Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|pp=226–227] :
* If Int("T") is contained in "X" then store "X" at "T", and finish.
* Else:
* If "X" intersects the canonical subset of the left child of "T", then insert "X" in that child, recursively.
* If "X" intersects the canonical subset of the right child of "T", then insert "X" in that child, recursively.The complete construction operation takes O("n"log"n") time, being n the amount of segments in "I".:"Proof"

:Sorting the endpoints takes O("n"log"n"). Building a balanced binary tree from the sorted endpoints, takes linear time on "n".:The insertion of an interval "X" = ["x", "x′"] into the tree, costs O(log"n").::"Proof:" Visiting every node takes constant time (assuming that canonical subsets are stored in a simple data structure like a linked list). When we visit node "v", we either store "X" at "v", or Int("v") contains an endpoint of "X". As proved above, an interval is stored at most twice at each level of the tree. There is also at most one node at every level whose corresponding interval contains "x", and one node whose interval contains "x′". So, at most four nodes per level are visited. Since there are O(log"n") levels, the total cost of the insertion is "O("log"n") .

Query

"This section describes the query operation of a segment tree in a one-dimensional space."

A query for a segment tree, receives a point "qx", and retrieves a list of all the segments stored which contain the point "qx".

Formally stated; given a node (subtree) "v" and a query point "qx", the query can be done using the following algorithm:
* Report all the intervals in I("v").
* If "v" is not a leaf:
** If "qx" is in Int(left child of "v") then
*** Perform a query in the left child of "v".
** Else
*** Perform a query in the right child of "v".

In a segment tree that contains "n" intervals, those containing a given query point can be reported in O(log"n" + "k") time, where "k" is the number of reported intervals.:"Proof:" The query algorithm visits one node per level of the tree, so O(log"n") nodes in total. In the other hand, at a node "v", the segments in "I" are reported in O(1 + "kv") time, where "kv" is the number of intervals at node "v", reported. The sum of all the "kv" for all nodes "v" visited, is "k", the number of reported segments. .

Generalization for higher dimensions

The segment tree can be generalized to higher dimension spaces, in the form of multi-level segment trees. In higher dimension versions, the segment tree stores a collection of axis-parallel (hyper-)rectangles, and can retrieve the rectangles that contain a given query point. The structure uses O("n"log"d"-1"n") storage, and answers queries in O(log"d"n").

The use of fractional cascading lowers the query time bound by a logarithmic factor. The use of the interval tree on the deepest level of associated structures lowers the storage bound with a logarithmic factor. Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|p=230]

Notes

The query that asks for all the intervals containing a given point, is often referred as "stabbing query" .

The segment tree is less efficient than the interval tree for range queries in one dimension, due to its higher storage requirement: O("n"log"n") against the O("n") of the interval tree. The importance of the segment tree is that the segments within each node’s canonical subset can be stored in any arbitrary manner Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|p=229] .

Another plus of the segment tree, is that it can easily be adapted to counting queries; that is, report the amount of segments containing a given point, instead of reporting the segments themselves. Instead of storing the intervals in the canonical subsets, it can simply be stored an integer representing their amount. Such a segment tree uses linear storage, and requires an O("n"log"n") query time, so it is optimal. [Harv |de Berg, van Kreveld, Overmars, Schwarzkopf|2000|pp=229–230]

A version for higher dimensions of the interval tree and the priority search tree does not exist, that is, there is no clear extension of these structures that solves the analogous problem in higher dimensions. But the structures can be used as associated structure of segment trees.

History

The segment tree was discovered by J. L. Bentley in 1977; in "Solutions to Klee’s rectangle problems" .

References

----Citation
last1=de Berg
first1=Mark
last2=van Kreveld
first2=Marc
last3=Overmars
first3=Mark
last4=Schwarzkopf
first4=Otfried
publication-date=2000
year=2000
title=Computational Geometry: algorithms and applications
edition=2nd
publisher=Springer-Verlag Berlin Heidelberg New York
isbn=3-540-65620-0


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Tree sitting — is a form of environmentalist civil disobedience in which a protester sits in a tree, usually on a small platform built for the purpose, to protect it from being cut down (speculating that loggers will not endanger human lives by cutting an… …   Wikipedia

  • Tree (descriptive set theory) — In descriptive set theory, a tree on a set X is a set of finite sequences of elements of X that is closed under subsequences. More formally, it is a subset T of X^{ …   Wikipedia

  • segment — 1. A section; a part of an organ or other structure delimited naturally, artificially, or by invagination from the remainder. SYN: segmentum [TA]. SEE ALSO: metamere. 2. A territory of an organ having independent function, supply, or drainage. 3 …   Medical dictionary

  • segment — noun /ˈsɛgmənt / (say segmuhnt) 1. one of the parts into which anything naturally separates or is naturally divided; a division or section. 2. Geometry a. a part cut off from a figure (especially a circular or a spherical one) by a line or a… …  

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… …   Wikipedia

  • Dancing tree — For the film Dancing tree, see Dancing tree (film) In computer science, a dancing tree is a tree data structure, which is similar to B+ tree. Invented by Hans Reiser, for use by the Reiser4 file system. As opposed to self balancing binary search… …   Wikipedia

  • Hash tree — A binary hash tree In cryptography and computer science Hash trees or Merkle trees are a type of data structure[citation needed] which contains a tree of summary information about a larger piece of da …   Wikipedia

  • Cover tree — The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed up of a nearest neighbor search. It is a refinement of the Navigating Net data structure, and related to a variety of other data… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”