关于左旋转和右旋转的条件判断问题
来源：12-5 左旋转和右旋转的实现
伟少_will
2018-05-24
老师, 我有一个疑问被弄晕了
当进行左旋的时候要进行if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)的判断
其实balanceFactor = 2的时候, 就需要进行左旋了, 不会等到balanceFactor = 3 或者 = 4
第一个问题: 是否可以把判断写成if(balanceFactor == 2 && getBalanceFator(node.left) == 1)呢
那么如果balanceFactor = 2的时候必须进行左旋, 问题又来了, 第二个判断条件根本不会触发
第二个问题:是否可以把判断直接简写写成if(balanceFactor == 2)呢
晕了.
1回答
-
赞！非常非常好的问题。
对于第一个问题，其实课程中的介绍，字里行间我已经透露出来了：）你说的非常对，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 的情况：）
722018-11-13
相似问题