红黑树维持平衡问题

Question

老师在讲  在红黑树中添加一个元素时， 用了3个if 来进行平衡的维持

并且说 这3个if 不是互斥的、

我仔细想了想，我始终觉得在左倾红黑树下，当第一个if满足时，即首先左旋转，后面的两个if条件是不会满足的。在当前node下。

所以，特来请教老师。

Answer 1

liuyubobobo 2018-07-13 00:36:39

课程在这一小节前面部分讲解的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全都执行了：）

加油！

• 提问者 丶远走高飞 #1

  老师 我能懂你这个意思。我是想表达在一个node下 是不会出现第一个if 和后面几个同时出发的

• 提问者 丶远走高飞 #2

  比如在 node为37的时候触发的是左旋转，但是其他两个并没有触发。
  而在node为42的时候，才触发了后两个。
  是这样的吧老师
  所以我想表达的观点 在于同一个node下

• 提问者 丶远走高飞 #3

  确实在一个树中插入一个元素，肯定会存在三个都触发。
  而 对于一个node来说，即这个node是要做平衡操作的node，即在if判断条件中的node。是不会在触发第一个if的情况下，又触发第二个if和第三个if。

点开查看后面10条评论

Answer 2

提问者 丶远走高飞 2018-07-13 09:24:28

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

答案一样。

Answer 3

提问者 丶远走高飞 2018-07-13 09:18:33

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

老师看图

• 提问者 丶远走高飞 #1

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