为什么我的AVL树旋转后输出值异常，树未正常完成重平衡？

问题根因 #

• 旋转操作返回的新根节点未被接收，重平衡结果没有同步到树结构中
  你在insert私有方法中调用LLRoatation(root)时，该方法返回的是旋转后的新父节点，但你没有将返回值赋值给当前的root变量，导致旋转后的结构没有被保留，原有失衡节点仍然作为子树的根，所以重平衡完全不生效，遍历输出自然不符合预期。
• 测试代码调用的preOrder前序遍历方法未实现
  现有代码仅实现了中序遍历的traverseInOrder方法，没有对应前序遍历的逻辑，也会导致你的输出异常。
• 新增节点未初始化height属性（非核心问题，但建议修复）
  新创建AvlNode时没有给height赋初始值，部分场景下可能导致高度计算异常。

修复方案 #

首先修改insert私有方法中的旋转调用逻辑：

// 原有错误代码
if(balanceFactor(root)==2 && balanceFactor(root.leftChild)==1){
    LLRoatation(root);
}
// 修改为
if(balanceFactor(root)==2 && balanceFactor(root.leftChild)==1){
    root = LLRoatation(root);
}

然后补充前序遍历的实现：

// 新增前序遍历公共方法
public void preOrder() {
    preOrder(root);
}

// 新增前序遍历私有实现
private void preOrder(AvlNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.value + " ");
    preOrder(root.leftChild);
    preOrder(root.rightChild);
}

建议补充AvlNode的height初始化：

public AvlNode (int value){
    this.value = value;
    this.height = 0; // 新增初始化，叶子节点初始高度为0
}

修复后效果 #

插入30、20、10执行LL旋转后，树的根节点变为20，左孩子是10，右孩子是30，前序遍历输出为20 10 30，符合AVL树重平衡后的预期结果。

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