History
Cartesian trees were introduced and named by Vuillemin (1980). The name is derived from the Cartesian coordinate system for the plane: 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. Gabow, Bentley & Tarjan (1984) and subsequent authors followed the definition here in which a Cartesian tree is defined from a sequence; this change generalizes the geometric setting of Vuillemin to allow sequences other than the sorted order of x-coordinates, and allows the Cartesian tree to be applied to non-geometric problems as well.
Read more about this topic: Cartesian Tree
Famous quotes containing the word history:
“The history of all hitherto existing society is the history of class struggles.”
—Karl Marx (1818–1883)
“In every election in American history both parties have their clichés. The party that has the clichés that ring true wins.”
—Newt Gingrich (b. 1943)