计算机考研 408每日一题2025.9.15

【解析】A

对于I，当v是叶结点时，若在删除v后T1没有失去平衡，则T2保持T1的结构不变，再次插入v必然是插入到原本的位置，此时T1与T3相同；若在删除v后T1失去平衡，则经过平衡旋转得到T2与T1结构不同，重新插入v后，T3的结构未必与原来的T1相同。下图（a）给出了一个T1与T3不同的例子。对于II和III，当v不是叶结点时，删除v后，T2的结构可能会发生变化，但重新插入v后，T3的结构既有恢复到与T1相同，也可能与T1不同，取决于删除和插入过程中是否触发了平衡旋转操作。下图（b）和图（c）分别给出了T1与T3相同和不同的例子。综上可知，仅有I的说法正确。

（a）v是叶结点，T1与T3不同

（c）v不是叶结点，T1与T3不同