\section{Discussion}
\label{sec:23trees}

We have already mentioned the data structure of Kaplan and Tarjan
\cite{Kaplan96} which allows splits and joins in worst-case
$O(\log(\min(a,b)))$ time.  We used treaps to implement a similar data
structure; for comparison, we will describe their structure here to
provide an indication of its complexity.

We start by defining a 6-list to be a list that can contain no more than 6
elements.  We can then recursively represent a sorted list $L$ as follows.
A list $L$ contains three pieces: a prefix, a suffix, and a sub-list.  The
prefix and suffix are 6-lists; the sub-list $c(L)$ is a list whose
elements are all either doubles or triples of elements from $L$.  If $L$
contains 6 or less elements then $c(L)$ is empty and all of the elements
are stored in the prefix and suffix. 

If we refer to the $i$-th level list with $c^i(L)$, then a list can be
represented as a stack $S(L)$ in which the $i$-th element of $S(L)$
contains pointers to the prefix and suffix of $c^i(L)$.

An element of $c^i(L)$ can be represented as a 2-3 tree of depth $i$.  For
ease of searching, the leftmost key of such a 2-3 tree is stored with the
tree itself.

A prefix or suffix is defined to be \emph{green} if it contains two to
four elements, \emph{yellow} if it contains one or five elements, and
\emph{red} if it contains zero or six elements.  The color of a list is
defined to be the ``worst'' of the colors of its prefix and suffix, where
red is defined to be ``worse'' than yellow, which is ``worse'' than green.

Kaplan and Tarjan maintain the following invariant over every list $L$:

``If $c^i(L)$ is a red list then $i > 0$ and there exists a green list
$c^j(L)$, $j < i$, such that any list $c^k(L)$, $j < k < l$, is yellow.''

In a functional setting, a list $L$ is not actually represented by $S(L)$
but by a different stack $S'(L)$ in which every maximal sequence of yellow
lists is replaced by a single element which contains a pointer to the
sequence.  The sequence is stored as a stack with the lowest-order list
on top.  This allows constant-time access to the topmost non-yellow list
in any stack. 

The structure described above permits implementations of {\sc split}\ and
{\sc join}\ which operate in $O(\log(\min(a,b)))$ time, where $a$ and $b$
are the sizes of the pieces involved.  With minor modifications we can
allow the structure to keep track of a key which is near the midpoint of
the list.  {\sc split}, {\sc join}, and {\sc getMidpoint}~are the only
operations that are required for our \cunion, {\sc intersect}, and {\sc
difference} algorithms, so we can use the structure described above as a
substitute for our treap data structures. 
