bittree

This is a rust library for O(1) equality-based find functions in a special data structure called a bit tree. However, despite this fast find speed, it has slow high constant factor O(1) indexing and editing. Because of this, this bit tree data structure should only be used for seldom changed and more often searched datasets. Another disadvantage of this is high memory usage, and so it isn't really as useful as one might think.

How does this work?

To achieve the fast search speed, bit trees add each value by creating a "bitpath". This bitpath contains all of the bits of the value and is followed to see if a value exists in the bit tree. At the bottom of a registered bitpath there is optionally a value representing the value that exists at the key that created the bitpath. Bitpaths are registered for an input key in a bit tree with the add function and can be removed with the remove function. Example:

fn main() {
    let mut btree = bittree::BitTree::new();
    btree.add(&1usize, Some(0usize));
    assert_eq!(btree.find(&0usize), Some(1usize));
    
    btree.remove(&1usize);
    assert_eq!(btree.find(&0usize), None);
}

What are actual practical use cases of this?

There are examples of use cases in the examples directory.

What made you come up with this?

When I was trying to figure out a format of data for O(1) splicing and range removal while still maintaining O(1) indexing (which itself would lead to O(n) sorting), I ended up going down a path leading me to this from a totally unrelated idea.