红黑树插入的实现

红黑树：

1.概念：

红黑树的性质：

红黑树的插入操作：

其前面的插入和二叉搜索树的一模一样，只是后面需要判断是否满足红黑树的性质：

具体分为三种情况：

1.uncle节点存在且为红色的：

对应如图：

这种情况只需要将parent和uncle节点都弄成黑色，对应的grandparent节点弄成黑色

接下来又会分为三种情况：

• 1.如果对应的grandparent就是根节点，那么只需要将根节点再弄成黑色即可

• 2.如果对应的grandparent的父亲是黑色节点，则直接结束即可

• 3.如果对应的grandparent的父亲是红色节点，则需要将cur = grandparent,再次进行循环

2.uncle节点存在且为黑：

第一种情况：

对应的这种情况，对应的需要旋转+变色：

可以看出左边的长度长，所以进行右旋：

这里的右旋与AVL数的完全相同：

右旋之后就得到下图：

再将parent变为黑，grandparent变为红

是满足红黑树条件的。

第二种情况：

对应这种情况需要先想左旋在向右旋：

同样与AVL树完全相同：

左旋是以p为节点，右旋的时候以g为节点

再将cur变为黑，grandparent变为红

对应的结果如下：

还有另外两种情况对应的是 parent == grandparent -> right

这又会分为两种情况，

分别进行左旋或者右左双旋，再将parent/cur变为黑，grandparent变为红即可。

3.uncle不存在：

对应的情况如下：

第一种情况：

只需要进行一次右旋再将parent变为黑，grandparent变为红即可：

第二种情况：

需要进行左右双旋，再将再将cur变为黑，grandparent变为红：

还有另外两种情况对应的是 parent == grandparent -> right

这又会分为两种情况，

分别进行左旋或者右左双旋，再将parent/cur变为黑，grandparent变为红即可。

通过分析之后，发现uncle节点存在且为黑和uncle节点不存在可以和为一种情况：

所以，一共有两大种情况：

1.uncle存在且为红：进行变色+循环即可

2.uncle存在且为黑/uncle不存在：进行旋转+变色即可

这里的代码其实不是关键。关键是思想

对应的代码如下：