# Index of /afs/cs/project/pscico/pscico/src/fingertrees

Tables
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.

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.