2018/06/18 by Robert E. Tarjan, Caleb C. Levy, Caleb Levy +1 · 2 voices · 7 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Arithmetic #Artificial intelligence #Binary logarithm #Binary number #Binary search tree #Binary tree #Combinatorics #Computer science #Discrete mathematics #Genomics and Phylogenetic Studies #Heap (data structure) #Interval tree #K-ary tree #Machine Learning and Algorithms #Mathematics #Node (physics) #Optimal binary search tree #Pointer (user interface) #Random binary tree #Range tree #Rank (graph theory) #Search algorithm #Search tree #Self-balancing binary search tree #Ternary search tree #Tree (set theory) #Tree structure #Weight-balanced tree #cs.DS
paper · pdf · doi:10.1145/3476830
published in ACM Transactions on Algorithms 17(4), 1-12 (Association for Computing Machinery) · V5 is the final published version. V4 appeared in the Workshop on Algorithms and Data Structures in 2019. V1 was presented at Highlights of Algorithms in 2018. 14 pages, 3 figures
openalex publication_date 2021/10/04 · openalex created_date 2021/10/11 · arxiv created 2022/02/22 · arxiv updated 2022/02/23 · openalex updated_date 2026/08/05
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.