让我们假设您发布的答案是正确的,并且给定的文件系统确实将内容存储在平衡树中。平衡树是一项非常昂贵的操作。保持树“部分”平衡非常简单,因为当您允许树稍微不平衡时,您只需担心在插入/删除点周围移动事物。然而,当谈到完全平衡的树时,当你移除一个给定的节点时,你可能会突然发现,这个节点的子节点可能属于树的完全相反的一侧,或者对侧的一个子节点已经成为根节点,并且它的所有子节点都需要在树上向上旋转。这需要您进行一连串的旋转,或者将所有项目放入一个数组中并重新创建树。
5
3 7
2 4 6 8
现在去掉7,容易吧?
5
3 8
2 4 6
现在去掉6,还是很容易的,是吗……?
5
3 8
2 4
现在去掉8,呃哦
5
3
2 4
让这棵树成为适当的平衡形式,例如:
4
3 5
2
至少与我们所做的其他移除相比,这是相当昂贵的,并且随着我们树的深度增加而呈指数级恶化。在移除 8 之前,我们可以通过移除 2 和 4 来加快(指数级)速度。特别是如果我们的树的深度超过 3 层。
没有排序删除平均为 O(K * log_I(N)^2)。N 表示元素总数,K 表示要删除的数量,I 是允许给定节点的子节点数,log_I(N) 然后是深度,对于每个深度级别,我们以二次方的方式增加操作次数。
使用一些排序帮助进行移除的平均时间为 O(K * log_I(N)),尽管有时排序无法帮助您,并且您无法移除需要重新平衡的内容。尽管如此,将其最小化是最佳的。
编辑:
另一种可能的树排序方案:
8
6 7
1 2 3 4
在这种情况下实现最优移除会更容易,因为我们可以利用我们对事物如何排序的知识。在任何一种情况下都有可能,实际上两者都是相同的,在这种情况下,逻辑更容易理解,因为对于给定的场景,排序更人性化。在任何一种情况下,按顺序都被定义为“首先删除最远的叶子”,在这种情况下,最远的叶子恰好也是最小的数字,我们可以利用这一事实使它更小更优化,但对于所展示的文件系统示例,这一事实不一定正确(尽管可能如此)。