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

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

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

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

平衡二叉树

A. 仅 I B. 仅 II C. 仅 I、II D. 仅 I、III

[tag_link]

正确答案：A

非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置。若删除的是 T1 的叶结点，则删除后平衡二叉树不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树 T1 与 T3 相同;若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树 T3 与 T1 可能不同。I 正确。例如，如下图所示，删除结点 0，平衡二叉树失衡调整，再插入结点 0 后，平衡二叉树和以前不同。对于比较绝对的说法 II 和 III，通常只需举出反例即可。

若删除的是 T1 的非叶结点，且删除和插入操作均没有导致平衡二叉树的调整 (这时可以首先想到删除的结点只有一个孩子的情况)，则该结点从非叶结点变成了叶结点，T1 与 T3 显然不同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树和以前不同。

若删除的是 T1 的非叶结点，且删除和插入操作后导致了平衡二叉树的调整，则该结点有可能通过旋转后继续变成非叶结点，T1 与 T3 相同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树失衡调整，调整后的平衡二叉树和以前相同。