您将如何实现具有惰性删除的平衡树？
更具体地说，是 AVL 树。 是否可以？ 我想这样做，但我认为未删除的节点在管理轮换时可能会出现问题。
我有一个可以正常工作的，但我想将这个带有延迟删除功能的用于其他用途。
More specifically, an AVL tree. Is it possible? I'd like to do it, but I'm thinking the undeleted nodes may be problematic to manage with the rotations.
I have one that works normally, but I'd like to use this one with lazy deletion for something else.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您希望它相对于所有节点（包括标记为删除的节点）保持“平衡”，您无需执行任何操作 - 您已经在那里了。
如果您希望它相对于未删除的节点集保持“平衡” - 问题是为什么？平衡的全部目的是防止失控（线性最坏情况）搜索，这取决于在节点上，而不是它们的删除状态。
If you want it to remain "balanced" with respect to all node (including the ones marked deleted) you don't have to do anything--you're already there.
If you want it to remain "balanced" with respect to the set of undeleted nodes--the question is why? The whole point of balancing is to prevent run away (linear worst case) searches and that depends on the nodes, not their deletion status.
在 AVL 树的上下文中，不删除到底意味着什么？
这可能意味着您不进行删除操作，也就是说，您根本不更新树。
这将导致树错误地重新平衡，因为平衡因子的向上扫描将使用错误的平衡因子。
这可能意味着更新平衡因素但不平衡。
这意味着，当您决定删除某些内容时，平衡因子最终会大于 2 或小于 -2； 这意味着需要多次旋转来纠正。 但这里的问题是，在旋转时，您无法再知道是否已经消除了子树深度； 因为虽然您知道一侧有太多的 3 个子树深度，但您不再知道正是一个元素导致了每一级的额外深度 - 您通常知道这一点，因为您一次添加或删除单个元素- 所以你不知道需要旋转多少次。 您可能会进行三次旋转，但只丢失一个子树深度，因为该深度有两个元素。 事实上，您如何知道要旋转哪些元素才能获得必要的元素？ 它们不一定都存在于您选择的删除元素和平衡因子为 3 的点的路径中。
我不确定，但我会大胆地说，正如我们所知，惰性删除会破坏 AVL 。
无论如何，你为什么要拖延？ AVL 的全部意义在于分摊每次添加/删除的再平衡成本，以便保持 O(log n) - 为什么要为规模更大、频率更低的再平衡建立再平衡债务呢？
What exactly does not deleting mean in the context of an AVL tree?
It could mean you do no work on deletion, which is to say, you don't update the tree at all.
This will cause the tree to rebalance incorrectly, because the upward scan for balance factors will be working with incorrect balance factors.
It could mean updating the balance factors but not balancing.
This means you would end up, when you did decide to delete something, with balance factors greater than 2 or smaller than -2; which implies multiple rotations to correct. The problem here though is that you can no longer know, upon a rotation, whether or not you've eliminated a subtree depth; because although you know there are say 3 subtree depths too many on one side, you no longer know it's exactly one element which is causing each level of that extra depth - something you normally know because you're adding or removing single elements at a time - so you have no idea how many rotations you need to do. You might do three rotations and only have lost one subtree depth, because there were two elements at that depth. In fact, how would you even be able to know which elements to rotate to get at the necessary elements? they wouldn't necessarily all exist in the path from your chosen delete element and the point where the balance factor is 3.
I'm not certain, but I'll go out on a limb and say lazy deletes breaks AVL as we know it.
Why would you want to delay, anyway? the whole point of AVL is to amortize the rebalance cost across each add/delete so you stay at O(log n) - why build up rebalance debt for larger, less frequent rebalancing?