如何在AVL树旋转后正确更新节点高度？插入节点时高度更新困惑

问题回顾 #

图中展示了一棵含50、52节点的AVL树，标注了H（高度）和BF（平衡因子）。插入节点51后，向上更新祖先高度时，节点50的高度变为3、BF变为2，树失衡；执行右左旋转后，高度彻底混乱。需求明确：

1. 插入节点时如何正确更新所有祖先高度
2. 旋转操作后如何修复高度计算

平衡因子公式：BF = node.right.height - node.left.height

附上你的实现代码：

public void insertTree(String word) {
    if (nodeCount == 0) {
        this.root = new AVLNode(word, 1, 0, null, null, null);
        AVLNode left = new AVLNode(null, null, 0, 0, this.root, null, null);
        AVLNode right = new AVLNode(null, null, 0, 0, this.root, null, null);
        this.root.setLeft(left);
        this.root.setRight(right);
        this.nodeCount++;
        return;
    }

    AVLNode nodeFound = treeSearch(word, this.root);
    AVLNode left = new AVLNode(null, 0, 0, nodeFound, null, null);
    AVLNode right = new AVLNode(null, 0, 0, nodeFound, null, null);
    nodeFound.setWord(word);
    nodeFound.setLeft(left);
    nodeFound.setRight(right);
    nodeFound.setHeight(1);
    nodeFound.setBF(0);
    this.nodeCount++;

    // Update height
    updateTree(nodeFound.getParent());
}

public void updateTree(AVLNode node) {
    while (node != null) {
        AVLNode nodeParent = node.getParent();
        node.setHeight(height2(node));
        balanceFactor(node);
        // Check if its necessary to do any rotation. Update the ancestor of the node
        balance(node);
        node = nodeParent;
    }
}

public int height(AVLNode node) {
    int heightLeft = node.getLeft().getHeight();
    int heightRight = node.getRight().getHeight();
    int height = 1 + Math.max(heightLeft, heightRight);
    return height;
}

核心问题分析 #

1. 高度更新逻辑未适配旋转：你的updateTree在旋转后仍按原父节点链遍历，但旋转已经改变了节点的层级关系，导致旋转后的节点高度未被正确重新计算。
2. 旋转操作未同步更新高度：旋转会改变3个节点的父子关系（原节点、子节点、孙子节点），这三个节点的高度都依赖子节点的最新状态，但你的代码没有在旋转后主动更新这些节点的高度。
3. 冗余空节点设计：给每个节点创建空左右子节点的设计不仅浪费空间，还可能导致高度计算的隐性错误（比如空节点高度设为0的逻辑是否统一）。

具体修复方案 #

1. 重构高度计算方法（去掉冗余空节点） #

先把空节点的设计去掉，直接用null表示空叶子，修改height方法处理空节点：

public int height(AVLNode node) {
    if (node == null) return 0; // 空节点高度为0
    return 1 + Math.max(height(node.getLeft()), height(node.getRight()));
}

对应修改insertTree的节点创建逻辑，不再生成空的左右子节点：

// 初始化根节点时
this.root = new AVLNode(word, 1, 0, null, null, null);
this.root.setLeft(null);
this.root.setRight(null);

// 插入新节点时
nodeFound.setWord(word);
nodeFound.setLeft(null); // 空左子节点
nodeFound.setRight(null); // 空右子节点
nodeFound.setHeight(1);
nodeFound.setBF(0);

2. 修复旋转操作的高度更新 #

旋转完成后，必须从下往上更新涉及节点的高度（先更新原节点，再更新旋转后的新根）。以左旋、右旋、右左旋转为例：

