Content deleted Content added
→Definition: tighter |
distinct in lead per GA1 |
||
Line 2:
[[File:Cartesian tree.svg|thumb|240px|A sequence of numbers and the Cartesian tree derived from them.]]
{{for|Descartes' metaphor of tree of knowledge|Tree of knowledge (philosophy)}}
In [[computer science]], a '''Cartesian tree''' is a [[binary tree]] derived from a sequence of distinct numbers. The smallest number in the sequence is at the root of the tree; its left and right subtrees are constructed recursively from the subsequences to the left and right of this number. When all numbers are distinct, the Cartesian tree is uniquely defined from the properties that it is [[Heap (data structure)|heap]]-ordered and that a [[Tree traversal|symmetric (in-order) traversal]] of the tree returns the original sequence.
Introduced by {{harvtxt|Vuillemin|1980}} in the context of geometric [[range searching]] [[data structure]]s, Cartesian trees have also been used in the definition of the [[treap]] and [[randomized binary search tree]] data structures for [[binary search]] problems, in [[comparison sort]] algorithms that perform efficiently on nearly-sorted inputs, and as the basis for [[pattern matching]] algorithms. A Cartesian tree for a sequence may be constructed in [[linear time]].
| |||