Cartesian tree: Difference between revisions

Revision as of 22:25, 16 August 2023

Revision as of 22:38, 16 August 2023

Line 16:

==History==

Cartesian trees were introduced and named by {{harvtxt|Vuillemin|1980}}, who used them as an example of the interaction between [[geometric combinatorics]] and the design and analysis of [[data structure]]s. In particular, Vuillemin used these structures to analyze the [[average-case complexity]] of concatenation and splitting operations on [[binary search tree]]s. The name is derived from the [[Cartesian coordinate]] system for the plane: in one 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 <math>x</math>-coordinates as its symmetric traversal order, and it has the heap property according to the <math>y</math>-coordinates of the points. {{harvtxt|Vuillemin|1980}} 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.{{sfnp|Vuillemin|1980}}

==Efficient construction==