A fast algorithm for melding splay trees

Abstract

Splay trees have emerged as an efficient method for representing ordered sets of items, allowing fast implementation of the usual range of set operations, including insert, access, and delete. Here we consider the more dramatic set operation meld, which produces an ordered set that is the union of two input sets. Starting with a collection of n singleton sets, we show that any sequence of n - 1 meld operations can be carried out in O(n log n) time to produce a single ordered set of at most n items. The splay tree melding algorithm presented is optimal to within a constant factor, as production of the final tree is tantamount to sorting the original list of items.