  We define simple variants of zip trees, called zip-zip trees, which provide
several advantages over zip trees, including overcoming a bias that favors
smaller keys over larger ones. We analyze zip-zip trees theoretically and
empirically, showing, e.g., that the expected depth of a node in an $n$-node
zip-zip tree is at most $1.3863\log n-1+o(1)$, which matches the expected depth
of treaps and binary search trees built by uniformly random insertions. Unlike
these other data structures, however, zip-zip trees achieve their bounds using
only $O(\log\log n)$ bits of metadata per node, w.h.p., as compared to the
$\Theta(\log n)$ bits per node required by treaps. In fact, we even describe a
``just-in-time'' zip-zip tree variant, which needs just an expected $O(1)$
number of bits of metadata per node. Moreover, we can define zip-zip trees to
be strongly history independent, whereas treaps are generally only weakly
history independent. We also introduce \emph{biased zip-zip trees}, which have
an explicit bias based on key weights, so the expected depth of a key, $k$,
with weight, $w_k$, is $O(\log (W/w_k))$, where $W$ is the weight of all keys
in the weighted zip-zip tree. Finally, we show that one can easily make zip-zip
trees partially persistent with only $O(n)$ space overhead w.h.p.
