Cartesian tree

In

returns the original sequence.

Cartesian trees were introduced by

linear time

.

Definition

Cartesian trees are defined using

It is also possible to characterize the Cartesian tree directly rather than recursively, using its ordering properties. In any tree, the subtree rooted at any node consists of all other nodes that can reach it by repeatedly following parent pointers. The Cartesian tree for a sequence of distinct numbers is defined by the following properties:

1. The Cartesian tree for a sequence is a binary tree with one node for each number in the sequence.
2. A symmetric (in-order) traversal of the tree results in the original sequence. Equivalently, for each node, the numbers in its left subtree are earlier than it in the sequence, and the numbers in the right subtree are later.
3. The tree has the min-heap property: the parent of any non-root node has a smaller value than the node itself.^[1]

These two definitions are equivalent: the tree defined recursively as described above is the unique tree that has the properties listed above. If a sequence of numbers contains repetitions, a Cartesian tree can be determined for it by following a consistent tie-breaking rule before applying the above construction. For instance, the first of two equal elements can be treated as the smaller of the two.^[2]

Cartesian trees were introduced and named by

system for the plane: in one version of this structure, as in the two-dimensional range searching application discussed below, a Cartesian tree for a point set has the sorted order of the points by their ${\displaystyle x}$-coordinates as its symmetric traversal order, and it has the heap property according to the ${\displaystyle y}$-coordinates of the points. Vuillemin described both this geometric version of the structure, and the definition here in which a Cartesian tree is defined from a sequence. Using sequences instead of point coordinates provides a more general setting that allows the Cartesian tree to be applied to non-geometric problems as well.^[2]

A Cartesian tree can be constructed in

from its input sequence. One method is to process the sequence values in left-to-right order, maintaining the Cartesian tree of the nodes processed so far, in a structure that allows both upwards and downwards traversal of the tree. To process each new value ${\displaystyle a}$, start at the node representing the value prior to ${\displaystyle a}$ in the sequence and follow the path from this node to the root of the tree until finding a value ${\displaystyle b}$ smaller than ${\displaystyle a}$. The node ${\displaystyle a}$ becomes the right child of ${\displaystyle b}$, and the previous right child of ${\displaystyle b}$ becomes the new left child of ${\displaystyle a}$. The total time for this procedure is linear, because the time spent searching for the parent ${\displaystyle b}$ of each new node ${\displaystyle a}$ can be charged against the number of nodes that are removed from the rightmost path in the tree.^[3]

An alternative linear-time construction algorithm is based on the all nearest smaller values problem. In the input sequence, define the left neighbor of a value ${\displaystyle a}$ to be the value that occurs prior to ${\displaystyle a}$, is smaller than ${\displaystyle a}$, and is closer in position to ${\displaystyle a}$ than any other smaller value. The right neighbor is defined symmetrically. The sequence of left neighbors can be found by an algorithm that maintains a

containing a subsequence of the input. For each new sequence value ${\displaystyle a}$, the stack is popped until it is empty or its top element is smaller than ${\displaystyle a}$, and then ${\displaystyle a}$ is pushed onto the stack. The left neighbor of ${\displaystyle a}$ is the top element at the time ${\displaystyle a}$ is pushed. The right neighbors can be found by applying the same stack algorithm to the reverse of the sequence. The parent of ${\displaystyle a}$ in the Cartesian tree is either the left neighbor of ${\displaystyle a}$ or the right neighbor of ${\displaystyle a}$, whichever exists and has a larger value. The left and right neighbors can also be constructed efficiently by parallel algorithms, making this formulation useful in efficient parallel algorithms for Cartesian tree construction.^[4]

Another linear-time algorithm for Cartesian tree construction is based on divide-and-conquer. The algorithm recursively constructs the tree on each half of the input, and then merges the two trees. The merger process involves only the nodes on the left and right spines of these trees: the left spine is the path obtained by following left child edges from the root until reaching a node with no left child, and the right spine is defined symmetrically. As with any path in a min-heap, both spines have their values in sorted order, from the smallest value at their root to their largest value at the end of the path. To merge the two trees, apply a merge algorithm to the right spine of the left tree and the left spine of the right tree, replacing these two paths in two trees by a single path that contains the same nodes. In the merged path, the successor in the sorted order of each node from the left tree is placed in its right child, and the successor of each node from the right tree is placed in its left child, the same position that was previously used for its successor in the spine. The left children of nodes from the left tree and right children of nodes from the right tree remain unchanged. The algorithm is parallelizable since on each level of recursion, each of the two sub-problems can be computed in parallel, and the merging operation can be efficiently parallelized as well.^[5]

Yet another linear-time algorithm, using a linked list representation of the input sequence, is based on locally maximum linking: the algorithm repeatedly identifies a local maximum element, i.e., one that is larger than both its neighbors (or than its only neighbor, in case it is the first or last element in the list). This element is then removed from the list, and attached as the right child of its left neighbor, or the left child of its right neighbor, depending on which of the two neighbors has a larger value, breaking ties arbitrarily. This process can be implemented in a single left-to-right pass of the input, and it is easy to see that each element can gain at most one left-, and at most one right child, and that the resulting binary tree is a Cartesian tree of the input sequence. ^{[6] [7]}

