Content deleted Content added
→Definition: ce per ga |
+wl |
||
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>
Line 38:
===As a binary search tree===
{{main article|Treap}}
Because a Cartesian tree is a binary tree, it is natural to use it as a [[binary search tree]] for an ordered sequence of values. However, defining a Cartesian tree based on the same values that form the search keys of a binary search tree does not work well: the Cartesian tree of a sorted sequence is just a [[path graph
This idea was applied by {{harvtxt|Seidel|Aragon|1996}}, who suggested the use of random numbers as priorities. The data structure resulting from this random choice is called a [[treap]], due to its combination of binary search tree and binary heap features. An insertion into a treap can be performed by inserting the new key as a leaf of an existing tree, choosing a priority for it, and then performing [[tree rotation]] operations along a path from the node to the root of the tree to repair any violations of the heap property caused by this insertion; a deletion can similarly be performed by a constant amount of change to the tree followed by a sequence of rotations along a single path in the tree.{{sfnp|Seidel|Aragon|1996}} A variation on this data structure called a zip tree uses the same idea of random priorities, but simplifies the random generation of the priorities, and performs insertions and deletions in a different way, by splitting the sequence and its associated Cartesian tree into two subsequences and two trees and then recombining them.{{sfnp|Tarjan|Levy|Timmel|2021}}
| |||