关于红黑树的插入结点问题
来源：13-7 红黑树中添加新元素
Yan雪杉
2019-06-07
老师，算法导论上这本书上说，每插入一个几点，五条性质里面必定只会违反一条性质，那么我是不是就可以把如下代码
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);
`
写回答
1回答
-
liuyubobobo
2019-06-08
不可以。
因为在 isRed(node.right) && !isRed(node.left) 的情况下，不是左旋转一下就结束了。
需要先左旋转；再右旋转；再颜色翻转；
在 isRed(node.left) && isRed(node.left.left) 的情况下，不是右旋转一下就结束了。
需要先右旋转；再颜色翻转；
只有 isRed(node.left) && isRed(node.right) 的情况下，是颜色翻转一下就结束了。
你修改的逻辑和我本来的代码逻辑是不等价的，请体会一下。
也可以再仔细理解一下这页PPT：
继续加油！：）
022019-07-26
相似问题