Cartesian Tree

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Introduced 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. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence.

Read more about Cartesian Tree:  Definition, Range Searching and Lowest Common Ancestors, Treaps, Efficient Construction, Application in Sorting, History

Famous quotes containing the word tree:

    It never had been inside the room,
    And only one of the two
    Was afraid in an oft-repeated dream
    Of what the tree might do.
    Robert Frost (1874–1963)