Zip trees

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We introduce the zip tree, (Zip: “To move very fast.”) 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 ties broken in favor of smaller keys. Zip trees are essentially treaps [8], 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 by Stephenson [10], Martínez and Roura [5], and Sprugnoli [9]. 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 [7], and simplify Dean and Jones’ mapping between skip lists and binary search trees [2].

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
PublisherSpringer Verlag
Pages566-577
Number of pages12
ISBN (Print)9783030247652
DOIs
StatePublished - Jan 1 2019
Event16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada
Duration: Aug 5 2019Aug 7 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11646 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Symposium on Algorithms and Data Structures, WADS 2019
CountryCanada
CityEdmonton
Period8/5/198/7/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Zip trees'. Together they form a unique fingerprint.

  • Cite this

    Tarjan, R. E., Levy, C. C., & Timmel, S. (2019). Zip trees. In Z. Friggstad, M. R. Salavatipour, & J-R. Sack (Eds.), Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings (pp. 566-577). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11646 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-24766-9_41