TY - JOUR
T1 - Zip Trees
AU - Tarjan, Robert E.
AU - Levy, Caleb
AU - Timmel, Stephen
N1 - Funding Information:
A preliminary version of this article was presented at the 2019 Algorithms and Data Structures Symposium (WADS) [12]. Research at Princeton University by the first two authors was partially supported by an innovation research grant from Princeton and a gift from Microsoft. Authors’ addresses: R. E. Tarjan, Department of Computer Science, Princeton University, 35 Olden Street, Princeton, New Jersey, United States and Intertrust Technologies, California, United States; email: ret@cs.princeton.edu; C. Levy, Sunshine, 165 University Avenue, Suite 5, Palo Alto, California, United States; email: caleb.levy@gmail.com; S. Timmel, Department of Mathematics, Virginia Tech, 225 Stanger Street, Blacksburg, Virginia, United States; email: stimmel@vt.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2021 Association for Computing Machinery. 1549-6325/2021/10-ART34 $15.00 https://doi.org/10.1145/3476830
Publisher Copyright:
© 2021 Association for Computing Machinery.
PY - 2021/10
Y1 - 2021/10
N2 - We introduce the zip tree,1 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 [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
AB - We introduce the zip tree,1 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 [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
KW - binary search tree
KW - randomized algorithm
KW - skip list
KW - treap
KW - Zip tree
UR - http://www.scopus.com/inward/record.url?scp=85117112427&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85117112427&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85117112427
SN - 1549-6325
VL - 17
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 4
M1 - 34
ER -