这是一个创建于 1841 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚刚开始看红黑树，然后画了一下[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