Range Searching and Lowest Common Ancestors
Cartesian trees may be used as part of an efficient data structure for range minimum queries, a range searching problem involving queries that ask for the minimum value in a contiguous subsequence of the original sequence. In a Cartesian tree, this minimum value may 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) of the 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 15). Because lowest common ancestors may be found in constant time per query, using a data structure that takes linear space to store and that may be constructed in linear time, the same bounds hold for the range minimization problem.
Bender & Farach-Colton (2000) reversed this relationship between the two data structure problems by showing that lowest common ancestors in an input tree could be solved efficiently applying a non-tree-based technique for range minimization. Their data structure uses an Euler tour technique to transform the input tree into a sequence and then finds range minima in the resulting sequence. The sequence resulting from this transformation has a special form (adjacent numbers, representing heights of adjacent nodes in the tree, differ by ±1) which they take advantage of in their data structure; to solve the range minimization problem for sequences that do not have this special form, they use Cartesian trees to transform the range minimization problem into a lowest common ancestor problem, and then apply the Euler tour technique to transform the problem again into one of range minimization for sequences with this special form.
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 may be used to form a Cartesian tree, by sorting the points by their x-coordinates and using the y-coordinates in this order as the sequence of values from which this tree is formed. If S is the subset of the input points within some vertical slab defined by the inequalities L ≤ x ≤ R, p is the leftmost point in S (the one with minimum x-coordinate), and q is the rightmost point in S (the one with maximum x-coordinate) then the lowest common ancestor of p and q 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 L ≤ x ≤ R and y ≤ T, may be answered by finding this bottommost point b, comparing its y-coordinate to T, and (if the point lies within the three-sided region) continuing recursively in the two slabs bounded between p and b and between b and q. In this way, after the leftmost and rightmost points in the slab are identified, all points within the three-sided region may be listed in constant time per point.
The same construction, of lowest common ancestors in a Cartesian tree, makes it possible to construct a data structure with linear space that allows the distances between pairs of points in any ultrametric space to be queried in constant time per query. The distance within an ultrametric is the same as the minimax path weight in the minimum spanning tree of the metric. From the minimum spanning tree, one can construct a Cartesian tree, the root node of which represents the heaviest edge of the minimum spanning tree. Removing this edge partitions the minimum spanning tree into two subtrees, and Cartesian trees recursively constructed for these two subtrees form the children of the root node of the Cartesian tree. The leaves of the Cartesian tree represent points of the metric space, and the lowest common ancestor of two leaves in the Cartesian tree is the heaviest edge between those two points in the minimum spanning tree, which has weight equal to the distance between the two points. Once the minimum spanning tree has been found and its edge weights sorted, the Cartesian tree may be constructed in linear time.
Read more about this topic: Cartesian Tree
Famous quotes containing the words range, searching, lowest, common and/or ancestors:
“The Canadians of those days, at least, possessed a roving spirit of adventure which carried them further, in exposure to hardship and danger, than ever the New England colonist went, and led them, though not to clear and colonize the wilderness, yet to range over it as coureurs de bois, or runners of the woods, or, as Hontan prefers to call them, coureurs de risques, runners of risks; to say nothing of their enterprising priesthood.”
—Henry David Thoreau (1817–1862)
““Why were you searching for me? Did you not know that I must be in my Father’s house?””
—Bible: New Testament, Luke 2:49.
Jesus to his parents when they found him in the temple.
“The lowest form of popular culture—lack of information, misinformation, disinformation, and a contempt for the truth or the reality of most people’s lives—has overrun real journalism. Today, ordinary Americans are being stuffed with garbage.”
—Carl Bernstein (b. 1944)
“By common consent of all the nations and all the ages the most valuable thing in this world is the homage of men, whether deserved or undeserved.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“Our ancestors were savages. The story of Romulus and Remus being suckled by a wolf is not a meaningless fable. The founders of every state which has risen to eminence have drawn their nourishment and vigor from a similar wild source. It was because the children of the Empire were not suckled by the wolf that they were conquered and displaced by the children of the northern forests who were.”
—Henry David Thoreau (1817–1862)