Projects

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 defined 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 define 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 first 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 efficiently, 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 effectively
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.