关于老师对于LR先对X左旋转转化成了LL的说法

Question

当对X进行左旋转后，新的y的以Z为根节点的左子树有可能是不平衡的，这就打破了对Y进行右旋转的初始条件，但是我发现最后对于Y进行右旋转的结果的确是满足平衡的，所以我认为在这里不能说是先转换成了LL的情况而应该说将两个步骤合在一起最终使LR的情况达到平衡，不知道老师对于我的这种思考怎么看呢

Answer 1

提问者 changpeku 2020-08-06 16:44:28

就是这里，老师

Answer 2

liuyubobobo 2020-08-06 15:24:54

我不确定我是不是完全理解了你的问题。

你画的图示，第一排对于 x 进行左旋转，关键在于这根本不满足左旋转的条件。因为此时 x 的左右子树相差为 1，因此 x 本身是平衡的，不需要左旋转。

继续加油！：）

• 提问者 changpeku #1

  第一排的那个是第二排的左子树，我只是为了方便所以提取出来了，完全是老师您在LR里面讲到的步骤，意即先对X(Y.left)进行左旋转，但是在条件里只有getBalanceFactor(node)>1&&getBalanceFactor(node.left)<0,所以我就画了这张图，对X进行左旋转后以Z为根节点的左子树有可能不平衡额

• liuyubobobo 回复 提问者 changpeku #2

  在我的将的例子里，大前提是 y 为根节点的子树不平衡，为了调节这个 y 的不平衡，我们要做两步，表现在代码里是这样的：
  
  if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
      node.left = leftRotate(node.left);
      return rightRotate(node);
  }
  
  这两步合在一起，调节了 y 的不平衡。
  
  是的，只是做一个 x 的左旋转以后，z 就不是平衡，因为之后转化成了 LL，LL 就是不平衡的，所以还需要第二步。这两步不能割裂来看。

• 提问者 changpeku 回复 liuyubobobo #3

  是的，但是转化正常的LL是以Y为旋转节点(因为是Y不平衡)，也就是说本来应该Z是平衡的吧，不过在这里通过两步的确使整棵树达到了平衡，但我觉得这样就不能说成转化成LL的说法了

点开查看后面9条评论