============= teardown_tree

API docs <https://docs.rs/teardown_tree/>_

|crates|_ |travis|_

.. |crates| image:: http://meritbadge.herokuapp.com/teardown_tree .. _crates: https://crates.io/crates/teardown_tree

.. |travis| image:: https://travis-ci.org/kirillkh/rs_teardown_tree.svg?branch=master .. _travis: https://travis-ci.org/kirillkh/rs_teardown_tree

A BST (binary search tree) written in Rust that supports efficient query and teardown scenarios, i.e. the typical usage pattern is to build a master copy of the tree, then

clone the master copy to a new tree
tear the tree down with a series of delete-range operations (and do something with the retrieved items), interspersed with range queries
rinse, repeat

Two variations are currently implemented: TeardownTree and IntervalTeardownTree (an |IntervalTree|_).

The tree does not use any kind of self-balancing and does not support insert operation.

.. |IntervalTree| replace:: augmented Interval Tree .. _IntervalTree: https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree

Details

The tree is implicit -- meaning that nodes do not store explicit pointers to their children. This is similar to how binary heaps work: all nodes in the tree reside in an array, the root always at index 0, and given a node with index i, its left/right children are found at indices 2*i+1 and 2*i+2. Thus no dynamic memory allocation or deallocation is done. This makes it possible to implement a fast clone operation: instead of traversing the tree, allocating and copying each node individually, we are able to allocate the whole array in a single call and efficiently copy the entire content.

As to delete-range operation, we use a custom algorithm running in O(k + log n) time, where k is the number of items deleted (and returned) and n is the initial size of the tree. Detailed description <delete_range.md>_.

An exhaustive automated test for delete-range has been written and is found in lib.rs. I have tested all trees up to the size n=10.

Usage

As a library

| And to your crate's root: | | extern crate teardown_tree;

To run the benchmarks

Install Rust and Cargo (any recent version will do, stable or nightly).
git clone https://github.com/kirillkh/rs_teardown_tree.git
cd rs_teardown_tree/benchmarks
cargo run --release

Benchmarks

.. image:: benchmarks/full_refill_teardown_1000.png :alt: TeardownTree vs other data structures: full refill/teardown cycle in bulks of 1000 :align: center

I have performed a set of benchmarks, comparing TeardownTree::delete_range() against

BTreeSet in Rust's standard library
|treap|_
|splay|_
TeardownTree::delete(), which deletes a single element

.. |treap| replace:: Treap .. _treap: https://github.com/kirillkh/treap-rs

.. |splay| replace:: SplayTree .. _splay: https://github.com/kirillkh/splay-rs

I made straightforward modifications to Treap and SplayTree in order to add support for delete_range, however BTreeSet lacks an equivalent operation (it has an O(log n) split, but not merge, see Rust #34666 <https://github.com/rust-lang/rust/issues/34666>_), therefore BTreeSet::remove() is used instead.

As the graph above shows, on my machine the whole clone/teardown sequence on a tree of 1,000,000 u64 items (we clone the tree, then delete 1000 items at a time until the tree is empty), is ~20 times faster with TeardownTree::delete_range() than with BTreeSet::remove(). It also uses 45% less memory.

|Benchmarks|_