AVL树删除规则

Question

对于AVL树，在从需要重构的树中删除节点时，我正在阅读的书指出有一些规则可以遵循来选择要重构的节点。以下是一个示例：

       44
     /   \
    17   62
        /  \
       50  78
      /  \   \
     48  54  88

这是在删除节点17的子节点后，AVL树失去平衡时的情况。

我读的书上指出，我们需要找到第一个失衡的位置z，从节点17开始向上查找，然后y是z中高度更高的孩子，最后x是y中高度更高的孩子。但是，如果y的两个孩子高度相同，则x将与y相同。在这种情况下，x是78，y是62，z是44。

现在提出了一个问题，为什么我们选择x与y在同一侧？如果我选择x不在y的同一侧，AVL树会有什么问题吗？我尝试举例并尝试选择两种类型的x并重构AVL树。但是，我无法找到任何选择x作为任何一个孩子所引起的问题。希望能得到帮助，帮助我解决这个问题。

- jkli123

---

有趣..您能分享一下您的分析，您在哪里找到了不是y的子级的x？ - Karthik Balaguru

@KarthikBalaguru 这种情况下是否可能存在一个不是 y 的子元素 x？如果需要重构，应该如何进行呢？我之前从未考虑过这个问题。 - jkli123

根据标准的三节点重构方法，只有将x作为y的子节点才能完成。简单来说，这是一种针对导致负载不平衡的路径进行修复的方法。因此，为了识别和修复该路径，在高度平衡被破坏时，z应该是第一个不平衡的节点，y应该是z的最高子节点，而x应该是z的孙子节点，且是y的最高子节点。就我所看到的而言，三节点重构过程始终如一地表明——如果y的一个子节点比另一个子节点高，则x是更高的子节点；否则，x是与y在z上相同侧的子节点。 - Karthik Balaguru

Answer 1

有趣的是，在各种网络论坛中，这个主题有很多不同的答案变体。我尝试创建所有可能的AVL树节点删除场景，并观察到如果从AVL树的左侧删除节点以使树失衡，则基于节点可用性执行LL或LR（任何可能的旋转），则树将保持平衡。对于右节点删除也是如此。

此外，需要确保由于旋转而移动的节点是否有子节点，如果它们在旋转之前位于左侧或右侧，则将子节点插入左侧或右侧。

- Ankit