Back to the PSciCo homepage

Finger Treaps


Overview

An LRTreap is a functional (and therefore fully persistent) balanced tree data structure based on treaps that permits search for a key in O(log(min(d,n-d))) expected time where d is the number of keys in the LRTreap that are less than the target key. It also supports the split and join operations in O(log(min(n,m))) expected time.

Using the bounds above, it is possible to write a merge function which finds the union of the keys in two LRTreaps using O(k log((n+k)/k)) expected work. This function can be parallelized to perform in O(log(n)log(n)) time. Functions for intersect and difference are also provided.

Source code is available in sml or in java. There is also a somewhat faster java implementation in which the split and join methods are optimized to make only one pass through the data.

Source code for our partial implementation of Kaplan and Tarjan's functional finger search data structure based on 2-3 trees is here. The implementation is modified to support an operation that returns a key near the middle of the structure. Code for our union, intersect, and difference algorithms is provided also.

Note that our partial implementation of the 2-3 tree data structure is does not actually meet the time bound that a full implementation would achieve, though it does meet the comparison bound. The difference is that our structure does not combine contiguous yellow lists into one stack entry - see their paper for further details.

A paper describing this data structure is here.


Acknowledgements

The PSCICO project is supported by NSF under the title "????????????" as part of the Experimental Software Systems program within CISE. The grant number is ?????????.


Back to the PSciCo homepage.