R. Tarjan, C. Levy, and S. Timmel. (2018)cite arxiv:1806.06726Comment: 16 pages, 1 figure, 5 algorithms.
Abstract
We introduce the zip tree, a form of randomized binary search tree. One can
view a zip tree as a treap (Seidel and Aragon 1996) in which priority ties are
allowed and in which insertions and deletions are done by unmerging and merging
paths (ünzipping" and "zipping") rather than by doing rotations.
Alternatively, one can view a zip tree as a binary-tree representation of a
skip list (Pugh 1990). Doing insertions and deletions by unzipping and zipping
instead of by doing rotations avoids some pointer changes and can thereby
improve efficiency. Representing a skip list as a binary tree avoids the need
for nodes of different sizes and can speed up searches and updates. Zip trees
are at least as simple as treaps and skip lists but offer improved efficiency.
Their simplicity makes them especially amenable to concurrent operations.
%0 Generic
%1 tarjan2018trees
%A Tarjan, Robert E.
%A Levy, Caleb C.
%A Timmel, Stephen
%D 2018
%K 2018 arxiv datastructure paper
%T Zip Trees
%U http://arxiv.org/abs/1806.06726
%X We introduce the zip tree, a form of randomized binary search tree. One can
view a zip tree as a treap (Seidel and Aragon 1996) in which priority ties are
allowed and in which insertions and deletions are done by unmerging and merging
paths (ünzipping" and "zipping") rather than by doing rotations.
Alternatively, one can view a zip tree as a binary-tree representation of a
skip list (Pugh 1990). Doing insertions and deletions by unzipping and zipping
instead of by doing rotations avoids some pointer changes and can thereby
improve efficiency. Representing a skip list as a binary tree avoids the need
for nodes of different sizes and can speed up searches and updates. Zip trees
are at least as simple as treaps and skip lists but offer improved efficiency.
Their simplicity makes them especially amenable to concurrent operations.
@misc{tarjan2018trees,
abstract = {We introduce the zip tree, a form of randomized binary search tree. One can
view a zip tree as a treap (Seidel and Aragon 1996) in which priority ties are
allowed and in which insertions and deletions are done by unmerging and merging
paths ("unzipping" and "zipping") rather than by doing rotations.
Alternatively, one can view a zip tree as a binary-tree representation of a
skip list (Pugh 1990). Doing insertions and deletions by unzipping and zipping
instead of by doing rotations avoids some pointer changes and can thereby
improve efficiency. Representing a skip list as a binary tree avoids the need
for nodes of different sizes and can speed up searches and updates. Zip trees
are at least as simple as treaps and skip lists but offer improved efficiency.
Their simplicity makes them especially amenable to concurrent operations.},
added-at = {2018-11-14T19:51:40.000+0100},
author = {Tarjan, Robert E. and Levy, Caleb C. and Timmel, Stephen},
biburl = {https://www.bibsonomy.org/bibtex/2259d84fd8f41398e82116475b1f90a24/analyst},
description = {[1806.06726] Zip Trees},
interhash = {147beb1c5d479efcc961ed9b268b1759},
intrahash = {259d84fd8f41398e82116475b1f90a24},
keywords = {2018 arxiv datastructure paper},
note = {cite arxiv:1806.06726Comment: 16 pages, 1 figure, 5 algorithms},
timestamp = {2018-11-14T19:51:40.000+0100},
title = {Zip Trees},
url = {http://arxiv.org/abs/1806.06726},
year = 2018
}