《数据结构与算法分析C++版》AVL树删除操作语句解读求助

在《C++数据结构与算法分析》的AVL树章节中，讲解删除操作时有个细节容易混淆：针对图4.34对应的情况1，当操作从向X插入节点变为从Z的子树中删除节点时，必须额外考虑Y与X深度相同的场景。

核心差异：插入 vs 删除的深度变化逻辑 #

• 插入操作中，情况1的触发原因是向X的左子树Y插入节点，导致X的深度比Z的右子树深2。此时Y的深度必然大于X的右子树（因为插入只会让单侧深度+1），所以单右旋即可修复失衡，无需考虑Y和X深度相等的情况。
• 删除操作中，失衡的触发原因是子树深度减少：当从Z的子树（比如X的右子树或Z的右子树）删除节点后，Z的左子树X比右子树深2。此时X的左子树Y和X的右子树可能深度相等——这种场景在插入时不可能出现，因此必须补充处理：
  • 若Y与X深度相同，对Z执行单右旋后，新的根节点X的左右子树深度一致，不会产生新的失衡，但需要重新计算Z和X的高度；
  • 若Y比X的右子树深，处理逻辑和插入场景一致，单右旋即可修复失衡。

内容的提问来源于stack exchange，提问作者Aaron Swartz