Cartesian Tree - History

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:

    “To history therefore I must refer for answer, in which it would be an unhappy passage indeed, which should shew by what fatal indulgence of subordinate views and passions, a contest for an atom had defeated well founded prospects of giving liberty to half the globe.”
    —Thomas Jefferson (1743–1826)

    “The history of all hitherto existing society is the history of class struggles.”
    —Karl Marx (1818–1883)

    “As History stands, it is a sort of Chinese Play, without end and without lesson.”
    —Henry Brooks Adams (1838–1918)