AVL搜索树插入多元素触发空指针异常，求排查解决思路

嘿，我帮你找到了几个导致空指针异常的关键问题，咱们一步步拆解：

1. balance方法的逻辑分支完全写错了 #

这是最核心的问题！你看你的balance方法里，处理右子树失衡的部分，else分支的逻辑完全乱了——不管右子树有没有失衡，都会执行doubleWithRightChild，这就导致当树本身是平衡的时候，强行去操作可能为空的右子节点，直接触发NPE。

原代码的错误分支：

else {
    if (height(t.rightChild) - height(t.leftChild) > IMBALANCE_ALLOWED) {
        if (height(t.rightChild.rightChild) >= height(t.rightChild.leftChild)) {
            t = rotateWithRightChild(t);
        }
    } else {
        t = doubleWithRightChild(t);
    }
}

正确的逻辑应该是：只有当右子树的高度差超过允许值时，才判断是单旋转还是双旋转；如果树是平衡的，就啥也不做，直接更新高度就行。修复后的balance方法：

private AvlNode<E> balance(AvlNode<E> t) {
    if (t == null) { return t; }
    // 左子树失衡，处理左旋转/双左旋转
    if (height(t.leftChild) - height(t.rightChild) > IMBALANCE_ALLOWED) {
        if (height(t.leftChild.leftChild) >= height(t.leftChild.rightChild)) {
            t = rotateWithLeftChild(t); // 这里还有个拼写错误，后面说
        } else {
            t = doubleWithLeftChild(t);
        }
    } 
    // 右子树失衡，处理右旋转/双右旋转
    else if (height(t.rightChild) - height(t.leftChild) > IMBALANCE_ALLOWED) {
        if (height(t.rightChild.rightChild) >= height(t.rightChild.leftChild)) {
            t = rotateWithRightChild(t);
        } else {
            t = doubleWithRightChild(t);
        }
    }
    // 不管平不平衡，最后都要更新当前节点的高度
    t.height = Math.max(height(t.leftChild), height(t.rightChild)) + 1;
    return t;
}

2. 方法名拼写错误：rotateWithLefChild少了个t #

你把rotateWithLeftChild写成了rotateWithLefChild（少了一个字母t），虽然Java不会报错，但在doubleWithLeftChild和doubleWithRightChild里调用这个方法时，配合上面的balance逻辑错误，很容易在处理空节点时触发异常。赶紧把所有地方的rotateWithLefChild改成rotateWithLeftChild，比如：

修复后的单左旋转方法：

private AvlNode<E> rotateWithLeftChild(AvlNode<E> k2) {
    AvlNode<E> k1 = k2.leftChild;
    k2.leftChild = k1.rightChild;
    k1.rightChild = k2;
    k2.height = Math.max(height(k2.leftChild), height(k2.rightChild)) + 1;
    k1.height = Math.max(height(k1.leftChild), k2.height) + 1;
    return k1;
}

还有doubleWithLeftChild和doubleWithRightChild里的调用也要同步修正。

3. height方法必须处理null节点 #

你没贴height方法的实现，但我猜你可能没处理null的情况——如果直接返回t.height，当t是null时就会炸。正确的height方法应该给空节点返回0（AVL树的约定）：

private int height(AvlNode<E> t) {
    return t == null ? 0 : t.height;
}

额外的排查小技巧 #

1. 单步调试第二个元素的插入过程：第一个元素没问题，第二个才炸，说明问题出在第一次balance操作上。一步步跟踪节点的创建、链接、旋转，看哪一步出现了意外的null引用。
2. 检查AvlNode的构造函数：别漏了初始化height字段！新创建的节点高度应该是1，不然后续计算高度差会乱：

private static class AvlNode<E> {
    E item;
    AvlNode<E> leftChild;
    AvlNode<E> rightChild;
    int height;

    AvlNode(E item, AvlNode<E> left, AvlNode<E> right) {
        this.item = item;
        this.leftChild = left;
        this.rightChild = right;
        this.height = 1; // 单个节点的高度是1，必须初始化！
    }
}

3. 加日志打印：在insert、balance、旋转方法里加一行日志，比如System.out.println("当前节点：" + (t == null ? "null" : t.item) + "，左子：" + (t.leftChild == null ? "null" : t.leftChild.item) + "，右子：" + (t.rightChild == null ? "null" : t.rightChild.item));，这样能快速定位到哪一步节点变成了null。

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