Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
Algorithmica · 2026-06 · 88 (3)
DOI: 10.1007/s00453-025-01364-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 16.04.2026. Verfasst von Ofek Gila und 2 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation, Microsoft.
Abstract (Originalsprache)
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 $$\Theta (\log n)$$ bits per node required by treaps. In addition, we 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, $$w_k$$ , is $$O(\log (W/w_k))$$ , 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.
Förderung
- National Science Foundation
- Microsoft
Zitieren
APA
Gila, O., Goodrich, M. T., & Tarjan, R. E. (2026). Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent. Algorithmica, 88(3). https://doi.org/10.1007/s00453-025-01364-2
Vancouver
Gila O, Goodrich MT, Tarjan RE. Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent. Algorithmica. 2026;88(3). doi:10.1007/s00453-025-01364-2
BibTeX
@article{Gila2026,
author = {Gila, Ofek and Goodrich, Michael T. and Tarjan, Robert E.},
title = {Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {3},
doi = {10.1007/s00453-025-01364-2}
}
EUVIMED