在 AVL 树中，每次我们重新平衡插入和删除时，它都需要恒定数量的单轮和双轮旋转，因为我们只需要检查从插入点或删除点到根的路径。
如果我们有一棵不平衡的树，我们将不得不检查是否每个可能的节点都是平衡的，因此O(n)重新平衡不平衡的树将花费成本。这个对吗？
问问题
7097 次
1 回答
8
重新平衡一棵不平衡的树确实需要时间 O(n)，但不是因为你提到的原因。在 AVL 树中，如果在插入元素之前树最大程度地不平衡，则插入和删除可能需要 Θ(log n) 旋转。这可能需要 O(n log n) 时间来重新平衡树，因为您可能对每个 n 个节点执行 O(log n) 工作。
但是，使用其他算法，您可以在 O(n) 时间内重新平衡一棵树。一个简单的选择是对树进行中序遍历以按排序顺序获取元素，然后通过自下而上递归地构建树来从这些元素中重建最佳 BST。或者，您可以使用Day-Stout-Warren 算法，它可以平衡 O(n) 时间和 O(1) 空间中的任何树。
希望这可以帮助！
于 2013-11-01T15:21:28.763 回答