AVL树右旋操作中仅更新部分节点高度的技术疑问

先看你提到的右旋实现代码：

def rightRotate(self, z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(self.getHeight(z.left),
                       self.getHeight(z.right))
    y.height = 1 + max(self.getHeight(y.left),
                       self.getHeight(y.right))
    return y

核心原因是：只有子树结构发生改变的节点，高度才会变化，才需要重新计算。我们拆解右旋操作的结构变化来分析：

• 右旋操作仅改动了三个指针：y.right指向z，z.left指向T3。其他所有节点的子树结构完全没动。
• 节点z的左子树从原来的y变成了T3，子树结构发生变化，因此必须重新计算它的高度（高度依赖左右子树的高度）。
• 节点y的右子树从原来的T3变成了z，子树结构发生变化，因此也必须重新计算它的高度。
• 至于你提到的节点8：它属于y的左子树，整个右旋过程中，它的子树没有任何修改，父节点也没变，因此它的高度和右旋前完全一致，根本不需要更新。你觉得它高度变化，大概率是混淆了「节点所在的层级」和「节点高度」的概念——层级是相对于根的位置，而高度是该节点到最远叶子的路径长度，两者不是一回事。

再举个具体的例子：
假设右旋前：

• 8是叶子节点，高度为1
• T3（比如是10）也是叶子节点，高度为1
• y（9）的高度是 1 + max(8.height, T3.height) = 2
• z（11）的高度是 1 + max(y.height, z.right.height) = 3

右旋后：

• 8的子树没动，高度还是1
• T3的子树没动，高度还是1
• z的左子树变成T3，所以z的高度重新计算为 1 + max(T3.height, z.right.height)（假设z.right高度不变）
• y的右子树变成z，所以y的高度重新计算为 1 + max(8.height, z.new_height)

可以看到，8的高度自始至终没有变化，只有z和y的高度因为子树结构改动需要更新。

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