{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:03:15Z","timestamp":1783576995005,"version":"3.55.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T00:00:00Z","timestamp":1633305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006734","name":"Princeton","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006734","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We introduce the\n            <jats:italic>zip tree<\/jats:italic>\n            ,\n            <jats:sup>1<\/jats:sup>\n            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.\n          <\/jats:p>\n          <jats:p>\n            We perform insertions and deletions by unmerging and merging paths (\n            <jats:italic>unzipping<\/jats:italic>\n            and\n            <jats:italic>zipping<\/jats:italic>\n            ) 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\u00ednez and Roura [5], and Sprugnoli [9].\n          <\/jats:p>\n          <jats:p>\n            From a\n            <jats:italic>theoretical<\/jats:italic>\n            standpoint, this work provides two main results. First, zip trees require only\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            ) bits (with high probability) to represent the largest rank in an\n            <jats:italic>n<\/jats:italic>\n            -node binary search tree; previous data structures require\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists [7], and simplify Dean and Jones\u2019 mapping between skip lists\n          <\/jats:p>","DOI":"10.1145\/3476830","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T01:10:42Z","timestamp":1633396242000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Zip Trees"],"prefix":"10.1145","volume":"17","author":[{"given":"Robert E.","family":"Tarjan","sequence":"first","affiliation":[{"name":"Princeton University, United States and Intertrust Technologies, California, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Caleb","family":"Levy","sequence":"additional","affiliation":[{"name":"Sunshine, Palo Alto, California, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Timmel","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, Virginia, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233341.1233413"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2689412"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321108"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274812"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00141-I"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02576649"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00995807"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","volume-title":"Data Structures and Network Algorithms","author":"Tarjan Robert","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24766-9_41"},{"key":"e_1_2_1_13_1","volume-title":"Zip Trees: A new approach to concurrent binary search trees.","author":"Timmel Stephen","year":"2017"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476830","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:20Z","timestamp":1750268960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476830"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,4]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3476830"],"URL":"https:\/\/doi.org\/10.1145\/3476830","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,4]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}