Cartesian Tree Algorithm

introduce by Vuillemin (1980) in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely specify from the property that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Gabow, Bentley & Tarjan (1984) and subsequent writers followed the definition here in which a Cartesian tree is specify from a sequence; this change generalizes the geometric setting of Vuillemin to let sequences other than the sorted order of X-coordinates, and lets the Cartesian tree to be apply to non-geometric problems as well. The name is derived from the Cartesian coordinate system for the airplane: in Vuillemin's version of this structure, as in the two-dimensional range searching application discussed above, a Cartesian tree for a point set has the sorted order of the points by their X-coordinates as its symmetric traversal order, and it has the heap property according to the Y-coordinates of the points. Cartesian trees were introduced and named by Vuillemin (1980).

Cartesian Tree source code, pseudocode and analysis