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:
“Compared to football, baseball is almost an Oriental game, minimizing individual stardom, requiring a wide range of aggressive and defensive skills, and filled with long periods of inaction and irresolution. It has no time limitations. Football, on the other hand, has immediate goals, resolution on every single play, and a lot of violence—itself a highlight. It has clearly distinguishable hierarchies: heroes and drones.”
—Jerry Mander, U.S. advertising executive, author. Four Arguments for the Elimination of Television, ch. 15, Morrow (1978)
“I esteem it the happiness of this country that its settlers, whilst they were exploring their granted and natural rights and determining the power of the magistrate, were united by personal affection. Members of a church before whose searching covenant all rank was abolished, they stood in awe of each other, as religious men.”
—Ralph Waldo Emerson (1803–1882)
“When you are invited by someone to a wedding banquet, do not sit down at the place of honor, in case someone more distinguished than you has been invited by your host...But when you are invited, go and sit down at the lowest place, so that when your host comes, he may say to you, Friend, move up higher’; then you will be honored in the presence of all who sit at the table with you.”
—Bible: New Testament, Luke 14:8,10.
“It is surely a matter of common observation that a man who knows no one thing intimately has no views worth hearing on things in general. The farmer philosophizes in terms of crops, soils, markets, and implements, the mechanic generalizes his experiences of wood and iron, the seaman reaches similar conclusions by his own special road; and if the scholar keeps pace with these it must be by an equally virile productivity.”
—Charles Horton Cooley (1864–1929)
“Our ancestors ... possessed a right, which nature has given to all men, of departing from the country in which chance, not choice has placed them.”
—Thomas Jefferson (1743–1826)