data-structures - 从 bst 中删除子树并在 logn 时间内平衡树

Question

我们是否可以在平衡二叉搜索树上执行 m 次插入和删除操作，以便删除操作删除一个节点和它下面的整个子树，然后平衡它？整个过程在每一步的分摊时间 O(log n) 内完成？

Answer 1

简短回答:是的，这是可能的。

您所描述的是自平衡二叉树，例如 AVL 树或红黑树。两者都采用 O(log n) 进行删除，其中包括节点的重新排序。 Here是一个页面的链接，该页面描述了这些树以及它们如何工作，比我能详细得多，包括插图。您还可以查看 Wikipedia page of AVL-trees ，他们有一个体面的解释以及插入的动画。以下是您最感兴趣的内容的简短版本:

AVL 树中的删除平均为 O(log n)，重新平衡平均为 O(log n)，最坏情况为 O(1)。这是通过旋转来完成的，这在两个来源中都有很好的解释。

维基百科页面还包含一些代码，如果您需要实现的话。

编辑:

要删除子树，您仍然可以做同样的事情。 Here是对此很好解释的链接。简短版本:删除子树可以完成 O(log n)(请记住，只要不直接重新平衡树，无论删除的节点数如何，删除仍然是 O(log n))，然后树会使用旋转重新平衡自己。这也可以改变你的树的根。删除整个子树当然会产生比仅删除树末端的一个节点更大的高度差。尽管如此，使用旋转可以通过找到第一个节点不平衡然后执行 AVL 重新平衡方案来重新平衡树本身。由于使用了旋转，这应该仍然都是 O(log n)。 Here您会发现树在删除后如何重新平衡自身，这会造成高度不平衡。