V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mizuku
V2EX  ›  算法

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

  •  
  •   mizuku · 2019-08-10 02:20:13 +08:00 · 3939 次点击
    这是一个创建于 1933 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    9 条回复    2019-08-10 23:51:35 +08:00
    heyenyan
        1
    heyenyan  
       2019-08-10 07:16:23 +08:00 via Android
    9 为什么会失衡?
    Alozxy
        2
    Alozxy  
       2019-08-10 07:25:37 +08:00
    不知到你用的是哪一版的教材,我手上的这一版只有写插入操作,没有删除操作的描述
    dlsflh
        3
    dlsflh  
       2019-08-10 08:46:03 +08:00 via Android
    咦…教材出错不是很正常的事情吗
    mizuku
        4
    mizuku  
    OP
       2019-08-10 15:05:57 +08:00
    @heyenyan 左边是 3,右边是 1
    mizuku
        5
    mizuku  
    OP
       2019-08-10 15:07:26 +08:00
    @Alozxy 是 github 上的,你可以看我的链接.我以为这个链接是照抄课本的,难道课本没有,是自己补充的?
    Alozxy
        6
    Alozxy  
       2019-08-10 15:09:33 +08:00
    @mizuku 严的书上是没有的
    Alozxy
        7
    Alozxy  
       2019-08-10 15:11:08 +08:00
    @mizuku
    其实就 avl 树的删除来看,我觉得你是误解了删除的情况,删除的情况和插入的情况是不同的
    就拿你的例子来说,插入的时候是不会有这种情况的,而删除的时候这种情况只需要进行一次单旋就行
    mizuku
        8
    mizuku  
    OP
       2019-08-10 23:09:18 +08:00
    @Alozxy 我知道只需一次单旋,只是 github 上的那个没考虑,既然你这么说了我就放心了
    Alozxy
        9
    Alozxy  
       2019-08-10 23:51:35 +08:00
    @mizuku 大概看了一下你给的代码,感觉像是作者自己写的,很多情况没有考虑到,还是自己买书看吧,至少靠谱点
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2647 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 02:59 · PVG 10:59 · LAX 18:59 · JFK 21:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.