Name Last modified Size Description
Parent Directory - 23tree-java.tar.gz 23-Jul-2001 00:49 7.6K java/ 30-Jul-2001 12:29 - lrtreap-javafast.tar.gz 23-Jul-2001 00:49 6.5K lrtreap-javasimple.t..> 23-Jul-2001 00:49 5.8K lrtreap-paper.ps 23-Jul-2001 00:49 286K lrtreap-sml.tar.gz 23-Jul-2001 00:49 3.3K sml/ 30-Jul-2001 12:29 - tex/ 30-Jul-2001 12:29 -
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.