# 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:

```rust
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.