这时候还是老规矩,不要嫌弃麻烦,因为只有经历了一步又一步的麻烦之后,你才能牢记那5条规则特征。我们对照之后会发现节点25和节点27是两个连续的红色节点,这时候又破坏了规则4。怎么办呢?那就继续调整就OK了。
难道这时候还要继续往上调整吗?如果你这样做就错了,因为不断地往上调整最后就会把根节点变成了红色,会走进死胡同。我们往下走。
第三步:把节点27变成黑色
来吧,继续重新审查那5条规则特征。很明显节点17和节点25是两个连续的红色,又破坏了。是不是心太累了,调整了这么久,还是没有保证那5条规则,感觉是不是还没有平衡二叉树好。如果你现在有这种感觉,我只能说,希望你继续坚持下去,胜利就在眼前。
第四步:把节点17和节点18都变成黑色节点
来来来,现在你再对照一下那5条规则,是不是完全保证了。写到这真的是太累了,和你读这篇文章的感觉一样一样的,不过这种情况也只是插入情况中的一种。继续往下看:
(1)叔叔节点是黑色:
这种情况下又分了两种情况:
第一种情况:新插入节点为父节点的左孩子
第二种情况:新插入节点为父节点的右孩子