Btreeset
- 1 min在rust里面, std::collections::BTreeSet 是什么数据结构
在Rust中,std::collections::BTreeSet
是一个基于B树实现的有序集合数据结构。它具有以下特点:
-
有序性:元素在集合中按照自然顺序(或者自定义的比较器)保持有序。
-
唯一性:集合中的每个元素都是唯一的,不允许重复。
-
基于B树:内部使用B树(平衡树)实现,保证了操作的高效性。
-
动态大小:可以动态增长或缩小。
- 主要操作的时间复杂度:
- 插入(insert):O(log n)
- 删除(remove):O(log n)
- 查找(contains):O(log n)
-
内存效率:相比于哈希集合(HashSet),BTreeSet通常更节省内存,但在某些操作上可能稍慢。
-
范围操作:支持高效的范围查询和迭代。
- 有序迭代:可以按顺序迭代元素。
BTreeSet
适用于需要保持元素有序且需要频繁执行范围操作的场景。如果你不需要有序性,而更关注插入和查找的平均性能,可能会选择 HashSet
。
B树插入过程
-
从根节点开始,向下遍历树以找到新键应该插入的叶子节点。
-
如果叶子节点未满,直接将新键插入到适当的位置。
-
如果叶子节点已满: a. 将新键临时插入到节点中。 b. 将节点分裂为两个节点,选择中间的键上移。 c. 如果父节点有空间,将中间键插入父节点。 d. 如果父节点也满了,继续向上分裂过程,直到找到未满的节点或创建新的根节点。
-
如果分裂一直进行到根节点,创建新的根节点,树的高度增加1。