Cartesian tree: Difference between revisions

Revision as of 22:18, 13 August 2023

Revision as of 22:26, 13 August 2023

Line 21:

An alternative linear-time construction algorithm is based on the [[all nearest smaller values]] problem. In the input sequence, define the ''left neighbor'' of a value <math>a</math> to be the value that occurs prior to <math>a</math>, is smaller than <math>a</math>, and is closer in position to <math>a</math> than any other smaller value. The ''right neighbor'' is defined symmetrically. The sequence of left neighbors can be found by an algorithm that maintains a [[stack (data structure)|stack]] containing a subsequence of the input. For each new sequence value <math>a</math>, the stack is popped until it is empty or its top element is smaller than <math>a</math>, and then <math>a</math> is pushed onto the stack. The left neighbor of <math>a</math> is the top element at the time <math>a</math> is pushed. The right neighbors can be found by applying the same stack algorithm to the reverse of the sequence. The parent of <math>a</math> in the Cartesian tree is either the left neighbor of <math>a</math> or the right neighbor of <math>a</math>, whichever exists and has a larger value. The left and right neighbors can also be constructed efficiently by [[parallel algorithm]]s, making this formulation useful in efficient parallel algorithms for Cartesian tree construction.<ref>{{harvtxt|Berkman|Schieber|Vishkin|1993}}.</ref>

Another linear-time algorithm for Cartesian tree construction is based on [[Divide-and-conquer algorithm|divide-and-conquer]]. The algorithm recursively constructs the tree on each half of the input, and then merges the two trees. byThe merger process involves takingonly the nodes on the left and right spine''spines'' of these trees: the left treespine andis the path obtained by following left spinechild ofedges from the root until reaching a node with no left child, and the right treespine (bothis ofdefined whichsymmetrically. areAs pathswith whoseany rootpath in a min-to-leafheap, orderboth spines sortshave their values in sorted order, from the smallest value at their root to their largest) andvalue performsat athe standardend [[Mergeof algorithm#Mergingthe path. To merge the two lists|mergingtrees, apply a [[merge algorithm]] operationto the right spine of the left tree and the left spine of the right tree, replacing these two paths in two trees by a single path that contains the same nodes. In the merged path, the successor in the sorted order of each node from the left tree is placed in its right child, and the successor of each node from the right tree is placed in its left child, the same position that was previously used for its successor in the spine. The left children of nodes from the left tree and right children of nodes from the right tree are leftremain unchanged. The algorithm is also parallelizable since on each level of recursion, each of the two sub-problems can be computed in parallel, and the merging operation can be [[Merge algorithm#Parallel merge|efficiently parallelized]] as well.{{sfnp|Shun|Blelloch|2014}}

It is possible to maintain the Cartesian tree of a dynamic input, subject to insertions of elements and [[lazy deletion]] of elements, in logarithmic [[amortized time]] per operation. Here, lazy deletion means that upa todeletion aoperation constantis fractionperformed ofby themarking elementsan element in the current tree mayas bebeing markeda asdeleted deletedelement, ratherbut thannot actually removedremoving it from the tree. When toothe largenumber of marked elements reaches a constant fraction of elementsthe aresize marked,of the whole tree, it is rebuilt, keeping only its unmarked elements.{{sfnp|Bialynicka-Birula|Grossi|2006}}

==Applications==