|0.1.1||May 12, 2019|
|0.1.0||May 12, 2019|
#1344 in Data structures
Zip tree in Rust
This project implements Tarjan's zip tree, a treap-like data structure with different insertion and deletion algorithms. The node ranks are organized like that in skip-list. You can visit Tarjans's paper to learn more details.
The ZipTree API mimics standard library's BTreeMap interface. It provides insertion, deletion,
and iterator interface. Zip tree supports
clone() via O(n) deep copy.
The project is published with MIT license.
Tarjan's zip tree implementation in Rust.
Zip tree is a treap with different insertion and deletion algorithms. It organizes node ranks like skip list, but takes less space than skip list. Insertion and deletion are done by zip and unzip operations instead of a series of tree rotations. You can see Tarjans's paper for more details.