java – 在B树中查找中值

发布时间：2020-12-15 04:10:09 所属栏目：Java 来源：网络整理

导读：我需要实现一个B树. 我需要创建以下方法：插入(x) – 0(log_t(x)). 搜索 – 成功搜索 – O(log_t(x)).不成功的搜索 – O(1){有很高的可能性} 所以我开始实现Insert(x) – 每次我有一个完整的叶子,我想把它分成两个分开的叶子. 一个键的键等于或低于中值键,

我需要实现一个B树.

我需要创建以下方法：

>插入(x) – 0(log_t(x)).
>搜索 – 成功搜索 – O(log_t(x)).不成功的搜索 – O(1){有很高的可能性}

所以我开始实现Insert(x) – 每次我有一个完整的叶子,我想把它分成两个分开的叶子.
一个键的键等于或低于中值键,第二个键将包含值高于中值的键.

如何在不损害运行时间的情况下找到此中位数？

我想过：

>将每个内部节点和叶子表示为较小的B树,但只有当树完全平衡时,中位数才是根(或根中的一个元素).
>将每个内部节点和叶子表示为双向链表.并且在插入输入时尝试获取中值键,但是输入不适用于它.
>表示为数组可能会给我中间,但是当我将其拆分时,我需要至少O(n / 2)将键插入到新数组中.

我能做什么？

关于搜索,想法明智：成功和不成功搜索之间的区别在于在叶子中搜索,但我仍然需要通过树的不同键“运行”以确定密钥是否在树中.那怎么可能是O(1)？

解决方法

在B树中,所有值都存储在叶子中.

请注意,您可以将每个叶子的指针添加到下一个叶子,除了标准B树之外,还可以获得包含所有元素的有序链接列表.

现在,请注意,假设您知道此链接列表中的当前中位数是什么 – 在插入/删除时,您可以便宜地计算新的中位数(它可以是相同的节点,下一个节点或前一个节点,没有其他选择).
请注意,修改此指针是O(1)(尽管插入/删除本身是O(logn).

鉴于这些知识 – 可以缓存指向中值元素的指针,并确保在删除/插入时保留它.当你要求中位数时 – 只需从缓存中取中位数 – O(1).

关于不成功的搜索 – O(1){有很高的可能性} – 这个是尖叫bloom filters,这是一个概率集实现,从来没有假阴性(从来没有说过某些东西没有设置)但是有一些误报(说某些东西在缓存中,而事实上并非如此).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!