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

[liunaijie]

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

[dploop]

有啥不对呢，没有违反红黑树的所有约束不就好了

[dploop]

不过有些地方还是不对，你插入 3 的时候没有违反红黑树约束为啥要旋转，同理插入 7 的时候也是，执行了很多无用的操作

[liunaijie]

@dploop 在 算法 这本书中是这么写的 把红节点当做 2-3 树中的 3-节点的最小值。也就是说红节点需要在左节点上。我也看了一些其他教程，也有不一样的描述。

[MapHacker]

《算法》中关于红黑树部分的内容我之前也看的很困惑，因为旋转的逻辑和别的地方看到的不太一样，比如 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 这个可视化算法的网站，后来干脆放弃《算法》，转向别的资料了。

[JasperHale]

算法一书上写是 LLRB 左倾红黑树,算是红黑树的一个变体.
左倾红黑树 与 红黑树的区别就是两个红色链接不能连到同一个节点上. 这些在插入 /删除 时的各种反转会简单不少.代码更少更容易看懂. LLRB 的论文 好像就是算法作者写的(实在记不清了). 在算法一书对应的视频中有详细讲解.

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

ps: https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf