首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

关于二叉排序树

  •  
  •   honeyshine75 · 2018-07-06 20:24:30 +08:00 · 1472 次点击
    这是一个创建于 521 天前的主题,其中的信息可能已经有所发展或是发生改变。

    可能是我理解不到位,有个问题想请教各位

    如果在删除二叉排序树叶子节点过程中使得该叶子节点的父节点平衡因子变为 2,那么这时候要不要调整呢? 之所以这么问是因为都说叶子直接删,可又说破坏了平衡二叉树的条件就要旋转。 所以我就不明白了。。。

    第 1 条附言  ·  2018-07-07 08:41:12 +08:00
    我的问题来源:如果叶子节点破坏平衡调整的话题中的 T1 和 T3 不能保证相同的,而答案选择的是 23
    http://m.nowcoder.com/questionTerminal?uuid=dda11740572c4059bcb929feca543751
    14 回复  |  直到 2018-07-07 11:40:00 +08:00
        1
    honeyshine75   2018-07-06 20:24:53 +08:00
    我明明有回车的呀。。。
        2
    lovefantasy   2018-07-06 20:41:44 +08:00 via Android
    建议去看下课本吧,百度下也行啊
        3
    honeyshine75   2018-07-06 21:20:03 +08:00
    @lovefantasy 以及看过了都说叶子直接删
        4
    lcdtyph   2018-07-06 21:38:34 +08:00
    @honeyshine75 #3
    平衡二叉树的删除一般分两步:1.普通查找二叉树上的删除; 2.保持平衡
    你可能只看了第一步
        5
    zzj0311   2018-07-07 00:17:10 +08:00 via Android
    叶子又没有儿子当然直接删,破坏了平衡当然要旋转恢复平衡,一点毛病都没有啊😯
        6
    ynyounuo   2018-07-07 03:42:27 +08:00 via iPhone
    删除当然要调整,否则删除还有什么难度。当然也有 lazy deletion 的形式,不过那是最笨的写法了吧。
        7
    honeyshine75   2018-07-07 08:34:08 +08:00 via Android
    @lcdtyph 不是的,我看到一个选择说把叶子节点删掉之后,再插入一个同样的节点,结果一样,如果调整的话就不一样了
        8
    honeyshine75   2018-07-07 08:34:48 +08:00 via Android
    @ynyounuo 书上都说的是叶子节点直接删,有子树的才调整啊
        9
    honeyshine75   2018-07-07 08:38:35 +08:00 via Android
    @zzj0311 有一个问题,请各位看一下这个题,如果叶子节点删除之后调整了,那么 T1 和 T3 不能保证相同

    http://m.nowcoder.com/questionTerminal?uuid=dda11740572c4059bcb929feca543751
    @ynyounuo
    @zzj0311
    @lcdtyph
        10
    honeyshine75   2018-07-07 08:44:16 +08:00 via Android
    @lovefantasy
    @lcdtyph
    @zzj0311
    @ynyounuo

    谢谢各位,我知道了,对方没说是平衡二叉排序树😅
        11
    liuhaotian   2018-07-07 08:47:12 +08:00 via iPhone
    二叉排序树下 binary search tree
    没有平衡条件
    叶子:直接删 不是叶子要调整
        12
    xlui   2018-07-07 08:49:47 +08:00 via iPhone
    二茬搜索树和平衡二叉树是不一样的,二叉搜索树不考虑失衡情况也不需要旋转。
        13
    honeyshine75   2018-07-07 10:00:42 +08:00 via Android
    @liuhaotian
    @xlui
    谢谢😘😘😘
        14
    chenjian026   2018-07-07 11:40:00 +08:00
    你这是 AVL 树吧 和二叉搜索树 BST 不一样
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4301 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 21ms · UTC 05:58 · PVG 13:58 · LAX 21:58 · JFK 00:58
    ♥ Do have faith in what you're doing.