用于特定目的的二进制搜索树

可以删除o(logn+objects num)中bst的值范围。

我知道最简单的方法是 Deterministic Skip List 数据结构(在继续之前,您可能需要先了解一下此数据结构)。 在确定性跳过列表中,所有实际值都存储在底层,并且在上层有指向它们的指针。插入、搜索和删除在O(logn)中完成。

范围删除操作可以按照以下算法进行:

• 查找范围-o(logn)中的第一个元素
• 在链接列表中继续,删除仍在范围内的所有元素。如果有指向上层的指针的元素-也将其移除,直到到达最顶层(从链接列表中移除)-o(已删除对象的数目)
• 固定指针以适应确定性跳过列表(每个向上指针之间有2-3个元素)

删除范围的总复杂性是O(logn+范围中的对象数)。 注意,如果您选择使用随机跳过列表,您会得到相同的复杂性,但平均而言,并不是最坏的情况。另外,为了满足2-3的需求,您不需要固定上层指针。

确定性跳过列表有一个到2-3树的1-1映射,因此,对于更多的工作,上面描述的过程也可以用于2-3树。

很久以前,在STL之前的日子里,我编写了自己的B-树(BST)算法,因为当时我有一个相当大的数据集(在两个相互依赖的树中大约有700K个项)。我发现,在每100-200次插入/删除后重新平衡是基于486和SGI硬件的实验,我当时可以获得的最高性能。这个数字现在可能不同,或者可能不同,因为它似乎是一个算法优化限制,除非您转换为并行模型。

简而言之,您可以为重新平衡应用修改触发器,并在完成所有修改后允许强制重新平衡。

改善是显著的。25米后,初始直线载荷未完成(终止工艺)。我们进行的再平衡也在15米后被杀死。每100个mods加载一次再平衡,并在不到3米的时间内运行。请注意,在“运行”部分,每个初始条目对树进行了0-8次修改。在近期再次修改树时,您真的需要考虑是否总是需要保持平衡。

嗯,那B-树呢?它们也是平衡的,如果你选择一个大订单——这取决于你有多少个项目——你将节省大量的对象创建/销毁时间。

到2。如果您有一个订单100的B树,您可以通过一个函数调用删除最多100个项目。

到3。这个特性可以应用于几乎所有的树,只需实现一个removesome()函数,它可以删除n个项并进行重新平衡。对于B-树来说,这有点棘手,但可以做到。

注:我想你是个程序员。如果你需要一个完整的,测试过的,现成的解决方案,你需要另一个答案。

如果每个节点都存储其高度而不是平衡因子,那么在AVL树中删除节点及其子节点应该很容易实现。删除节点后,继续旋转,直到两个子节点的差异不超过一个。然后移到树上重复。与正常删除的唯一真正区别是 while 而不是 if 用于测试高度。

这个 Set OCAML标准库中的实现是一个纯功能的AVL树,它满足您的所有需求,尤其是集理论操作(联合、交集、差异)的非常有效的实现。插入和删除是O(log n)。通过将元素表示为集合并使用集合差分,可以删除元素的子树和运行。通过创建一个2元素集并应用集合联合,可以同时插入两个元素。