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

不懂就问,红黑树的插入过程

  •  
  •   liunaijie · 2019-12-13 18:54:01 +08:00 · 2190 次点击
    这是一个创建于 974 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚刚开始看红黑树,然后画了一下[1,3,5,7,9,2,4,6,8]这个的插入过程 画完后总感觉在插入(2)节点后,(1)节点连接了两个红色节点有点不对。但是把它转换成 2-3 树又感觉没有什么问题。所以发出来向大家请教一下。我画的这个过程对不对呢? 图片地址: https://raw.githubusercontent.com/liunaijie/images/master/20191213184917.png

    5 条回复    2019-12-13 21:35:43 +08:00
    dploop
        1
    dploop  
       2019-12-13 19:00:01 +08:00
    有啥不对呢,没有违反红黑树的所有约束不就好了
    dploop
        2
    dploop  
       2019-12-13 19:04:16 +08:00
    不过有些地方还是不对,你插入 3 的时候没有违反红黑树约束为啥要旋转,同理插入 7 的时候也是,执行了很多无用的操作
    liunaijie
        3
    liunaijie  
    OP
       2019-12-13 20:19:45 +08:00 via Android
    @dploop 在 算法 这本书中是这么写的 把红节点当做 2-3 树中的 3-节点的最小值。也就是说红节点需要在左节点上。我也看了一些其他教程,也有不一样的描述。
    MapHacker
        4
    MapHacker  
       2019-12-13 20:37:39 +08:00
    《算法》中关于红黑树部分的内容我之前也看的很困惑,因为旋转的逻辑和别的地方看到的不太一样,比如 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 这个可视化算法的网站,后来干脆放弃《算法》,转向别的资料了。
    JasperHale
        5
    JasperHale  
       2019-12-13 21:35:43 +08:00
    算法一书上写是 LLRB 左倾红黑树,算是红黑树的一个变体.
    左倾红黑树 与 红黑树的区别就是两个红色链接不能连到同一个节点上. 这些在插入 /删除 时的各种反转会简单不少.代码更少更容易看懂. LLRB 的论文 好像就是算法作者写的(实在记不清了). 在算法一书对应的视频中有详细讲解.

    这是个坑,今年尝试刷一遍算法 /数据结构. LLRB 很快写完了.但是红黑树至今难产.

    ps: https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2453 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 06:57 · PVG 14:57 · LAX 23:57 · JFK 02:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.