2回答

liuyubobobo

2019-04-29

已采纳

不知道我是不是没有理解你的问题。第一个if左旋转对应ppt讲的这种情况：

此时，当递归回溯到37节点的时候，满足第一个if，即37的右孩子是42，同时37的左孩子不能为红，就左旋转。（如果是红，37的左右孩子都是红色，做flip color就好了。）

此时，你可以再回顾一下左旋转，理解一下左旋转到底做了什么事情。是的，此时，要纠正42，需要从37的视角去做这个左旋转，旋转后，42是37的根，37变成了42的左孩子。请注意我们左旋转的注释：

//   node                     x    
//  /   \     左旋转         /  \    
// T1   x   --------->   node   T3    
//     / \              /   \    
//    T2 T3            T1   T2    
private Node leftRotate(Node node){    
  
    Node x = node.right;    
    
    // 左旋转    
    node.right = x.left;    
    x.left = node;    
    
    x.color = node.color;    
    node.color = RED;    
    
    return x;    
}

继续加油！：）

0

1

NioCo

谢谢老师 ，我的疑问是这张图，第二个if判断的是第三步，第三个if判断的是第四步，可是第二小步中的if判断难道不是if(isRed(node.left) && isRed(node.left.right) ) 吗？ -------------------------------------------- 我想我大概懂了 ，第一个if判断是递归回溯一次，第二个递归判断是回溯两次的，第三个也是回溯一次的情况，不知道是不是这样理解 ：）

2019-04-29

共1条回复

NioCo

提问者

2019-04-29

谢谢老师 ，我的疑问是这张图，第二个if判断的是第三步，第三个if判断的是第四步，可是第二小步中的if判断难道不是if(isRed(node.left) && isRed(node.left.right) ) 吗？

0

4

枫桥小生

我也是看了几遍，才搞懂这里的左旋转的操作时机。懂了。现在我理解的就是，在2-节点的时候插入一个大于当前节点的值的节点的时候，放在当前节点的右侧，这个时机就已经发生左旋转了。

2021-03-21

共4条回复