Cartesian tree: Difference between revisions

Revision as of 23:09, 10 August 2023

Revision as of 23:18, 10 August 2023

Line 7:

==Definition==

Cartesian trees are defined using [[binary tree]]s, which are a form of [[rooted tree]]. These are mathematical structures rather than computer [[data structure]]s, although Cartesian trees have been used as part of the definition of certain data structures. A ''rooted tree'' consists of a collection of nodes, with bidirectional links connecting ''parent'' and ''child'' nodes, such that repeatedly following parent links, starting from any node, will always reach a unique ''root'' node. In a ''binary tree'', each node may have at most two children, designated as its left and right child. As well, each node may have some associated data (a number, in the case of a Cartesian tree). A Cartesian tree for a given sequence of distinct numbers may be defined from a [[recursion|recursivelyrecursive]] construction. ItsTo rootconstruct nodethe isCartesian associatedtree withfor a given sequence of distinct numbers, set its root to be the minimum number in the sequence.,<ref name=minmax>In some references, the ordering of the numbers is reversed, so the root node instead holds the maximum value.</ref> The left child ofand the roottree ishas the rootmax-heap nodeproperty ofrather a Cartesian tree constructed inthan the samemin-heap wayproperty.</ref> forand the[[recursion|recursively]] subsequenceconstruct ofits numbersleft toand theright leftsubtrees offrom the minimum,subsequences before itand inafter thethis sequencenumber, respectively. And the right child of the root is the root node ofAs a Cartesianbase treecase, constructedwhen in the same way for the subsequenceone of numbersthese to the right of the minimum, after it in the sequence. If the left or right subsequencesubsequences is empty, there is no left or right child, respectively.{{sfnp|Vuillemin|1980}}

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. Each node is associated with a single sequence value.

#A [[Tree_traversal#In-order,_LNR|symmetric (in-order) traversal]] of the tree results in the original sequence. That is, the left subtree consists of the values earlier than the root in the sequence order, while the right subtree consists of the values 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 may be determined for it by following a consistent tie-breaking rule before applying the above construction. For instance, the first of two equal elements may be treated as the smaller of the two.{{sfnp|Vuillemin|1980}}