It is possible to maintain the Cartesian tree of a dynamic input, subject to insertions of elements and

Applications

Range searching and lowest common ancestors

Cartesian trees form part of an efficient data structure for

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 ${\displaystyle x}$-coordinates and using the ${\displaystyle y}$-coordinates in this order as the sequence of values from which this tree is formed. If ${\displaystyle S}$ is the subset of the input points within some vertical slab defined by the inequalities ${\displaystyle L\leq x\leq R}$, ${\displaystyle p}$ is the leftmost point in ${\displaystyle S}$ (the one with minimum ${\displaystyle x}$-coordinate), and ${\displaystyle q}$ is the rightmost point in ${\displaystyle S}$ (the one with maximum ${\displaystyle x}$-coordinate) then the lowest common ancestor of ${\displaystyle p}$ and ${\displaystyle 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 ${\displaystyle L\leq x\leq R}$ and ${\displaystyle y\leq T}$, can be answered by finding this bottommost point ${\displaystyle b}$, comparing its ${\displaystyle y}$-coordinate to ${\displaystyle T}$, and (if the point lies within the three-sided region) continuing recursively in the two slabs bounded between ${\displaystyle p}$ and ${\displaystyle b}$ and between ${\displaystyle b}$ and ${\displaystyle q}$. 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.[3]

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.^[12] 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 can be constructed in linear time.^[13]

The Cartesian tree of a sorted sequence is just a

of logarithmic depth from sorted sequences of values. This can be done by generating priority numbers for each value, and using the sequence of priorities to generate a Cartesian tree. This construction may equivalently be viewed in the geometric framework described above, in which the ${\displaystyle x}$-coordinates of a set of points are the values in a sorted sequence and the ${\displaystyle y}$-coordinates are their priorities.[14]

This idea was applied by Seidel & Aragon (1996), who suggested the use of random numbers as priorities. The self-balancing binary search tree resulting from this random choice is called a treap, due to its combination of binary search tree and min-heap features. An insertion into a treap can be performed by inserting the new key as a leaf of an existing tree, choosing a priority for it, and then performing tree rotation operations along a path from the node to the root of the tree to repair any violations of the heap property caused by this insertion; a deletion can similarly be performed by a constant amount of change to the tree followed by a sequence of rotations along a single path in the tree.^[14] A variation on this data structure called a zip tree uses the same idea of random priorities, but simplifies the random generation of the priorities, and performs insertions and deletions in a different way, by splitting the sequence and its associated Cartesian tree into two subsequences and two trees and then recombining them.^[15]

If the priorities of each key are chosen randomly and independently once whenever the key is inserted into the tree, the resulting Cartesian tree will have the same properties as a

length of the search path to any given value is at most ${\displaystyle 2\ln n}$, and the whole tree has logarithmic depth (its maximum root-to-leaf distance) with high probability. More formally, there exists a constant ${\displaystyle C}$ such that the depth is ${\displaystyle \leq C\ln n}$ with probability tending to one as the number of nodes tends to infinity. The same good behavior carries over to treaps. It is also possible, as suggested by Aragon and Seidel, to reprioritize frequently-accessed nodes, causing them to move towards the root of the treap and speeding up future accesses for the same keys.^[14]

Levcopoulos & Petersson (1989) describe a sorting algorithm based on Cartesian trees. They describe the algorithm as based on a tree with the maximum at the root,^[16] but it can be modified straightforwardly to support a Cartesian tree with the convention that the minimum value is at the root. For consistency, it is this modified version of the algorithm that is described below.

The Levcopoulos–Petersson algorithm can be viewed as a version of

1. Construct a Cartesian tree for the input sequence
2. Initialize a priority queue, initially containing only the tree root
3. While the priority queue is non-empty:
   • Find and remove the minimum value in the priority queue
   • Add this value to the output sequence
   • Add the Cartesian tree children of the removed value to the priority queue

As Levcopoulos and Petersson show, for input sequences that are already nearly sorted, the size of the priority queue will remain small, allowing this method to take advantage of the nearly-sorted input and run more quickly. Specifically, the worst-case running time of this algorithm is ${\displaystyle O(n\log k)}$, where ${\displaystyle n}$ is the sequence length and ${\displaystyle k}$ is the average, over all values in the sequence, of the number of consecutive pairs of sequence values that bracket the given value (meaning that the given value is between the two sequence values). They also prove a lower bound stating that, for any ${\displaystyle n}$ and (non-constant) ${\displaystyle k}$, any comparison-based sorting algorithm must use ${\displaystyle \Omega (n\log k)}$ comparisons for some inputs.[16]

The problem of Cartesian tree matching has been defined as a generalized form of

Notes