An experimental inquiry into zip trees, the randomized binary tree data structure recently proposed by Tarjan et al. We compare the empirical performance of zip trees along a number of axes with a variety of classic data structures, including
- Treaps
- Skip lists, a randomized linked-list-based structure.
- Splay trees, a self-adjusting data structure that is conjectured to be a competitively optimal BST.
See Project report