Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent

Ofek Gila, Michael T. Goodrich, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We define simple variants of zip trees, called zip-zip trees, 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-node zip-zip tree is at most 1.3863 log n- 1 + o(1 ), 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 O(log log n) bits of metadata per node, w.h.p., as compared to the Θ(log n) bits per node required by treaps. In fact, we even describe a “just-in-time” zip-zip tree variant, which needs just an expected O(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 biased zip-zip trees, which have an explicit bias based on key weights, so the expected depth of a key, k, with weight, wk, is O(log (W/ wk) ), where W 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 O(n) space overhead w.h.p.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings
EditorsPat Morin, Subhash Suri
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages19
ISBN (Print)9783031389054
StatePublished - 2023
Event18th International Symposium on Algorithms and Data Structures, WADS 2023 - Montreal, Canada
Duration: Jul 31 2023Aug 2 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14079 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Symposium on Algorithms and Data Structures, WADS 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent'. Together they form a unique fingerprint.

Cite this