// 左旋：x是失衡节点，y是x的右子节点，旋转后y成为子树新根
private AVLNode rotateLeft(AVLNode x) {
    AVLNode y = x.getRight();
    AVLNode T2 = y.getLeft();

    // 调整父子关系
    y.setParent(x.getParent());
    if (x.getParent() != null) {
        if (x == x.getParent().getLeft()) {
            x.getParent().setLeft(y);
        } else {
            x.getParent().setRight(y);
        }
    } else {
        root = y; // x是根节点，旋转后y成为新根
    }
    y.setLeft(x);
    x.setParent(y);
    x.setRight(T2);
    if (T2 != null) T2.setParent(x);

    // 从下往上更新高度：先更新x，再更新y
    x.setHeight(height(x));
    y.setHeight(height(y));

    return y;
}

// 右旋：y是失衡节点，x是y的左子节点，旋转后x成为子树新根
private AVLNode rotateRight(AVLNode y) {
    AVLNode x = y.getLeft();
    AVLNode T2 = x.getRight();

    // 调整父子关系
    x.setParent(y.getParent());
    if (y.getParent() != null) {
        if (y == y.getParent().getLeft()) {
            y.getParent().setLeft(x);
        } else {
            y.getParent().setRight(x);
        }
    } else {
        root = x; // y是根节点，旋转后x成为新根
    }
    x.setRight(y);
    y.setParent(x);
    y.setLeft(T2);
    if (T2 != null) T2.setParent(y);

    // 从下往上更新高度：先更新y，再更新x
    y.setHeight(height(y));
    x.setHeight(height(x));

    return x;
}

// 平衡处理方法：返回旋转后的子树根节点
private AVLNode balance(AVLNode node) {
    int bf = node.getBF();
    // 右子树过重（BF > 1）
    if (bf > 1) {
        AVLNode rightChild = node.getRight();
        int rightBf = rightChild.getBF();
        // 右左旋转：先右旋右子节点，再左旋当前节点
        if (rightBf < 0) {
            node.setRight(rotateRight(rightChild));
            return rotateLeft(node);
        } else {
            // 单纯左旋
            return rotateLeft(node);
        }
    }
    // 左子树过重（BF < -1）
    else if (bf < -1) {
        AVLNode leftChild = node.getLeft();
        int leftBf = leftChild.getBF();
        // 左右旋转：先左旋左子节点，再右旋当前节点
        if (leftBf > 0) {
            node.setLeft(rotateLeft(leftChild));
            return rotateRight(node);
        } else {
            // 单纯右旋
            return rotateRight(node);
        }
    }
    // 不需要旋转，返回原节点
    return node;
}

3. 修改updateTree的遍历逻辑 #

旋转后，原节点的位置被新根节点替代，需要从新根的父节点继续向上更新高度，而不是原节点的父节点：

public void updateTree(AVLNode node) {
    while (node != null) {
        AVLNode nodeParent = node.getParent();
        // 更新当前节点的高度和BF
        node.setHeight(height(node));
        balanceFactor(node);
        
        // 执行平衡旋转，获取旋转后的子树根节点
        AVLNode rotatedRoot = balance(node);
        if (rotatedRoot != node) {
            // 发生了旋转，接下来从新根的父节点继续向上更新
            node = rotatedRoot.getParent();
        } else {
            // 未旋转，继续遍历原父节点
            node = nodeParent;
        }
    }
}

// 平衡因子计算方法
private void balanceFactor(AVLNode node) {
    int leftHeight = node.getLeft() == null ? 0 : node.getLeft().getHeight();
    int rightHeight = node.getRight() == null ? 0 : node.getRight().getHeight();
    node.setBF(rightHeight - leftHeight);
}

验证逻辑 #

插入节点51的流程：

1. 插入51作为52的左子节点
2. 从52开始向上更新高度：52的高度变为2，BF变为-1
3. 继续到50：50的高度变为3，BF变为2（右子树过重）
4. 触发右左旋转：先右旋52（此时51成为52的父节点），再左旋50（51成为新的根节点）
5. 旋转后依次更新50、52、51的高度，最后从51的父节点（无）结束遍历
6. 最终所有节点的高度和BF都会恢复正常

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