avl-tree - 您将如何实现具有延迟删除的平衡树？

Question

更具体地说，是 AVL 树。可能吗？我想这样做，但我认为未删除的节点可能难以管理旋转。

我有一个可以正常工作的，但我想用这个延迟删除来做其他事情。

Answer 1

如果您希望它相对于所有节点（包括标记为已删除的节点）保持“平衡”，您无需做任何事情——您已经在那里了。

如果您希望它相对于未删除的节点集保持“平衡”——问题是为什么？ 平衡的重点是防止失控（线性最坏情况）搜索，这取决于节点，而不是它们的删除状态。

Answer 2

在 AVL 树的上下文中，不删除到底意味着什么？

这可能意味着您不进行删除操作，也就是说，您根本不更新树。

这将导致树不正确地重新平衡，因为向上扫描平衡因子将使用不正确的平衡因子。

这可能意味着更新平衡因素但不平衡。

这意味着当您决定删除某些内容时，您最终会得到大于 2 或小于 -2 的平衡因子；这意味着要纠正多次旋转。但是这里的问题是，在旋转时，您不再知道您是否已经消除了子树深度。因为尽管您知道一侧的 3 个子树深度太多，但您不再知道正是一个元素导致了每个级别的额外深度 - 您通常知道这一点，因为您一次添加或删除单个元素- 所以你不知道你需要做多少次旋转。您可能进行了 3 次旋转并且只丢失了一个子树深度，因为在该深度有两个元素。事实上，你怎么会知道要旋转哪些元素以获得必要的元素？它们不一定都存在于您选择的删除元素和平衡因子为 3 的路径中。

我不确定，但我会冒险说惰性删除会破坏我们所知道的 AVL。

无论如何，你为什么要拖延？AVL 的重点是在每次添加/删除时分摊重新平衡成本，因此您保持在 O(log n) - 为什么要为更大、更不频繁的重新平衡建立重新平衡债务？