红黑树插入的实现

红黑树:

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不存在:进行旋转+变色即可

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

对应的代码如下: