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:
“It’s nice to be a part of history but people should get it right. I may not be perfect, but I’m bloody close.”
—John Lydon (formerly Johnny Rotten)
“Revolutions are the periods of history when individuals count most.”
—Norman Mailer (b. 1923)
“The history of progress is written in the blood of men and women who have dared to espouse an unpopular cause, as, for instance, the black man’s right to his body, or woman’s right to her soul.”
—Emma Goldman (1869–1940)