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