bittree

这是一个Rust库，用于在称为位树的特殊数据结构中实现O(1)基于等价的查找功能。然而，尽管这个查找速度很快，但它具有慢速的常数因子O(1)索引和编辑。因此，这种位树数据结构应仅用于很少更改且更常搜索的数据集。它的另一个缺点是内存使用量高，因此其实际用途并不像人们想象的那么有用。

它是如何工作的？

为了实现快速的搜索速度，位树通过创建一个“位路径”来添加每个值。这个位路径包含值的所有位，并沿着它检查值是否存在于位树中。在注册的位路径底部，可以选择一个表示在创建位路径的键上存在的值的值。位路径通过位树中的add函数为输入键注册，并且可以通过remove函数删除。示例

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);
}

这个的实际应用场景有哪些？

在examples目录中有使用案例的示例。

是什么让你想到这个的？

当我试图弄清楚一种O(1)拼接和范围删除的数据格式，同时仍然保持O(1)索引（这本身会导致O(n)排序）时，我最终走上了一条完全无关的想法的道路。