我需要实现一个 B+ 树。
我需要创建以下方法:
- 插入(x) - 0(log_t(x))。
- 搜索 - 成功搜索 - O(log_t(x))。搜索不成功 - O(1) {具有很高的可能性}
所以我开始实现 Insert(x) - 每次我有一个完整的叶子时,我都想把它分成两个分开的叶子。一个叶子的键等于或低于中值键,第二个叶子将包含值高于中值的键。
我怎样才能在不影响运行时间的情况下找到这个中位数?
我想过:
- 将每个内部节点和叶子表示为较小的 B+ 树,但只有当树完全平衡时,中值才是根(或根中的元素之一)。
- 将每个内部节点和叶子表示为双向链表。并在插入输入时尝试获取中间键,但是有输入无法使用。
- 表示为数组可能会给我中间,但是当我将其拆分时,我至少需要 O(n/2) 将键插入新数组。
我能做些什么?
关于搜索,Idea-wise:成功和不成功搜索之间的区别在于在叶子中搜索,但我仍然需要“运行”树的不同键以确定键是否在树中。那么它怎么可能是 O(1) 呢?