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

为什么说 AVL 树是严格平衡的,而红黑树不是严格平衡的

  •  
  •   linxiaoziruo · 2019-01-15 11:43:14 +08:00 · 2598 次点击
    这是一个创建于 2137 天前的主题,其中的信息可能已经有所发展或是发生改变。

    为什么说 AVL 树是严格平衡的,而红黑树不是严格平衡的?红黑树经过旋转不也是平衡树吗?怎么还说红黑树不是严格平衡的呢?

    10 条回复    2019-01-16 14:49:08 +08:00
    lttzzlll
        1
    lttzzlll  
       2019-01-15 12:36:12 +08:00 via Android
    严格平衡的定义 任意左右子树高度差不超过 1。其余都是非严格平衡。
    lttzzlll
        2
    lttzzlll  
       2019-01-15 12:39:49 +08:00 via Android
    叶节点,非任意。
    yidinghe
        3
    yidinghe  
       2019-01-15 13:05:49 +08:00
    红黑树是根据自己那套规则来判断要不要旋转,旋转完之后即使没有达到严格平衡,只要符合规则就处理结束了。这是在执行效率方面所做的取舍。
    linxiaoziruo
        4
    linxiaoziruo  
    OP
       2019-01-15 13:44:21 +08:00
    @lttzzlll 没明白你的意思。平衡树的定义不就是“任意左右子树高度差不超过 1 ”吗?
    linxiaoziruo
        5
    linxiaoziruo  
    OP
       2019-01-15 13:45:08 +08:00
    @linxiaoziruo 红黑树是平衡树的一种。什么才是严格平衡呢?红黑树又为什么不是严格平衡呢?
    GuuJiang
        6
    GuuJiang  
       2019-01-15 14:14:06 +08:00 via iPhone
    这个在红黑树的定义里已经写得很清楚了吧,红黑树的平衡只是保证了各子树的黑高度相等,而由黑高度的定义可以看出最坏情况下最高子树的高度是最低子树高度的两倍
    linxiaoziruo
        7
    linxiaoziruo  
    OP
       2019-01-15 15:43:17 +08:00
    @GuuJiang 弄明白了。红黑树不是平衡树,只是接近平衡树。
    mortonnex
        8
    mortonnex  
       2019-01-15 16:00:28 +08:00
    建议楼主顺便了解下:
    1.hashmap 中红黑树的使用
    2.MySQL 中索引为什么要用 B+树

    学习 avl 树可以串联起很多知识
    linxiaoziruo
        9
    linxiaoziruo  
    OP
       2019-01-15 17:07:08 +08:00
    各位大佬们,多谢了!工作四五年,从没正儿八经写过这些数据结构,最近在自己重新写,收益颇丰。
    linxiaoziruo
        10
    linxiaoziruo  
    OP
       2019-01-16 14:49:08 +08:00
    @GuuJiang 大佬,我看到一篇文章,内容是把 2-3 树演化成“红黑树”,但是这里红色和黑色标志的是“链接”,不是“节点”。红黑树还能这么定义的吗?给链接着色生成的红黑树,和给节点着色产生的红黑树都是红黑树吗?还是说给链接着色的红黑树只不过时作者意淫出来的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1020 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 19:57 · PVG 03:57 · LAX 11:57 · JFK 14:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.