这个时候x被重新赋值为60,因为60是根节点,所以会退出 while 循环。在退出循序后,会再次把根节点设置为黑色,得到最终的结构如下图所示。
最后经过两次执行while循环后,我们的红黑树会调整成现在这样的结构,这样的红黑树结构是平衡的,所以路径的黑高一致,并且没有红色节点相连的情况。
第二种场景 旋转搭配变色来保持平衡
接下来我们再来演示第二种场景,需要结合变色和旋转一起来保持平衡。
给定下面这样一颗红黑树:
现在我们插入节点66,得到如下树结构。
同样地,我们进入fixAfterInsertion(e)方法。