Brian C. Dean Associate Professor Division of Computer Science School of Computing, Clemson University Office: McAdams Hall, Room 205 Phone: 864-656-5866 Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974 Email: bcdean@cs.clemson.edu

Building Cartesian Trees from Free Trees

One can build a Cartesian tree from an n-element sequence in O(n) time, and from an n-node free tree in O(n log n) time (with a matching worst-case lower bound in the comparison model of computation). We connect these results together by describing an "adaptive" Cartesian tree construction algorithm running in O(n log k) time on a free tree with k leaves. We also provide a matching worst-case lower bound in the comparison model.

Available in pdf.