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:
“Everyone who enjoys supposes that the tree was concerned with the fruit, but it was really concerned with the seed.In this lies the difference between all those who create and those who enjoy.”
—Friedrich Nietzsche (18441900)