斗胆质疑一下权威,严蔚敏的《数据结构》的 AVL 树,有一个特殊情况是不是没考虑到?

https://github.com/kangjianwei/Data-Structure/blob/master/▲课本算法实现 /▲09%20 查找 /07%20BalancedBinarySortTree/BalancedBinarySortTree.c#L305-L310

(链接显示不对,调不过来了,总之你看链接的指向应该知道在哪里找...)

在发现左边失衡要调整的时候,值考虑了 LH,RH,但是还有 EH 这种特殊的情况

这种特殊的情况只出现在删除节点时, 测试数据:

依次插入: 9 5 10 -1 6 11 -2 1 2

然后删除 10

会使 9 节点失衡,EH=2,但是这个失衡是 9 右子树某节点删除导致的,而不是 9 左子树插入新节点导致的

这时,似乎需要对 9 当做 LL 型进行旋转:

就像这个代码: https://www.geeksforgeeks.org/avl-tree-set-2-deletion/ 中的:

if (balance > 1 && getBalance(root->left) >= 0) 
    return rightRotate(root);

这里考虑了==0 的情况 是课本出错了吗?这个教材很权威的吧,我还是认为可能自己哪里想错了