调试AVL树删除：不平衡节点不在删除路径上

Question

我正在用 C++ 实现 AVL 树，我遇到了一种情况，在删除节点并重新平衡树后，不直接位于从被删除节点到根的路径上的节点变得不平衡。我已经完成了删除和重新平衡算法，但我似乎无法识别问题。

这是任何操作之前的初始 AVL 树状态： 我想删除值为“914”的节点。根据我的算法，我继续删除，然后执行必要的旋转以重新平衡树。然而，在删除和重新平衡过程之后，我最终得到一个不平衡的节点，该节点不是已删除节点的直接祖先。

这是删除和重新平衡操作后的树：

我的算法会在每次旋转后更新高度和平衡，并且它似乎遵循正确的 AVL 删除过程。然而，它最终导致节点“381”不平衡，我不明白为什么。

Answer 1

错误出现在您用于平衡根部的第一次旋转中（a 部分）：不需要进行此旋转。仅当根的左子节点是“右重”时才需要它。但事实并非如此。因此，您不应该执行“a 部分”，而只在右侧的根部应用一次旋转。 这是从起点开始的整个序列：

             ___720___
            /         \
       ___381__       914
      /        \      / \
   _169_       459  735 915
  /     \      / \    \
159     272  426 561  783
  \     / \      / \
  165 218 286  537 717

删除914后

             ___720___
            /         \
       ___381__       915
      /        \      /
   _169_       459  735
  /     \      / \    \
159     272  426 561  783
  \     / \      / \
  165 218 286  537 717

节点 915 不平衡：由于它的左子节点右重，我们需要双重旋转（首先向左旋转 735，然后向右旋转 915）：

             ___720___
            /         \
       ___381__       783
      /        \      / \
   _169_       459  735 915 
  /     \      / \
159     272  426 561
  \     / \      / \
  165 218 286  537 717

节点 720 不平衡。但这里 720 的左孩子不是右重，所以我们需要 720 向右旋转 

single

：

       ______381_____
      /              \
   _169_            _720_
  /     \          /     \
159     272      459     783 
  \     / \      / \     / \
  165 218 286  426 561 735 915 
                   / \
                 537 717

现在树已经平衡了。