上面我们看到了旋转一棵树要进行怎么样的旋转,接下来我们讨论如何插入一个新节点(利用旋转和颜色规则来保持树的平衡)
Ⅳ、节点的插入在我们向下查找插入点的时候我们主要讨论一下三个方面
下行途中的颜色变化
向下路途上的旋转
插入节点后的旋转
① 下行途中的颜色变化首先我们讨论下行途中的颜色变化查找的方式和普通的二叉搜索树是一样的,只是在下行的途中会涉及到颜色的变化,规则如下:每当遇到一个有两个红色子节点的黑色节点时,它必须把子节点变为黑色,把父节点变为红色(除非父节点为根节点),如下图就进行了一次颜色变换
上图中进行颜色变化没有改变从根向下过P到叶节点或空子节点路径上的黑色节点的数目因此颜色变换并没有违反规则4,这样变化的好处是在不违背规则3的情况下连接新的红色节点更容易。上面颜色变化虽然不会违背规则4但是有可能违背规则3,若上图中P节点的父节点是红色,那么变换之后就违背了规则3,那么此时就会对树进行旋转操作,
② 在向下的路径上的旋转向下路径上的旋转有两种可能性,当违背的节点是外侧的子孙节点“违背规则的节点”是指在造成红红冲突的父子节点对中的子节点,我们从50开始创建一棵新树插入以下节点:25,75,12,37,6和18在插入12和6的时候需要做颜色变换。接下来我们要插入节点3,必须对节点12以及它的子节点6和18做颜色变换,此时生成的树就是下图中的a树,此时节点25和12违背了红黑树规则3,此时需要对此树进行旋转的操作,
这里我们设刚刚进行颜色变换的三角形的顶点为X,X的父节点为p,祖父节点为G,此时我们对上图中的a进行如下的颜色变化和旋转:
改变X的祖父节点P的颜色(本例中旋转后还必须要改变根的颜色)
改变X父节点P的颜色
以X的祖父节点G为顶旋转,向X上升的方向旋转
这样 就满足了红-黑树的颜色规则,树就成为了一棵平衡树,此时就能很容易地插入节点3,插入之后如上图中的b图所示。
若插入的是内侧的子孙节点,此时我们以根为50,插入25,75,12,37,31和43.在插入12和31之前需要颜色变换,然后新插入节点28,向下查找插入点的时候,在37节点的时候需要执行颜色变换,变换后如下图的a树所示,变换后25和37都是红色需要进行旋转操作,此时颜色变换三角形的顶点X为37,P为25,G为50,执行以下四步使树从新平衡
改变G的颜色
改变X的颜色
以P为顶旋转向X上升的方向旋转,旋转结果如下图b所示
以G为顶旋转,X上升方向旋转,旋转后即可轻松插入节点28
③ 插入节点之后的旋转接下来我们讨论插入节点之后的旋转,这里我们讨论插入的节点为X,其父节点为P,祖父节点为G。1.若节点X在P的一侧与P在G的一侧相同,则X就是一个外侧的子孙节点(a,d),反之若不相同则X是一个内侧子孙节点(b,c)。下图显示了”指向“左右变化的多样性
为恢复红黑规则所执行的操作是由X和它的亲属所决定的,节点只以三种当时排列(上面的指向变换不算在内)
P是黑色的。
P是红色的,X是G的一个外侧子孙节点
P是红色的X是G的一个内侧的子孙节点,如下图所示