AVL树节点高度计算Python实现疑问：node.height与递归逻辑解析

嘿，我来帮你把这两个疑惑拆解清楚～

1. node.height 是不是Python内置的函数？ #

完全不是哦！node.height 是你在 Node 类里自己定义的实例属性（不是函数）。你在 Node 的构造方法 __init__ 里写了 self.height=0，这就意味着每个创建出来的 Node 对象都会自带这个属性，用来存储该节点在AVL树中的高度值。

不过这里要提个小问题：你当前的 Node 类代码有个错误——leftchild 和 rightchild 没有初始化，运行时会触发 AttributeError，得改成这样：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.height = 0
        self.leftchild = None  # 必须初始化，不然会报错
        self.rightchild = None

2. calcHeight 递归怎么正确返回高度？ #

你现在的 calcHeight 逻辑其实只是返回节点已有的 height 属性值，但目前你只在初始化节点时把 height 设为0，没有在树结构变化时更新这个值，所以它根本没法反映节点的实际高度。

在AVL树中，一个节点的正确高度应该是：1 + max(左子树高度, 右子树高度)（空树的高度定义为-1，这也是你 calcHeight 里返回-1的原因）。所以你需要新增一个更新高度的方法，在节点的左右子树变化后（比如插入、删除、旋转操作后）调用它，来同步节点的 height 属性：

class AVL(object):
    def __init__(self):
        self.root = None

    def calcHeight(self, node):
        if not node:
            return -1
        return node.height

    def calcBalance(self, node):
        if not node:
            return 0
        return self.calcHeight(node.leftchild) - self.calcHeight(node.rightchild)

    # 新增更新高度的方法
    def updateHeight(self, node):
        if node:
            node.height = 1 + max(self.calcHeight(node.leftchild), self.calcHeight(node.rightchild))

举个例子，当你插入一个新节点后，需要从该节点向上回溯，依次调用 updateHeight 更新每个祖先节点的高度，这样 calcHeight 递归时返回的就是正确的高度值了。比如插入操作的大致逻辑会是：

def insert(self, data):
    self.root = self._insert(data, self.root)

def _insert(self, data, node):
    if not node:
        return Node(data)
    # 普通BST插入逻辑
    if data < node.data:
        node.leftchild = self._insert(data, node.leftchild)
    else:
        node.rightchild = self._insert(data, node.rightchild)
    # 插入后更新当前节点高度
    self.updateHeight(node)
    # 计算平衡因子，判断是否需要旋转
    balance = self.calcBalance(node)
    # 后续就是AVL的四种旋转逻辑...
    return node

这样一来，calcHeight 递归时，空节点返回-1，非空节点返回的是已经通过 updateHeight 计算好的实际高度，就能正确支撑平衡因子的计算啦。

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