AVL 树中的删除

从AVL树中删除节点与在二叉搜索树中删除节点类似。删除可能会扰乱AVL树的平衡因子，因此需要重新平衡树以保持AVL属性。为此，我们需要执行旋转。旋转有两种类型：L旋转和R旋转。在这里，我们将讨论R旋转。L旋转是它们的镜像。

如果待删除节点位于关键节点的左子树中，则需要应用L旋转；否则，如果待删除节点位于关键节点的右子树中，则应用R旋转。

我们假设A是关键节点，B是其左子树的根节点。如果节点X（位于A的右子树中）将被删除，则可能出现三种不同的情况：

R0旋转（节点B的平衡因子为0）

如果节点B的平衡因子为0，并且删除节点X后节点A的平衡因子被扰乱，则通过使用R0旋转来旋转树，从而重新平衡树。

关键节点A向右移动，节点B成为树的根，T1作为其左子树。子树T2和T3成为节点A的左子树和右子树。R0旋转涉及的过程如图所示。

示例

删除下图所示AVL树中的节点30。

解决方案

在这种情况下，节点B的平衡因子为0，因此将使用R0旋转来旋转树，如图所示。节点B（10）成为根，而节点A向右移动。节点B的右子节点现在将成为节点A的左子节点。

R1旋转（节点B的平衡因子为1）

如果节点B的平衡因子为1，则执行R1旋转。在R1旋转中，关键节点A向右移动，子树T2和T3分别作为其左子树和右子树。T1将放置为节点B的左子树。

R1旋转涉及的过程如图所示。

示例

删除下图所示AVL树中的节点55。

解决方案

从AVL树中删除55会扰乱节点50（即节点A）的平衡因子，节点A成为关键节点。这是R1旋转的条件，在这种条件下，节点A将向右移动（如下图所示）。B的右侧现在成为A的左侧（即45）。

解决方案中涉及的过程如图所示。

R-1旋转（节点B的平衡因子为-1）

如果节点B的平衡因子为-1，则执行R-1旋转。这种情况与LR旋转的处理方式相同。在这种情况下，节点C（节点B的右子节点）成为树的根节点，其中B和A分别作为其左子节点和右子节点。

子树T1、T2分别成为B的左子树和右子树；T3、T4分别成为A的左子树和右子树。

R-1旋转涉及的过程如图所示。

示例

删除下图所示AVL树中的节点60。

解决方案

在这种情况下，节点B的平衡因子为-1。删除节点60会扰乱节点50的平衡因子，因此需要对其进行R-1旋转。节点C（即45）成为树的根节点，节点B（40）和A（50）分别作为其左子节点和右子节点。