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:
“But when the bowels of the earth were sought,
And men her golden entrails did espy,
This mischief then into the world was brought,
This framed the mint which coined our misery.
...
And thus began th’exordium of our woes,
The fatal dumb-show of our misery;
Here sprang the tree on which our mischief grows,
The dreary subject of world’s tragedy.”
—Michael Drayton (1563–1631)