Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
arxiv(2023)
摘要
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.3863log 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(loglog 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, 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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要