题目

在任意一棵非空平衡二叉树(AVL 树)T1 中，删除某结点 v 之后形成平衡二叉树 T2 ，再将 v 插入 T2 形成平衡二叉树 T3 。下列关于 T1 与 T3 的叙述中，正确的是( )。

I. 若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同

II. 若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同

III. 若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同

错因

B

误判 II 为"一定不同"。删非叶结点时确实要用前驱/后继顶替再删叶位，结构在 T2 里发生了改变；但插回 v 后 AVL 通过旋转往往能恢复原状（见总解析的反例）。所以"一定不同"过强。同时漏判了 I 也对。

C

把 II 当成对的同时也认 I 对。问题仍在 II——删非叶后再插回 v 不一定会让 T3 与 T1 不同，存在反例使 T3 = T1。

D

把 III 当成"一定相同"。但删除非叶时用前驱替换，再插回 v 时插入路径与原结构里 v 所在位置可能不同（特别当 v 是根、且删除后引发结构平移）；插回后若触发旋转方向与原构造不同，T3 ≠ T1。所以 III 也站不住脚。

总解析

逐条分析：

I. v 是叶结点，T1 与 T3 可能不相同 → ✅ 正确

构造一个删叶子触发旋转的反例。T1：

删 v=1，2 节点的 BF 变成 −2 失衡（左子树空、右子树高 2），对 2 做 RR 左旋后得 T2：

插回 1：1<4→左，1<2→左，作为 2 的左孩子，未触发新失衡。T3：

T3 ≠ T1（根从 2 变成 4），所以"可能不同"成立。

II. v 不是叶结点，T1 与 T3 一定不相同 → ❌ 错误

举一个 T3 = T1 的反例。T1：

v=2（根，非叶）。删除时用前驱 1 替换 v 的值，再删除原 1 所在叶位，T2：

是 AVL（BF=−1）。将 2 插回：2>1→右，2<3→左，落到 3 的左孩子位：

此时 1 的 BF=−2 失衡，3 的 BF=+1 → RL 双旋。先对 3 右旋得 1(_, 2(_, 3))，再对 1 左旋得：

T3 = T1。所以"一定不同"被反例否决。

III. v 不是叶结点，T1 与 T3 一定相同 → ❌ 错误

也可以构造 T3 ≠ T1 的反例。例如删根 v 后用前驱替换、整个结构发生平移，再插回 v 时新插入路径触发的旋转方向与原构造不同，最终 T3 与 T1 形态不一致。所以"一定相同"也不成立。

结论：三条命题中只有 I 一定正确。最终答案是 A。