Content deleted Content added
→Applications: per GA1 |
|||
Line 30:
Cartesian trees form part of an efficient data structure for [[Range Minimum Query|range minimum queries]]. An input to this kind of query specifies a contiguous subsequence of the original sequence; the query output should be the minimum value in this subsequence.<ref>{{harvtxt|Gabow|Bentley|Tarjan|1984}}; {{harvtxt|Bender|Farach-Colton|2000}}.</ref> In a Cartesian tree, this minimum value can be found at the [[lowest common ancestor]] of the leftmost and rightmost values in the subsequence. For instance, in the subsequence (12,10,20,15,18) of the example sequence, the minimum value of the subsequence (10) forms the lowest common ancestor of the leftmost and rightmost values (12 and 18). Because lowest common ancestors can be found in constant time per query, using a data structure that takes linear space to store and can be constructed in linear time, the same bounds hold for the range minimization problem.<ref>{{harvtxt|Harel|Tarjan|1984}}; {{harvtxt|Schieber|Vishkin|1988}}.</ref>
{{harvtxt|Bender|Farach-Colton|2000}} reversed this relationship between the two data structure problems by showing that data structures for range minimization could also be used for finding lowest common ancestors. Their data structure associates with each node of the tree its distance from the root, and constructs a sequence of these distances in the order of an [[Euler tour]] of the (edge-doubled) tree. It then constructs a range minimization data structure for the resulting sequence. The lowest common ancestor of any two vertices in the given tree can be found as the minimum distance appearing in the interval between the initial positions of these two vertices in the sequence. Bender and Farach-Colton also provide a method for range minimization that can be used for the sequences resulting from this transformation, which have the special property that adjacent sequence values differ by
The same range minimization problem may also be given an alternative interpretation in terms of two dimensional range searching. A collection of finitely many points in the [[Cartesian plane]] can be used to form a Cartesian tree, by sorting the points by their <math>x</math>-coordinates and using the <math>y</math>-coordinates in this order as the sequence of values from which this tree is formed. If <math>S</math> is the subset of the input points within some vertical slab defined by the inequalities <math>L\le x\le R</math>, <math>p</math> is the leftmost point in <math>S</math> (the one with minimum <math>x</math>-coordinate), and <math>q</math> is the rightmost point in <math>S</math> (the one with maximum <math>x</math>-coordinate) then the lowest common ancestor of <math>p</math> and <math>q</math> in the Cartesian tree is the bottommost point in the slab. A three-sided range query, in which the task is to list all points within a region bounded by the three inequalities <math>L\le x\le R</math> and <math>y\le T</math>, can be answered by finding this bottommost point <math>b</math>, comparing its <math>y</math>-coordinate to <math>T</math>, and (if the point lies within the three-sided region) continuing recursively in the two slabs bounded between <math>p</math> and <math>b</math> and between <math>b</math> and <math>q</math>. In this way, after the leftmost and rightmost points in the slab are identified, all points within the three-sided region can be listed in constant time per point.{{sfnp|Gabow|Bentley|Tarjan|1984}}
| |||