关于左旋转和右旋转的条件判断问题

Question

老师, 我有一个疑问被弄晕了

当进行左旋的时候要进行if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)的判断

其实balanceFactor = 2的时候, 就需要进行左旋了, 不会等到balanceFactor = 3 或者 = 4

第一个问题: 是否可以把判断写成if(balanceFactor == 2 && getBalanceFator(node.left) == 1)呢

那么如果balanceFactor = 2的时候必须进行左旋, 问题又来了, 第二个判断条件根本不会触发

第二个问题:是否可以把判断直接简写写成if(balanceFactor == 2)呢

晕了.

Answer 1

liuyubobobo 2018-05-24 21:30:13

赞！非常非常好的问题。

对于第一个问题，其实课程中的介绍，字里行间我已经透露出来了：）你说的非常对，balanceFactor > 1的时候，其实只可能为2。因为我们每次只添加一个节点，子树的高度只可能增加1，平衡因子的变化也只可能有1的变化。因此，在不平衡的情况下，只可能从1变成2（或者对称的，balanceFactor < -1的时候，只可能从-1变成-2）：）

对于第2个问题，首先，由于问题1中解释的原因，你的猜想也是对的。我们可以把判断条件写成if(balanceFactor == 2 && getBalanceFator(node.left) == 1) 但是仅限于add的情况，对于remove的情况，再向上回溯的过程中，有可能出现 getBalanceFator(node.left) == 0 的情况，在这里，为了代码的统一，我的风格是写成了 if(balanceFactor == 2 && getBalanceFator(node.left) >= 0)

但是，我们不能写成if(balanceFactor == 2)，这个问题问的还有点儿早，在下一小节，你就会看到讲解balanceFactor == 2 但是getBalanceFator(node.left) == -1 的情况：）

• 提问者 伟少_will #1

  谢谢老师, 我真的问早了, 果然下一章就解决了我的疑惑

• ITdoge #2

  是的，不写等于可以