C++ Implementation of Zip Trees

Description

C++ implementation of balanced binary search trees called Zip Trees. The data structure was described in the following paper

@inproceedings{TarjanLT19,
  author    = {Robert E. Tarjan and Caleb C. Levy and Stephen
               Timmel},
  title     = {Zip Trees},
  booktitle = {16th International Symposium on Algorithms and Data
               Structures (WADS 2019)},
  pages     = {566--577},
  year      = {2019},
  doi       = {10.1007/978-3-030-24766-9_41},
}

The latest version of this code is available from https://github.com/dominikkempa/zip-tree

Compilation and usage

The package contains the implementation and the correctness tests of two variants of Zip Trees: one with, and one without the parent pointer. Additionally, the version with the parent pointer is benchmarked against Red-Black trees from the STL library. Instructions on how to compile and run the code for each of the version of the tree are found in the README files in the specific directories in the src/ folder.

Terms of use

This code is released under the MIT/X11 license. See the file LICENCE for more details. If you use this code, please include the link to the repository with the latest version of this code.

Implemented by

Dominik Kempa