Cartesian tree: Difference between revisions

Revision as of 22:26, 13 August 2023

Revision as of 00:48, 14 August 2023

Line 28:

===Range searching and lowest common ancestors===

[[File:Cartesian tree range searching.svg|thumb|300px|Two-dimensional range-searching using a Cartesian tree: the bottom point (red in the figure) within a three-sided region with two vertical sides and one horizontal side (if the region is nonempty) can be found as the nearest common ancestor of the leftmost and rightmost points (the blue points in the figure) within the slab defined by the vertical region boundaries. The remaining points in the three-sided region can be found by splitting it by a vertical line through the bottom point and recursing.]]

Cartesian trees form part of an efficient [[data structure]] for [[Range Minimum Query|range minimum queries]],. aAn [[rangeinput searching]]to problemthis involvingkind queriesof thatquery askspecifies fora contiguous subsequence of the minimumoriginal valuesequence; inthe aquery contiguousoutput subsequenceshould ofbe the originalminimum sequencevalue 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 shown in the first illustration, the minimum value of the subsequence (10) forms the lowest common ancestor of the leftmost and rightmost values (12 and 1518). 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 ±1. As they describe, for range minimization in sequences that do not have this form, it is possible to use Cartesian trees to reduce the range minimization problem to lowest common ancestors, and then to use Euler tours to reduce lowest common ancestors to a range minimization problem with this special form.{{sfnp|Bender|Farach-Colton|2000}}