红黑树新增操作的详解

红黑树的新增操作动画详解

红黑树二叉查找树：满足以下特点：

因为是完美的黑色平衡二叉查找树，类似于AVL的平衡因子，避免出现下图的情况：

第一种情况：没有父节点P
如果新增节点C没有P节点，那么它就是根节点，就直接变色为black【性质2】
为什么插入的节点默认为red呢？
因为红黑树是完美的黑色平衡二叉查找树，如果默认为black，就可能会打破这种平衡：
第二种情况：有父节点P且颜色为black：
那就新增节点C颜色为red【因为不影响平衡，就直接增加】
当父节点P为红色是才会去考虑Uncle节点
第三种情况P为red且U节点为red：

关于递归处理，我们看完第四种情况，一块来验证
第四种情况:P为red,U为black或者为Nil
因为三角关系最后还要转化为直线的情况，我们先看三角关系


注意此时时CPG组成的三角关系！！！
以C为圆心，旋转P


三点一线情况处理：

以P为圆心旋转G,之后P,G变色

让我们看一下动态的演示：

我们新增节点为C:0057，其P:0058节点为red,U节点为Nil,符合第四种情况的三角关系：
首先：以C为圆点，旋转P:

然后变成了三点一线关系：此时P:0057,C:0058
以P为圆心，旋转G:0043，然后P，G变色：

现在我们来看一下第三种的递归处理
我新增C:0059节点,其父节点P:0058为red,U节点：0043为red,为第三种情况：

首先P,U,G变色：


我们把G:0057作为新增节点C:0057,其P:0015,U:0005,G:0008
我们发现P为red,U为black,其次C,P,G三点一线，
第一步：以P为圆点，旋转G:

我们发现两个red节点相邻【不满足性质4，同时0015节点为根节点必须为black】要变色！！0015变为black,0008变为red(因为行数限制，没办法上图了)可以通过下面的网址来进行动态验证红黑树【观看粉菜学院视频自己整理总结】
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html