这是一个创建于 2133 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚刚开始看红黑树，然后画了一下[1,3,5,7,9,2,4,6,8]这个的插入过程 画完后总感觉在插入(2)节点后，(1)节点连接了两个红色节点有点不对。但是把它转换成 2-3 树又感觉没有什么问题。所以发出来向大家请教一下。我画的这个过程对不对呢？ 图片地址： https://raw.githubusercontent.com/liunaijie/images/master/20191213184917.png
 | 1 dploop 2019-12-13 19:00:01 +08:00 有啥不对呢，没有违反红黑树的所有约束不就好了 |
| 2 dploop 2019-12-13 19:04:16 +08:00 不过有些地方还是不对，你插入 3 的时候没有违反红黑树约束为啥要旋转，同理插入 7 的时候也是，执行了很多无用的操作 |
 | 3 liunaijie OP @dploop 在 算法 这本书中是这么写的 把红节点当做 2-3 树中的 3-节点的最小值。也就是说红节点需要在左节点上。我也看了一些其他教程，也有不一样的描述。 |
 | 4 MapHacker 2019-12-13 20:37:39 +08:00 《算法》中关于红黑树部分的内容我之前也看的很困惑，因为旋转的逻辑和别的地方看到的不太一样，比如 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 这个可视化算法的网站，后来干脆放弃《算法》，转向别的资料了。 |
 | 5 JasperHale 2019-12-13 21:35:43 +08:00 算法一书上写是 LLRB 左倾红黑树,算是红黑树的一个变体. 左倾红黑树 与 红黑树的区别就是两个红色链接不能连到同一个节点上. 这些在插入 /删除 时的各种反转会简单不少.代码更少更容易看懂. LLRB 的论文 好像就是算法作者写的(实在记不清了). 在算法一书对应的视频中有详细讲解. 这是个坑,今年尝试刷一遍算法 /数据结构. LLRB 很快写完了.但是红黑树至今难产. ps: https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf |
Select Language