On random cartesian trees

Cartesian trees are binary search trees in which the nodes exhibit the heap property according to a second (priority) key. If the search key and the priority key are independent, and the trees is built based on n independent copies, Cartesian trees basically behave like ordinary random binary search trees. In this article, we analyze the expected behavior when the keys are dependent: in most cases, the expected search, insertion, and deletion times are Φ(√n). We indicate how these results can be used in the analysis of divide-and-conguer algorithms for maximal vectors and convex hulls. Finally, we look at distributions for which the expected time per operation grows like n^a for a ?1/2, 1]. © 1994 John Wiley & Sons, Inc.