  We introduce the zip tree, a form of randomized binary search tree that
integrates previous ideas into one practical, performant, and
pleasant-to-implement package. A zip tree is a binary search tree in which each
node has a numeric rank and the tree is (max)-heap-ordered with respect to
ranks, with rank ties broken in favor of smaller keys. Zip trees are
essentially treaps (Seidel and Aragon 1996), except that ranks are drawn from a
geometric distribution instead of a uniform distribution, and we allow rank
ties. These changes enable us to use fewer random bits per node. We perform
insertions and deletions by unmerging and merging paths ("unzipping" and
"zipping") rather than by doing rotations, which avoids some pointer changes
and improves efficiency. The methods of zipping and unzipping take inspiration
from previous top-down approaches to insertion and deletion (Stephenson 1980;
Mart\'inez and Roura 1998; Sprugnoli 1980). From a theoretical standpoint, this
work provides two main results. First, zip trees require only $O(\log \log n)$
bits (with high probability) to represent the largest rank in an $n$-node
binary search tree; previous data structures require $O(\log n)$ bits for the
largest rank. Second, zip trees are naturally isomorphic to skip lists (Pugh
1990), and simplify the mapping of (Dean and Jones 2007) between skip lists and
binary search trees.
