平衡不平衡/部分平衡 BST 的复杂性？

Question

在 AVL 树中，每次我们重新平衡插入和删除时，它都需要恒定数量的单次和双次旋转，因为我们只需要检查从插入或删除点到根的路径。

如果我们有一个不平衡的树，我们将不得不检查是否每个可能的节点都是平衡的，因此O(n)重新平衡一个不平衡的树会产生成本。这样对吗？

Answer 1

重新平衡不平衡的树确实需要时间 O(n)，但不是因为您提到的原因。在 AVL 树中，如果在插入元素之前树最大程度地不平衡，则插入和删除可能需要 Θ(log n) 旋转。这可能需要 O(n log n) 时间来重新平衡树，因为您可能对 n 个节点中的每一个都执行 O(log n) 工作。

但是，使用其他算法，您可以在 O(n) 时间内重新平衡树。一个简单的选择是对树进行中序遍历以按排序顺序获取元素，然后通过自底向上递归构建树来从这些元素重建最佳 BST。或者，您可以使用Day-Stout-Warren 算法，它可以在 O(n) 时间和 O(1) 空间中平衡任何树。

希望这可以帮助！