Building Cartesian trees from free trees with k leaves

One can build a Cartesian tree from an n-element sequence in O(n) time, and from an n-node free tree in O(nlogn) time (with a matching worst-case lower bound in the comparison model of computation). We connect these results together by describing a Cartesian tree construction algorithm based on a “b...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2013-05, Vol.113 (9), p.345-349
Main Authors: Dean, Brian C., Mohan, Raghuveer
Format: Article
Language:English
Subjects:
Adaptive algorithms
Algorithms
Cartesian
Cartesian tree
Comparative analysis
Computer science
Construction
Data processing
Data structures
Leaves
Lower bounds
Matching
Mathematical models
Range queries
Studies
Trees
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:One can build a Cartesian tree from an n-element sequence in O(n) time, and from an n-node free tree in O(nlogn) time (with a matching worst-case lower bound in the comparison model of computation). We connect these results together by describing a Cartesian tree construction algorithm based on a “bitonicity transform” running in O(nlogk) time on a free tree with k leaves, noting that a path is the special case of a tree with just 2 leaves. We also provide a matching worst-case lower bound in the comparison model. •We propose faster algorithms for building Cartesian trees from free trees.•We derive matching lower bounds for our algorithms.•Our results highlight interesting structural properties of Cartesian trees.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2013.02.014