Skip to main content
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr11536
Full metadata record
DC FieldValueLanguage
dc.contributor.authorTarjan, Robert E-
dc.contributor.authorLevy, Caleb C-
dc.contributor.authorTimmel, Stephen-
dc.date.accessioned2021-10-08T19:47:38Z-
dc.date.available2021-10-08T19:47:38Z-
dc.date.issued2019en_US
dc.identifier.citationTarjan, Robert E., Caleb C. Levy, and Stephen Timmel. "Zip Trees." In Workshop on Algorithms and Data Structures (2019): pp. 566-577. doi:10.1007/978-3-030-24766-9_41en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttps://arxiv.org/pdf/1806.06726.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr11536-
dc.description.abstractWe 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 𝑂(loglog𝑛) bits (with high probability) to represent the largest rank in an n-node binary search tree; previous data structures require 𝑂(log𝑛) 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].en_US
dc.format.extent566 - 577en_US
dc.language.isoen_USen_US
dc.relation.ispartofWorkshop on Algorithms and Data Structuresen_US
dc.rightsAuthor's manuscripten_US
dc.titleZip Treesen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-030-24766-9_41-
dc.identifier.eissn1611-3349-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
ZipTrees.pdf451.03 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.