EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

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

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →