Content deleted Content added
→As a binary search tree: might as well use same log twice |
move section |
||
Line 14:
#The tree has the [[Binary heap|min-heap property]]: the parent of any non-root node has a smaller value than the node itself.<ref name=minmax/>
These two definitions are equivalent: the tree defined recursively as described above is the unique tree that has the properties listed above. If a sequence of numbers contains repetitions, a Cartesian tree can be determined for it by following a consistent tie-breaking rule before applying the above construction. For instance, the first of two equal elements can be treated as the smaller of the two.{{sfnp|Vuillemin|1980}}
==History==▼
Cartesian trees were introduced and named by {{harvtxt|Vuillemin|1980}}. The name is derived from the [[Cartesian coordinate]] system for the plane: in one 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 <math>x</math>-coordinates as its symmetric traversal order, and it has the heap property according to the <math>y</math>-coordinates of the points. {{harvtxt|Vuillemin|1980}} described both this geometric version of the structure, and the definition here in which a Cartesian tree is defined from a sequence. Using sequences instead of point coordinates provides a more general setting that allows the Cartesian tree to be applied to non-geometric problems as well.{{sfnp|Vuillemin|1980}}▼
==Efficient construction==
Line 60 ⟶ 63:
===In pattern matching===
The problem of ''Cartesian tree matching'' has been defined as a generalized form of [[string matching]] in which one seeks a [[substring]] (or in some cases, a [[subsequence]]) of a given string that has a Cartesian tree of the same form as a given pattern. Fast algorithms for variations of the problem with a single pattern or multiple patterns have been developed, as well as data structures analogous to the [[suffix tree]] and other text indexing structures.<ref>{{harvtxt|Park|Amir|Landau|Park|2019}}; {{harvtxt|Park|Bataa|Amir|Landau|2020}}; {{harvtxt|Song|Gu|Ryu|Faro|2021}}; {{harvtxt|Kim|Cho|2021}}; {{harvtxt|Nishimoto|Fujisato|Nakashima|Inenaga|2021}}; {{harvtxt|Oizumi|Kai|Mieno|Inenaga|2022}}</ref>
▲==History==
▲Cartesian trees were introduced and named by {{harvtxt|Vuillemin|1980}}. The name is derived from the [[Cartesian coordinate]] system for the plane: in one 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 <math>x</math>-coordinates as its symmetric traversal order, and it has the heap property according to the <math>y</math>-coordinates of the points. {{harvtxt|Vuillemin|1980}} described both this geometric version of the structure, and the definition here in which a Cartesian tree is defined from a sequence. Using sequences instead of point coordinates provides a more general setting that allows the Cartesian tree to be applied to non-geometric problems as well.{{sfnp|Vuillemin|1980}}
==Notes==
| |||