3回答

liuyubobobo

2018-07-13

已采纳

课程在这一小节前面部分讲解的PPT，就是举了三个最基础的例子，分别说明了什么时候只需要flipColor（只走最后一个if）；什么时候右旋转以后再flipColor（走最后两个if）；什么时候需要先左旋转，再右旋转，最后flipColor（走三个if），最终，得到了下面的图示：

左旋转以后需要右旋转再flipColor，请再回顾课程中的这个例子（对应视频2：08至4：52）：）

当然，也可以自己动手实验。在我们这一小节的代码上，运行这个测试：（就是上面PPT中描述的情况）

public static void main(String[] args){
    RBTree<Integer, Integer> map = new RBTree<>();
    map.add(42, null);
    map.add(37, null);
    map.add(40, null); // 在插入这个40的时候，三个if都会走
}

为了看到三个if的运行情况，可以在三个if中做相应的打印输出：

if (isRed(node.right) && !isRed(node.left)){
    System.out.println("Add " + key + ", leftRotate");
    node = leftRotate(node);
}
if (isRed(node.left) && isRed(node.left.left)){
    System.out.println("Add " + key + ", rightRotate");
    node = rightRotate(node);
}
if (isRed(node.left) && isRed(node.right)){
    System.out.println("Add " + key + ", flipColors");
    flipColors(node);
}

测试一下，看看是不是会输出这样的结果？

Add 40, leftRotate
Add 40, rightRotate
Add 40, flipColors

在插入40的时候，三个if全都执行了：）

加油！

0

13

fangxingjing

回复

liuyubobobo

理解了，node一层层往上递归的

2019-10-20

共13条回复

丶远走高飞

提问者

2018-07-13

这样看会不会更清晰。 我把第一个if和后两个if做成互斥条件

答案一样。

0

0

丶远走高飞

提问者

2018-07-13

我测试了。。并没有在同一个函数调用

老师看图

0

1

丶远走高飞

很明显 左旋转是在node为37时触发，然后返回值是一个为40的node。但是此时并没有触发下面的条件。 而在node为42时，进行了右旋，然后返回了node40，然后此时又满足颜色反转条件，又进行反转。 所以第一个if的触发后，并不会在同一个函数调用中，又触发另外两个if。只会在向上平衡时，在另外的节点 触发第二个if和第三个if

2018-07-13

共1条回复