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