TY - GEN

T1 - Zip-Zip Trees

T2 - 18th International Symposium on Algorithms and Data Structures, WADS 2023

AU - Gila, Ofek

AU - Goodrich, Michael T.

AU - Tarjan, Robert E.

N1 - Funding Information:
Research at Princeton Univ. was partially supported by a gift from Microsoft. Research at Univ. of California, Irvine was supported by NSF Grant 2212129. c○ The Author(s), under exclusive license to Springer Nature Switzerland AG 2023
Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85172731126&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172731126&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38906-1_31

DO - 10.1007/978-3-031-38906-1_31

M3 - Conference contribution

AN - SCOPUS:85172731126

SN - 9783031389054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 474

EP - 492

BT - Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 31 July 2023 through 2 August 2023

ER -