Cartesian tree: Difference between revisions

Revision as of 22:16, 13 August 2023

Revision as of 22:17, 13 August 2023

Line 17:

==Efficient construction==

A Cartesian tree can be constructed in [[linear time]] from its input sequence.

One method is to simply process the sequence values in left-to-right order, maintaining the Cartesian tree of the nodes processed so far, in a structure that allows both upwards and downwards traversal of the tree. To process each new value <math>a</math>, start at the node representing the value prior to <math>a</math> in the sequence and follow the [[Path (graph theory)|path]] from this node to the root of the tree until finding a value <math>b</math> smaller than <math>a</math>. The node <math>a</math> becomes the right child of <math>b</math>, and the previous right child of <math>b</math> becomes the new left child of <math>a</math>. The total time for this procedure is linear, because the time spent searching for the parent <math>b</math> of each new node <math>a</math> can be [[Potential method|charged]] against the number of nodes that are removed from the rightmost path in the tree.{{sfnp|Gabow|Bentley|Tarjan|1984}}

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>