Cartesian tree: Difference between revisions

Revision as of 03:13, 12 August 2023

Revision as of 03:15, 12 August 2023

Line 11:

It is also possible to characterize the Cartesian tree directly rather than recursively, using its ordering properties. In any tree, the ''subtree'' rooted at any node consists of all other nodes that can reach it by repeatedly following parent pointers. The Cartesian tree for a sequence of distinct numbers is defined by the following properties:

#The Cartesian tree for a sequence is a [[binary tree]] with one node for each number in the sequence.

#A [[Tree_traversal#In-order,_LNR|symmetric (in-order) traversal]] of the tree results in the original sequence. ThatEquivalently, isfor each node, the leftnumbers subtreein consistsits ofleft thesubtree valuesare earlier than the rootit in the sequence order, whileand the rightnumbers subtreein consiststhe ofright thesubtree valuesare later than the root, and a similar ordering constraint holds at each lower node of the tree.

#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}}