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:
“[F]or as Socrates says that a wise man is a citizen of the world, so I thought that a wise woman was equally at liberty to range through every station or degree of men, to fix her choice wherever she pleased.”
—Sarah Fielding (1710–1768)
“I have been searching history to see if really a woman has any precedent to claim the right to have her rights, and I am compelled to say that we men are not so much ahead of women after all, and the only way we have kept our reputation up is by keeping her down—and don’t you forget it!”
—George E. Foster, U.S. women’s magazine contributor. The Woman’s Magazine, pp. 38-41 (October 1886)
“Great abilites are not requisite for an Historian; for in historical composition, all the greatest powers of the human mind are quiescent. He has facts ready to his hand; so there is no exercise of invention. Imagination is not required in any degree; only about as much as is used in the lowest kinds of poetry. Some penetration, accuracy, and colouring, will fit a man for the task, if he can give the application which is necessary.”
—Samuel Johnson (1709–1784)
“All men whilst they are awake are in one common world: but each of them, when he is asleep, is in a world of his own.”
—Plutarch (46–120)
“Tradition! We scarcely know the word anymore. We are afraid to be either proud of our ancestors or ashamed of them. We scorn nobility in name and in fact. We cling to a bourgeois mediocrity which would make it appear we are all Americans, made in the image and likeness of George Washington.”
—Dorothy Day (1897–1980)