Zip Tree

Jun 18, 2018

A probabilistic binary search tree that is similar to skip lists and treaps. One can think of zip trees as treaps with different ranking, insertion, and deletion implementations.

The tree is in max-heap order and the ranks are randomly chosen from a geometric distribution instead of an uniform one like in treaps. Insertion and deletion will use unzipping and zipping to reorder the nodes properly by relinking them.

Pros	Cons
More efficient than skip lists	Newest of the probabilistic binary search tree data structures
Updates faster than treaps' rotations	Greater depth than treaps
Less space used compared to treaps with the ranks/priorties