如何在存储最深子树高度的AVL树中区分单旋转与双旋转？

问题背景 #

我正在实现AVL树，每个节点存储其下方最深子树的高度，树的表示格式为「value: height」，示例树如下：

0: 2
 \
  1: 1
   \
    2: 0

我用以下TypeScript函数计算平衡因子，公式为左子树高度减右子树高度，未定义子节点返回-1：

private balanceFactor(currentNode: AVLTreeNode<E> | undefined): number {
    if (currentNode === undefined) {
      return -1;
    }
    let leftHeight = currentNode.hasLeft() ? currentNode.getLeft().getHeight() : -1;
    let rightHeight = currentNode.getRight() ? currentNode.getRight().getHeight() : -1;
    return leftHeight - rightHeight
}

参考的旋转逻辑如下：

balance(N) = Depth(Nleft) - Depth(Nright)

if (balance(P) > 1) {
    if (balance(L) < 0) {
        rotate_left(L);
    }
    rotate_right(P);
}
else if (balance(P) < -1) {
    if (balance(R) > 0) {
        rotate_right(R); 
    }
    rotate_left(P);      
}

双旋转场景（如下结构）能正常处理：

2: 2
   /
  1: 1
   \
    0: 0

但单旋转场景（如下结构）会被误判为双旋转：

2: 2
 \
  1: 1
   \
    0: 0

问题原因与修正方案 #

问题出在空节点的高度定义与旋转逻辑不匹配：你的平衡因子函数将空节点高度设为-1，但参考的旋转逻辑是基于「空节点高度为0」的AVL树标准定义，导致平衡因子计算偏差，触发错误的旋转判断。

具体修正步骤： #

1. 调整平衡因子函数的空节点高度定义
   将未定义子节点的高度从-1改为0，修改后的函数：

private balanceFactor(currentNode: AVLTreeNode<E> | undefined): number {
    if (currentNode === undefined) {
      return 0;
    }
    let leftHeight = currentNode.hasLeft() ? currentNode.getLeft().getHeight() : 0;
    let rightHeight = currentNode.getRight() ? currentNode.getRight().getHeight() : 0;
    return leftHeight - rightHeight
}

2. 同步节点高度的存储逻辑
   确保节点的height属性符合标准定义：

• 空节点高度为0
• 叶子节点高度为1（节点高度 = max(左子树高度, 右子树高度) + 1）
  修正后，单旋转场景的树结构应表示为：

2: 3
 \
  1: 2
   \
    0: 1

修正后逻辑验证 #

以单旋转场景为例：

• 节点0的平衡因子：0-0=0
• 节点1的平衡因子：0-1=-1（左空高度0，右子树高度1）
• 节点2的平衡因子：0-2=-2（左空高度0，右子树高度2）
  此时进入balance(P) < -1分支，检查右子节点（节点1）的平衡因子为-1 < 0，无需执行rotate_right(R)，直接执行rotate_left(P)，符合单旋转的需求，不会误判为双旋转。

内容的提问来源于stack exchange，提问作者M. Nicol