Skip to content
The methodOpen data
Back to the collection

Zip Trees

Robert E. Tarjan, Caleb C. Levy, Stephen Timmel

2018 · arXiv

Statistics & probabilityAlgorithms
Read the paper
HN score
1
Mentions
5
Readers
3
Months
5
What’s in a score?

From the abstract

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ínez 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

5 selected excerpts · 5 total mentions

Labo333
Neutral mention · rule
All of those operations are achievable when replacing sqrt with log by using Skip lists (https://en.wikipedia.org/wiki/Skip_list), and probably with Zip trees as well (https://arxiv.org/abs/1806.06726). That being said, the overload of a complex data structure might multiply the running time by a factor up to ~10 (mostly because of cache misses), so simpler structures will be more performant for short inputs. There is a more general pattern in most tree data structures where you can transform the log(n) recursive operations on the tree into sqrt(n) operations on a simpler structure with 2 levels. I happen to have described the solution to a problem where you must use a sqrt-decomposition datastructure to have updates in O(1) and queries in O(sqrt(n)) because O(log(n)) everywhere is not good enough as there are a lot of updates to do (https://tryalgo.org/en/2017/09/01/path-statistics/).
Original comment Show HN: Array with Constant Time Access and Fast Insertion and Deletion
anfelor
Neutral mention · rule
Another interesting data structure related to skiplists but not mentioned here are zip trees: https://arxiv.org/abs/1806.06726 The are a tree-based version of skiplists and thus more suited to functional programming / immutable datastructures.
Original comment What Cannot be Skipped About the Skiplist
anfelor
Neutral mention · rule
There is also a nice new datastructure called Zip Trees [1] which is isomorphic to skip lists in the sense that it performs exactly the same comparisons on insertion/deletion (but it can skip some redundant ones). I would expect zip trees to be faster than skip lists in practice. [1]: https://arxiv.org/abs/1806.06726
Original comment Let's Talk SkipList

Keep following the thread.

More in Statistics & probability

More from the same topics.