关于AVL树节点高度计算Python实现的疑问

先帮你指出代码里一个小问题：你的Node类构造函数里，self.leftchild和self.rightchild没有初始化值，运行时会触发AttributeError，建议修正为：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.height = 0
        self.leftchild = None
        self.rightchild = None

接下来逐个解答你的疑问：

疑问1：node.height是否为Python已定义的函数？ #

完全不是，node.height是你自己在Node类中定义的实例属性，不是Python内置的函数或属性。你在Node的__init__方法里初始化了self.height=0，所以每个创建出来的Node对象都会自带这个属性，用来存储该节点的高度值。

疑问2：递归调用calcHeight方法时，仅返回node.height是如何实现高度返回的？ #

其实你的当前实现存在逻辑缺陷——你只在节点初始化时把height设为0，但没有在AVL树的插入、删除、旋转等操作中更新这个属性，所以现在的calcHeight只是返回你一开始设置的固定值0，并没有真正计算节点的实际高度。

要正确实现高度计算，有两种常见方式：

方式1：实时递归计算高度 #

修改calcHeight方法，让它动态计算节点的高度（节点高度 = 左右子树高度的最大值 + 1）：

def calcHeight(self, node):
    if not node:
        return -1  # 空节点高度设为-1，这样叶子节点高度就是0
    return 1 + max(self.calcHeight(node.leftchild), self.calcHeight(node.rightchild))

这种方式不需要维护node.height属性，每次调用都实时递归计算，但缺点是频繁调用时性能会稍差。

方式2：维护node.height属性 #

如果你想保留node.height属性来存储高度，就需要在所有会改变树结构的操作（插入、删除、旋转）后，回溯更新受影响节点的高度。比如新增一个更新高度的方法：

def updateHeight(self, node):
    if node:
        # 基于子树高度更新当前节点高度
        node.height = 1 + max(self.calcHeight(node.leftchild), self.calcHeight(node.rightchild))

然后在插入节点后、完成旋转操作后，调用这个方法来更新路径上的节点高度，这样calcHeight方法就可以直接返回node.height了——前提是你保证每次树结构变化时都同步更新了高度。

内容的提问来源于stack exchange，提问作者2K19EC157 SAARTHAK SHAKARGAYE