Btreeset

- 1 min

在rust里面, std::collections::BTreeSet 是什么数据结构

在Rust中,std::collections::BTreeSet 是一个基于B树实现的有序集合数据结构。它具有以下特点:

  1. 有序性:元素在集合中按照自然顺序(或者自定义的比较器)保持有序。

  2. 唯一性:集合中的每个元素都是唯一的,不允许重复。

  3. 基于B树:内部使用B树(平衡树)实现,保证了操作的高效性。

  4. 动态大小:可以动态增长或缩小。

  5. 主要操作的时间复杂度:
    • 插入(insert):O(log n)
    • 删除(remove):O(log n)
    • 查找(contains):O(log n)
  6. 内存效率:相比于哈希集合(HashSet),BTreeSet通常更节省内存,但在某些操作上可能稍慢。

  7. 范围操作:支持高效的范围查询和迭代。

  8. 有序迭代:可以按顺序迭代元素。

BTreeSet 适用于需要保持元素有序且需要频繁执行范围操作的场景。如果你不需要有序性,而更关注插入和查找的平均性能,可能会选择 HashSet

B树插入过程

  1. 从根节点开始,向下遍历树以找到新键应该插入的叶子节点。

  2. 如果叶子节点未满,直接将新键插入到适当的位置。

  3. 如果叶子节点已满: a. 将新键临时插入到节点中。 b. 将节点分裂为两个节点,选择中间的键上移。 c. 如果父节点有空间,将中间键插入父节点。 d. 如果父节点也满了,继续向上分裂过程,直到找到未满的节点或创建新的根节点。

  4. 如果分裂一直进行到根节点,创建新的根节点,树的高度增加1。