{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:47:00Z","timestamp":1782265620487,"version":"3.54.5"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T00:00:00Z","timestamp":1776297600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T00:00:00Z","timestamp":1776297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2212129"],"award-info":[{"award-number":["2212129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2212129"],"award-info":[{"award-number":["2212129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We define simple variants of zip trees, called\n                    <jats:italic>zip-zip trees<\/jats:italic>\n                    , which provide several advantages over zip trees, including overcoming a bias that favors smaller keys over larger ones. We analyze zip-zip trees theoretically and empirically, showing, e.g., that the expected depth of a node in an\n                    <jats:italic>n<\/jats:italic>\n                    -node zip-zip tree is at most\n                    <jats:inline-formula>\n                      <jats:tex-math>$$1.3863\\log n-1+o(1)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , which matches the expected depth of treaps and binary search trees built by uniformly random insertions. Unlike these other data structures, however, zip-zip trees achieve their bounds using only\n                    <jats:inline-formula>\n                      <jats:tex-math>$$O(\\log \\log n)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    bits of metadata per node, w.h.p., as compared to the\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\Theta (\\log n)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    bits per node required by treaps. In addition, we describe a \u201cjust-in-time\u201d zip-zip tree variant, which needs just an expected\n                    <jats:italic>O<\/jats:italic>\n                    (1) number of bits of metadata per node. Moreover, we can define zip-zip trees to be strongly history independent, whereas treaps are generally only weakly history independent. We also introduce\n                    <jats:italic>biased zip-zip trees<\/jats:italic>\n                    , which have an explicit bias based on key weights, so the expected depth of a key,\n                    <jats:italic>k<\/jats:italic>\n                    , with weight,\n                    <jats:inline-formula>\n                      <jats:tex-math>$$w_k$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , is\n                    <jats:inline-formula>\n                      <jats:tex-math>$$O(\\log (W\/w_k))$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:italic>W<\/jats:italic>\n                    is the weight of all keys in the weighted zip-zip tree. Finally, we show that one can easily make zip-zip trees partially persistent with only\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ) space overhead w.h.p.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01364-2","type":"journal-article","created":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:35:45Z","timestamp":1776317745000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5931-771X","authenticated-orcid":false,"given":"Ofek","family":"Gila","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7505-5768","authenticated-orcid":false,"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,16]]},"reference":[{"key":"1364_CR1","unstructured":"Acar, U.A.: Self-Adjusting Computation. Ph.D. thesis, Carnegie Mellon Univ. (2005)"},{"issue":"6","key":"1364_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s00446-014-0229-0","volume":"27","author":"Y Afek","year":"2014","unstructured":"Afek, Y., Kaplan, H., Korenfeld, B., Morrison, A., Tarjan, R.E.: The CB tree: a practical concurrent self-adjusting search tree. Distrib. Comput. 27(6), 393\u2013417 (2014). https:\/\/doi.org\/10.1007\/s00446-014-0229-0","journal-title":"Distrib. Comput."},{"key":"1364_CR3","volume-title":"The probabilistic method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The probabilistic method, 4th edn. John Wiley & Sons, Hoboken (2016)","edition":"4"},{"key":"1364_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00453-004-1138-6","volume":"42","author":"A Bagchi","year":"2005","unstructured":"Bagchi, A., Buchsbaum, A.L., Goodrich, M.T.: Biased skip lists. Algorithmica 42, 31\u201348 (2005)","journal-title":"Algorithmica"},{"key":"1364_CR5","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Conway, A., Farach-Colton, M., Kuszmaul, W., Tagliavini, G.: (2023) Tiny pointers. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 477\u2013508 . https:\/\/doi.org\/10.1137\/1.9781611977554.ch21","DOI":"10.1137\/1.9781611977554.ch21"},{"issue":"3","key":"1364_CR6","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"SW Bent","year":"1985","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased search trees. SIAM J. Comput. 14(3), 545\u2013568 (1985)","journal-title":"SIAM J. Comput."},{"key":"1364_CR7","doi-asserted-by":"crossref","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased 2-3 trees. In: 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pp. 248\u2013254. IEEE (1980)","DOI":"10.1109\/SFCS.1980.15"},{"key":"1364_CR8","doi-asserted-by":"publisher","unstructured":"Dean, B.C., Jones, Z.H.: Exploring the duality between skip lists and binary search trees. In: Proc. of the 45th Annual Southeast Regional Conference (ACM-SE). pp. 395\u2013399 (2007). https:\/\/doi.org\/10.1145\/1233341.1233413","DOI":"10.1145\/1233341.1233413"},{"issue":"3","key":"1364_CR9","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1145\/5925.5930","volume":"33","author":"L Devroye","year":"1986","unstructured":"Devroye, L.: A note on the height of binary search trees. J. ACM 33(3), 489\u2013498 (1986)","journal-title":"J. ACM"},{"issue":"3","key":"1364_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF00265991","volume":"24","author":"L Devroye","year":"1987","unstructured":"Devroye, L.: Branching processes in the analysis of the heights of trees. Acta Informatica 24(3), 277\u2013298 (1987)","journal-title":"Acta Informatica"},{"key":"1364_CR11","doi-asserted-by":"publisher","unstructured":"Dillencourt, M., Goodrich, M.T.: Simplified chernoff bounds with powersof-two probabilities. Inf. Process. Lett. 182, 106397 (2023). https:\/\/doi.org\/10.1016\/j.ipl.2023.106397","DOI":"10.1016\/j.ipl.2023.106397"},{"issue":"1","key":"1364_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38(1), 86\u2013124 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90034-2","journal-title":"J. Comput. Syst. Sci."},{"key":"1364_CR13","doi-asserted-by":"crossref","unstructured":"Eberl, M., Haslbeck, M.W., Nipkow, T.: Verified analysis of random binary tree structures. In: 9th Int. Conf. on Interactive Theorem Proving (ITP). pp. 196\u2013214. Springer (2018)","DOI":"10.1007\/978-3-319-94821-8_12"},{"key":"1364_CR14","unstructured":"Erickson, J.: Lecture notes on treaps. Online (2017), available: https:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/notes\/03-treaps.pdf"},{"issue":"2","key":"1364_CR15","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0022-0000(82)90004-6","volume":"25","author":"P Flajolet","year":"1982","unstructured":"Flajolet, P., Odlyzko, A.: The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25(2), 171\u2013213 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"1364_CR16","volume-title":"Algorithm design and applications","author":"MT Goodrich","year":"2015","unstructured":"Goodrich, M.T., Tamassia, R.: Algorithm design and applications. Wiley, Hoboken (2015)"},{"issue":"3","key":"1364_CR17","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1016\/j.amc.2011.01.089","volume":"218","author":"BN Guo","year":"2011","unstructured":"Guo, B.N., Qi, F.: Sharp bounds for harmonic numbers. Appl. Math. Comput. 218(3), 991\u2013995 (2011). https:\/\/doi.org\/10.1016\/j.amc.2011.01.089","journal-title":"Appl. Math. Comput."},{"issue":"6","key":"1364_CR18","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T Hagerup","year":"1990","unstructured":"Hagerup, T., R\u00fcb, C.: A guided tour of Chernoff bounds. Inf. Process. Lett. 33(6), 305\u2013308 (1990)","journal-title":"Inf. Process. Lett."},{"key":"1364_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s00453-004-1140-z","volume":"42","author":"JD Hartline","year":"2005","unstructured":"Hartline, J.D., Hong, E.S., Mohr, A.E., Pentney, W.R., Rocke, E.C.: Characterizing history independent data structures. Algorithmica 42, 57\u201374 (2005)","journal-title":"Algorithmica"},{"issue":"2","key":"1364_CR20","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/274787.274812","volume":"45","author":"C Mart\u00ednez","year":"1998","unstructured":"Mart\u00ednez, C., Roura, S.: Randomized binary search trees. J. ACM 45(2), 288\u2013323 (1998). https:\/\/doi.org\/10.1145\/274787.274812","journal-title":"J. ACM"},{"key":"1364_CR21","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Dynamic binary search. In: Salomaa, A., Steinby, M. (eds.) Automata, Languages and Programming, Fourth Colloquium, University of Turku, Finland, July 18\u201322, 1977, Proceedings. Lecture Notes in Computer Science, vol. 52, pp. 323\u2013336. Springer (1977)","DOI":"10.1007\/3-540-08342-1_25"},{"key":"1364_CR22","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Dynamic binary search. SIAM J. Comput. 8(2), 175\u2013198 (1979)","DOI":"10.1137\/0208014"},{"key":"1364_CR23","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Arbitrary weight changes in dynamic trees. RAIRO Theor. Informatics Appl. 15(3), 183\u2013211 (1981)","DOI":"10.1051\/ita\/1981150301831"},{"key":"1364_CR24","doi-asserted-by":"publisher","unstructured":"Merkle, R.C.: Protocols for public key cryptosystems. In: 1980 IEEE Symposium on Security and Privacy. pp. 122\u2013122 (1980). https:\/\/doi.org\/10.1109\/SP.1980.10006","DOI":"10.1109\/SP.1980.10006"},{"key":"1364_CR25","volume-title":"Probability and computing: randomization and probabilistic techniques in algorithms and data analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and computing: randomization and probabilistic techniques in algorithms and data analysis, 2nd edn. Cambridge University Press, Cambridge (2017)","edition":"2"},{"key":"1364_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"1364_CR27","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/BF01994884","volume":"32","author":"T Papadakis","year":"1992","unstructured":"Papadakis, T., Ian Munro, J., Poblete, P.V.: Average search and update costs in skip lists. BIT Numer. Math. 32(2), 316\u2013332 (1992)","journal-title":"BIT Numer. Math."},{"issue":"6","key":"1364_CR28","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33(6), 668\u2013676 (1990). https:\/\/doi.org\/10.1145\/78973.78977","journal-title":"Commun. ACM"},{"issue":"3","key":"1364_CR29","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1145\/765568.765571","volume":"50","author":"B Reed","year":"2003","unstructured":"Reed, B.: The height of a random binary search tree. J. ACM 50(3), 306\u2013332 (2003)","journal-title":"J. ACM"},{"issue":"7","key":"1364_CR30","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29(7), 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"issue":"4\u20135","key":"1364_CR31","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R Seidel","year":"1996","unstructured":"Seidel, R., Aragon, C.R.: Randomized search trees. Algorithmica 16(4\u20135), 464\u2013497 (1996)","journal-title":"Algorithmica"},{"key":"1364_CR32","doi-asserted-by":"crossref","unstructured":"Shiu, D.: Efficient computation of tight approximations to Chernoff bounds. Computational Statistics pp. 1\u201315 (2022)","DOI":"10.1007\/s00180-022-01219-2"},{"key":"1364_CR33","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. In: 13th ACM Symposium on Theory of Computing (STOC). pp. 114\u2013122 (1981)","DOI":"10.1145\/800076.802464"},{"issue":"4","key":"1364_CR34","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/3476830","volume":"17","author":"RE Tarjan","year":"2021","unstructured":"Tarjan, R.E., Levy, C., Timmel, S.: Zip trees. ACM Trans. Algorithms 17(4), 34:1-34:12 (2021). https:\/\/doi.org\/10.1145\/3476830","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01364-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01364-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01364-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:11:08Z","timestamp":1782263468000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01364-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,16]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1364"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01364-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,16]]},"assertion":[{"value":"23 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declares that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"40"}}