前一篇文章就描述的2-3树的结构特性和添加元素的操作：

https://blog.****.net/qq_41723615/article/details/89408056

下面利用2-3树来理解红黑树：

 

一、颜色翻转和右旋转：

 

红黑树添加新元素：（颜色翻转）flipColors

1.首先向空的红黑树添加一个元素42，让它变为黑色。

2.添加一个新的节点37，直接添加在左子节点位置上即可：

3.如果要添加的位置在右子节点上呢？例如红黑树有一个黑色根节点37，需要在右子节点上添加一个节点42：

此时就需要进行左旋转了：

这种操作在2-3树中相当于把一个新的节点放在二节点中。

4.向红黑树中的“3-node”添加元素：

向红黑树添加节点66：

此时应该添加到右孩子中：

这种情况在2-3树种相当于37 42 66都是融合在一起的。可以理解为2-3树的临时的4节点：

这种情况对应在红黑树就相当于三个2节点都是黑色的节点，并且节点不需要旋转，将42所处的节点位置分裂而成的两个子节点37 66变为黑色即可：每个黑节点的左侧如果没有红色节点则表示该黑色节点为单独的2节点。

此时的根节点在2-3树中又要和它的父亲节点进行融合变为新的根节点，相当于把42节点变为红色：

此时可以发现42与它的子节点颜色进行翻转。

 

5.添加12的操作：

结果：

这种情况在2-3树类似于：

此时就需要进行右旋转了：

1.为根节点与左孩子添加右孩子，方便理解：

2.进行node.left = T1

3.接着让x.right = node

4.此时需要维护颜色信息：x.color = node.color

5.此时的12 37 42对应到2-3树还是临时4节点，所以需要进行node.color = RED

此时就完成了红黑树的右旋转过程：

 

 

 

 

 

温馨提示

关注我的公众号【Java剑主】，学习更多有深度的技术文章。本博客不在记录原创博文，请移步公众号获取最新内容。

修道注重根基，熟透原理方能看透事物本质，编程亦如此！ Java修炼之道，道心坚不移！踏剑寻梦，不忘初心！