A Space Efficient Variant of Path Copying for Partially Persistent Sorted Sets

摘要

A simple algorithm for solving a version of thepartially persistent sorted set problemis given. The algorithm requiresO(n) space andO(n log n) time to handlenoperations. Unlike Sarnak and Tarjan's algorithm, the new algorithm can make use of any of the existing balanced tree schemes that can be implemented with “path copying,” at the expense of not efficiently implementing some operations on partially persistent search trees.