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

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

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

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

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

    学习 avl 树可以串联起很多知识
        9
    linxiaoziruo   272 天前
    各位大佬们,多谢了!工作四五年,从没正儿八经写过这些数据结构,最近在自己重新写,收益颇丰。
        10
    linxiaoziruo   271 天前
    @GuuJiang 大佬,我看到一篇文章,内容是把 2-3 树演化成“红黑树”,但是这里红色和黑色标志的是“链接”,不是“节点”。红黑树还能这么定义的吗?给链接着色生成的红黑树,和给节点着色产生的红黑树都是红黑树吗?还是说给链接着色的红黑树只不过时作者意淫出来的。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4444 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 31ms · UTC 06:19 · PVG 14:19 · LAX 23:19 · JFK 02:19
    ♥ Do have faith in what you're doing.