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

[mizuku]

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 的情况 是课本出错了吗?这个教材很权威的吧,我还是认为可能自己哪里想错了

[heyenyan]

9 为什么会失衡？

[Alozxy]

不知到你用的是哪一版的教材,我手上的这一版只有写插入操作,没有删除操作的描述

[dlsflh]

咦…教材出错不是很正常的事情吗

[mizuku]

@heyenyan 左边是 3,右边是 1

[mizuku]

@Alozxy 是 github 上的,你可以看我的链接.我以为这个链接是照抄课本的,难道课本没有,是自己补充的?

[Alozxy]

@mizuku 严的书上是没有的

[Alozxy]

@mizuku
其实就 avl 树的删除来看,我觉得你是误解了删除的情况,删除的情况和插入的情况是不同的
就拿你的例子来说,插入的时候是不会有这种情况的,而删除的时候这种情况只需要进行一次单旋就行

[mizuku]

@Alozxy 我知道只需一次单旋,只是 github 上的那个没考虑,既然你这么说了我就放心了

[Alozxy]

@mizuku 大概看了一下你给的代码,感觉像是作者自己写的,很多情况没有考虑到,还是自己买书看吧,至少靠谱点