## Cartesian tree

You are not Member of this Project.

**Project Owner :**vani.R

**Created Date :**Thu, 15/03/2012 - 13:41

**Project Description :**

e the Cartesian tree arising from a sequence

A1 . . . An by placing its minimum element Ai at the root

1

; its left and right subtrees are

recursively deﬁned to be Cartesian trees of the subsequences A1 . . . Ai−1 and Ai+1 . . . An.

The Cartesian tree in this case is a heap-ordered binary tree whose in-order traversal yields

the original sequence A1 . . . An. We deﬁne the Cartesian tree of a free tree T similarly,

as shown in Figure 1(b). The root node of the Cartesian tree corresponds to the edge

e of minimum weight in T, and its two children are Cartesian trees of the subtrees into

which T splits upon removal of e. Internal nodes in the Cartesian tree correspond to edges

in T, while leaves in the Cartesian tree correspond to nodes in T. Cartesian trees have

a variety of algorithmic applications, mostly due to their use in relating range minimum

queries (RMQs) with lowest common ancestor (LCA) queries. In both a sequence and a

free tree, the answer to an RMQ along a subsequence or subpath corresponds to the answer

of an LCA query in the Cartesian tree, as indicated in Figure 1.

In this work, we address the problem of building a Cartesian tree. One can easily build

a Cartesian tree in O(n) time from an n-element sequence and in O(n log n) time from

an n-node tree. Moreover, there is a matching Ω(n log n) worst-case lower bound on the

worst-case construction time of a Cartesian tree from a free tree in the comparison model,

since the Cartesian tree of a star-shaped tree is a depth-n sorted path (see Figure 2(a)), so

the process of Cartesian tree construction can be used to sort. We connect the dots between

these two cases, giving an O(n log k) algorithm for Cartesian tree construction from an nnode free tree with k leaves (and we provide a matching lower bound in the comparison

model). Such an algorithm could be termed an “adaptive” algorithm with respect to k, in

the same manner as adaptive sorting algorithms (see, e.g., [5]) gracefully scale in running

time between O(n) and O(n log n) depending on some auxiliary parameter beyond just the

problem size n that characterizes the intrinsic hardness of an instance (e.g., number of

inversions).

A Pointer-Based Implementation:

All of the steps in our construction algorithm can run in the simplistic pointer machine

model except for the O(n) algorithm of Demaine et al. [4] that builds a Cartesian tree

from a free tree once its edges are sorted (this algorithm uses a decremental connectivity

structure that depends on features of the RAM model). However, we note that since our

ultimate target running time is only O(n log k), we can use a slightly weaker approach

for decremental connectivity to obtain a purely pointer-based solution for Cartesian tree

construction.

To describe our construction, let us ﬁrst review how to build a Cartesian tree from a free tree

T in O(n log n) time in a simple top-down manner. This is done by repeatedly removing

edges from T (in increasing order of weight), creating a forest F whose components are

repeatedly split apart until F has been decomposed into n isolated nodes. We store the

edge weights in F in a binary heap H, so locating the minimum edge at each step takes

O(log n) time. As we decompose F, we simultaneously build out a Cartesian tree whose

leaves correspond to components in F. Each time we split a component C in F on some

edge e, we expand the corresponding leaf in our Cartesian tree by replacing it with a node

corresponding to e having children corresponding to the two sub-components obtained by

splitting C on e. To implement this eﬃciently, we need to use a decremental connectivity

data structure that can quickly identify the component of F to which each newly-extracted

edge from H belongs. This is easy to do in O(log n) amortized time per split operation, by

the standard trick of relabeling the edges in the smaller component created by the split (we

can determine which is smaller by traversing both in parallel, stopping when one traversal

terminates).

In order to implement the approach above in only O(n log k) time, we work with a “compressed” forest having only O(k) nodes and edges, so every heap operation on H and every

split takes only O(log k) (amortized) time. The compressed forest is obtained by initially

applying the bitonic transformation described above, so each segment in our tree eﬀectively

consists of a bitonic sequence of edge weights. We then treat each bitonic segment as two

monotonic segments, and we represent each monotonic segment s as only a single edge in

our compressed forest, labeled with the minimum edge weight in s. Monotonicity is crucial, since each time we remove the minimum edge from H and perform a split, this does

not create any new edges in the compressed forest — it merely removes the endpoint edge

of some existing segment, resulting in a change in the label of the edge representing that

segment (and a corresponding O(log k) time update to that edge’s record in H). The total

running time for our pointer-based construction algorithm is therefore only O(n log k).

You are not authorized to access this content.

You are not authorized to access this content.

You are not authorized to access this content.

You are not authorized to access this content.

You are not authorized to access this content.