AVL树插入后Undo操作的最优时间复杂度及误区解析

你忽略了AVL树插入操作的核心特性：插入后最多仅需一次旋转即可恢复整个树的平衡性，且仅常数个节点的平衡因子和结构会被修改。

常规删除操作需要O(log n)时间，是因为删除可能导致从删除节点到根的路径上多个节点失衡，需要逐层向上调整平衡。但插入操作的逻辑完全不同：

• AVL树插入时，先按BST规则将节点作为叶子插入，随后从该节点向上遍历检查平衡因子。
• 一旦遇到第一个平衡因子变为±2的节点，仅需一次单旋或双旋就能修复整个树的平衡。旋转完成后，更高层节点的平衡因子不会再受影响——因为旋转会将该失衡节点的平衡因子恢复至0，同时其父节点的平衡因子也会回到插入前的状态（或变为0），上层节点无需再调整。
• 整个插入过程中，只有插入节点、其祖先中到第一个失衡节点为止的常数个节点（最多3个，对应双旋场景）的平衡因子被修改，旋转操作也仅涉及2-3个节点的结构调整。

因此，只要在插入时记录以下常数级的关键信息（无需额外O(log n)空间）：

• 刚插入的节点引用
• 所有平衡因子被修改的节点及其原始平衡因子值
• 若发生旋转，记录旋转类型（单旋/双旋）及涉及的节点

Undo操作时只需执行：

1. 删除插入的节点
2. 将记录的节点平衡因子恢复为原始值
3. 反转旋转操作（若有），恢复树的结构

所有这些操作都是常数时间，即O(1)复杂度，而非你之前认为的O(log n)。

内容的提问来源于stack exchange，提问作者יאיר אבישר