This is a visual guide to zip-trees, a probabilistic search tree data structure. See the original zip-tree paper for complexity analyses and the connection to skip lists, and the G-tree paper for a broader perspective that leads to a powerful generalisation.
The trees are defined inductively.
The empty tree is a a tree, and
a value with a left subtree and a right subtree is a tree.
Let U be a set of values with a total order ≤.
Let S be a finite subset of U.
Let r be a function from S to the natural numbers (including zero). We call r(s) the rank of s.
We say a value s outranks a value t if either the rank of s is strictly greater than that of t or their ranks are equal and s ≤ t.
The rank-maximal value in a set of value is the unique value in that set that outranks all other values in the set.
The zip-tree on the empty set is the empty tree .
The zip-tree on a nonempty set S is the tree whose root is the rank-maximal value in S, whose left subtree is the zip-tree on all values less than the root, and whose right subtree is the zip-tree on all values greater than the root.
Good to know: if you select ranks randomly from a geometric distribution with p = 0.5, the resulting zip-tree is of logarithmic height with high probability.
In plain English: for each value, flip a coin until it shows tails, and count how many times it showed heads first. Use that as the rank for the value. The resulting tree is very likely to be rather balanced.
You can also assign ranks uniformly at random from a larger set of numbers (using log(n) bits for n values). Then you call them treaps instead of zip-trees.
The split (or unzip) operation takes a zip-tree and a split value , and returns the zip-tree containing all values strictly less than and the zip-tree containing all values greater than or equal to .
Calling split on the empty tree with any split value yields two empty trees .
Now we describe how to split a nonempty zip-tree with root at position .
If ≥ , we say to the left subtree of , and to the right subtree of .
If < , we say to the left subtree of , and to the right subtree of .
Remove the edge from to .
Recursively split at , obtaining (closer to ) and (farther from ).
Add an edge from to . Done!
The insert operation takes a zip-tree and a value , and returns the zip-tree containing and all values in .
Calling insert on the empty tree with any value yields the zip-tree whose root is and whose subtrees are empty.
Calling insert with a value on any nonempty zip-tree whose root is leaves the tree unchanged.
Now we describe how to insert a value into a nonempty zip-tree whose root is outranked by .
Split the tree at .
Call the lesser resulting tree and the greater resulting tree .
Make the left subtree of and the right subtree of . Done!
Finally, we describe how to insert a value into a nonempty zip-tree whose root outranks .
If ≥ , we say to the left subtree of , and to the right subtree of .
If < , we say to the left subtree of , and to the right subtree of .
Remove the edge from to .
Recursively insert into .
Call the resulting tree .
Make the right subtree of . Done!
The join (or zip) operation takes a left zip-tree and a right zip-tree , with containing only values strictly less than those in . It returns the zip-tree on the union of the values of and .
Calling join on the empty tree and any tree yields .
Calling join on any tree and the empty tree yields .
Now we describe how to join two nonempty zip-trees.
We say to the tree whose root is outranked by the root of the other tree.
If > , we say to the left subtree of , and to the right subtree of .
If < , we say to the left subtree of , and to the right subtree of .
Remove the edge from to .
Recursively join and .
Call the resulting tree .
Add an edge from to . Done!
The remove operation takes a zip-tree and a value , and returns the zip-tree containing all values in except for .
Calling remove on the empty tree with any value yields the empty tree.
Calling remove with a value on any nonempty zip-tree whose root is outranked by leaves the tree unchanged.
Now we describe how to remove a value from a nonempty zip-tree with root , left subtree , and right subtree .
Compute the join of and . Done!
Finally, we describe how to remove a value from a nonempty zip-tree whose root outranks .
If ≥ , we say to the left subtree of , and to the right subtree of .
If < , we say to the left subtree of , and to the right subtree of .
Remove the edge from to .
Recursively remove from .
Call the resulting tree .
Make the right subtree of . Done!
If you are implementing zip-trees as a library, please consider implementing join-based set-set algorithms as well. You already have join and split anyway.
This page is an exploration and a proof of concept, in preparation for an explanation of two-dimensional zip-trees. The visual language could be improved quite a bit, but that wasn't my top priority.
All diagrams generated with rough.js. I wish it could rotate ellipses, otherwise it was quite pleasant to use.