我对 AVL 树做了测试。有一个问题引入了一个 undo 函数，该函数只能在插入 AVL 树后调用，并且删除之前插入的节点。我可以改变插入值的方式，只要它仍然具有 O(log n) 时间复杂度。
接下来的问题是：这个 undo 函数的最佳时间复杂度是多少，为什么？
我认为这是O(log n)，因为正常删除可能需要旋转从根到插入节点的路径中的每个节点。但显然这不是正确的答案。我错过了什么？
撤消操作可以在 O(1) 时间内完成，但实际上您必须更改插入节点的方式。
我们知道有关标准 AVL 树中最后插入的节点的一些信息：
它是一片叶子。即使插入导致一次或多次旋转，这些旋转也永远不会将子节点附加到新插入的节点。
无需旋转即可将其移除（即使在插入时进行了旋转）。
但是，插入可能意味着从根到插入节点的路径上的所有节点的平衡因子发生变化（在最坏的情况下），因此如果我们进行撤消，我们仍然需要恢复这些平衡因子操作。
虽然前两点暗示撤消操作为 O(1)，但最后一点意味着我们仍然有 O(log𝑛) 最坏情况。
由于最后一个“障碍”，我建议采用以下方法：
插入时，不要对其进行任何旋转，也不要为其调整任何平衡系数。推迟这些平衡操作，直到执行另一次插入或删除，然后first执行推迟的重新平衡（如果有），然后才执行下一个操作（与插入时的方式相同）。这意味着您将 O(log𝑛) 的最坏情况时间复杂度添加到最坏情况下本身也是 O(log𝑛) 的操作，但 O(log𝑛 + log𝑛) 仍然是 O(log𝑛)，因此我们可以执行此推迟重新平衡而不影响操作本身的时间复杂度（下一个插入/删除）。
插入时，请记住插入位置（即记住父节点引用，如果有）。如果您已经记住了一个插入点（对于可能的前面插入），请覆盖该信息。
删除时，将上面提到的信息删除，这样就不会用于后续的撤消操作——这是不允许的）。
现在撤消很容易：确认最后一个操作是插入，然后删除插入的节点。因为我们已经推迟了任何轮换和平衡因子的计算，所以没有什么可做的。现在这是一个 O(1) 操作。
当您搜索一个节点并且它恰好是通过最近操作插入的节点时，那么您可能需要比树已正确重新平衡时多遍历一个节点。但这并不影响搜索操作的时间复杂度，因为 O(log𝑛 + 1) = O(log𝑛)。
结论：通过这种类型的“延迟重新平衡”，您可以实现 O(1) 时间复杂度的撤消。