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。