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

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

  •  
  •   mizuku · 126 天前 · 1845 次点击
    这是一个创建于 126 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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
        1
    heyenyan   126 天前 via Android
    9 为什么会失衡?
        2
    Alozxy   126 天前
    不知到你用的是哪一版的教材,我手上的这一版只有写插入操作,没有删除操作的描述
        3
    dlsflh   126 天前 via Android
    咦…教材出错不是很正常的事情吗
        4
    mizuku   126 天前
    @heyenyan 左边是 3,右边是 1
        5
    mizuku   126 天前
    @Alozxy 是 github 上的,你可以看我的链接.我以为这个链接是照抄课本的,难道课本没有,是自己补充的?
        6
    Alozxy   126 天前
    @mizuku 严的书上是没有的
        7
    Alozxy   126 天前
    @mizuku
    其实就 avl 树的删除来看,我觉得你是误解了删除的情况,删除的情况和插入的情况是不同的
    就拿你的例子来说,插入的时候是不会有这种情况的,而删除的时候这种情况只需要进行一次单旋就行
        8
    mizuku   125 天前
    @Alozxy 我知道只需一次单旋,只是 github 上的那个没考虑,既然你这么说了我就放心了
        9
    Alozxy   125 天前
    @mizuku 大概看了一下你给的代码,感觉像是作者自己写的,很多情况没有考虑到,还是自己买书看吧,至少靠谱点
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2215 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 27ms · UTC 10:30 · PVG 18:30 · LAX 02:30 · JFK 05:30
    ♥ Do have faith in what you're doing.