关于红黑树的插入结点问题

Question

老师，算法导论上这本书上说，每插入一个几点，五条性质里面必定只会违反一条性质，那么我是不是就可以把如下代码

		 if (isRed(node.right) && !isRed(node.left))
	            node = leftRotate(node);

        if (isRed(node.left) && isRed(node.left.left))
            node = rightRotate(node);

        if (isRed(node.left) && isRed(node.right))
            flipColors(node);
        `

换成

		if (isRed(node.right) && !isRed(node.left))
	            node = leftRotate(node);
        else if (isRed(node.left) && isRed(node.left.left))
            node = rightRotate(node);
        else if (isRed(node.left) && isRed(node.right))
            flipColors(node);
        `

Answer 1

liuyubobobo 2019-06-08 00:42:35

不可以。

因为在 isRed(node.right) && !isRed(node.left) 的情况下，不是左旋转一下就结束了。

需要先左旋转；再右旋转；再颜色翻转；

在 isRed(node.left) && isRed(node.left.left) 的情况下，不是右旋转一下就结束了。

需要先右旋转；再颜色翻转；

只有 isRed(node.left) && isRed(node.right) 的情况下，是颜色翻转一下就结束了。

你修改的逻辑和我本来的代码逻辑是不等价的，请体会一下。

也可以再仔细理解一下这页PPT：

继续加油！：）

• 无心铁憨憨 #1

  3个if条件不是互斥的，最极端的情况是3个if都会进入，我的理解是相当于由LR转为LL，再右旋转，最后颜色反转，当然，不是标准的LR，类似于这种情况

• liuyubobobo 回复 无心铁憨憨 #2

  你理解的完全正确：）