证明 getBalanceFacter(node)>1 && getBalanceFacter(node.left)>=0就是向node的左子树的左边添加了节点
来源：12-4 旋转操作的基本原理
何时才能成大佬
2019-10-11
对于任意一个节点NODE
如果它是平衡的，那么其必满足下面三种情况之一：
NODE左子树高度-NODE右子树高度=-1
NODE左子树高度-NODE右子树高度=0
NODE左子树高度-NODE右子树高度=1
那么：
假设不平衡的节点node在未插入新节点时左子树的高度为HL，右子树的高度为HR，那么插入新节点之前有以下三种情况：
①HL-HR=-1 (node的左子树低，右子树高)
②HL-HR=0 (node的左子树和右子树高度相同)
③HL-HR=1 (node的左子树低，右子树低)
当添加新节点之后，若node节点不平衡，则有以下情况：
/****情况一、/
一、getBalanceFactor(node)>1 即HL-HR>1
因为node节点之前是平衡的，插入节点后造成了node的不平衡， 所以:插入节点之前HL-HR=1,插入插入节点之后HL-HR=2>1
由HL-HR=1 —> HL-HR=2 只能是HL加了1（HR不可能减1）
所以新添加的节点一定添加到了node的左边
在此情况下，添加新节点后node一定有左节点
假设
node的左节点为node.left
添加节点后
node.left的左子树高度为hL(hL>=0),右子树高度为hR(hR>=0)
/*********************************************************/
(1)getBalanceFactor(node.left)>=0 即hL - hR>=0
又因为node.left是平衡的，所以此时有两种情况：
<1>hL-hR=0
当由hL-hR=-1 -> hL-hR=0 则是因为hL加了1，此时意味着新节点添加在了node.left的左边。
当由hL-hR=0 -> hL-hR=0 则不可能（此时意味着hL和hR都没变，那么node.left的高度也不会变，又因为node.right的高度没改变，且插入新节点之前node是平衡的,所以此时node不可能不平衡。）
当由hL-hR=1 -> hL-hR=0 则不可能（此时意味着hR加了1，但是在添加节点之前hL>hR（hL-hR=1）,添加节点之后hL=hR,所以添加后node.left的高度也不会变( max{hL,hR}+1没变 ),又因为node.right的高度没改变,且插入新节点之前node是平衡的,所以此时node不可能不平衡。）
<2>hL-hR=1
当由hL-hr=-1 --> hL-hR=1 则不可能（插入新节点后hL和hR只能变化一个，且变化的范围为+1、-1、0）
当由hL-hR=0 --> hL-hR=1 则是因为hL加了1，此时意味着新节点添加在了node.left的左边。
当由hL-hR=1 -->hL-hR=1 则不可能（此时意味着hL和hR都没变，那么node.left的高度也不会变，又因为node.right的高度没改变，且插入新节点之前node是平衡的,所以此时node不可能不平衡。）
/*******************************************************************/
由一、（1）中的<1><2>可得，新插入的节点在node的左子树的左边
剩下的情况
一、(2)
二、（1）
二、（2）
还没学，所以还没写，请问bobo老师我这样推导正确吗？
2回答
-
大赞！感谢分享！：）
继续加油！：）
012019-10-11 -
何时才能成大佬
提问者
2019-10-12
对于不平衡条件的证明：
对于node节点不平衡，有四种情况
第一、新节点插入到了node左子树的左边
第二、新节点插入到了node左子树的右边
第三、新节点插入到了node右子树的右边
第四、新节点插入到了node右子树的左边
① getBalanceFactor(node)>=1 && getBalanceFactor(node.left)>=0
（LL）
因为： 插入新节点之后对node节点有
getBalanceFactor(node)>=1
即： node.left.height-node.right-height>=1
综合代码性质，有
node.left.height-node.right-height=2 （1）
因为： 插入新节点之前node节点是平衡的
所以： 插入新节点之前对node节点有
-1<=getBalanceFactor(node)<=1
即： 插入新节点之前对node节点有三种情况
node.left.height-node.right.height=-1 （2）
node.left.height-node.right.height=0 （3）
node.left.height-node.right.height=1 （4）
对于： 插入新节点之前和插入新节点之后
·当node节点由式（2）变为式（1）时，此时该情况不可能出现。
·当node节点由式（3）变为式（1）时，此时该情况不可能出现。
·当node节点由式（4）变为式（1）时，此时必是由于插入新节点后 node.left.height增加了1。故此时插入的新节点必在node节点左子 树中。
故： 新插入的节点必在node左子树中。
因为： 插入新节点之后对node.left节点有
getBalanceFactor(node.left)>=0
即： node.left.left.height-node.left.right.height>=0
因为： 插入新节点之后node.left节点是平衡的
所以： 插入新节点之后对node.left节点有两种情况
node.left.left.height-node.left.right.height=0 （5）
node.left.left.height-node.left.right.height=1 （6）
因为： 插入新节点之前node.left节点也是平衡的
所以： 插入新节点之前对node.left节点有
-1<=getBalanceFactor(node.left)<=1
即： 插入新节点之前对node节点有三种情况
node.left.left.height-node.left.right.height=-1 （7）
node.left.left.height-node.left.right.height=0 （8）
node.left.left.height-node.left.right.height=1 （9）
对于： 插入新节点之前和插入新节点之后
·当node.left节点由式（7）变为式（5）时
此时必是由于插入新节点后node.left.left.height增加了1。
而插入新节点前
node.left.left.height<node.left.right.height
插入新节点前后
node.left.left.height=node.left.right.height
所以插入新节点前后
max(node.left.left.height,node.left.right.height)未改变
所以插入新节点前后node.left.height的高度未改变
则node的平衡因子也未改变
而插入新节点前node是平衡的
故插入新节点之后node也是平衡的
此时node不可能满足条件①
故此时该情况不可能出现
·当node.left节点由式（8）变为式（5）时
此时node.left.left.height 和node.left.right.heigh都未改变
所以node.left的高度也未发生改变
则node的平衡因子也没改变
而node插入新节点之前是平衡的
故插入新节点之后node也是平衡的
此时node不可能满足条件①。
故此时该情况不可能出现。
·当node.left节点由式（9）变为式（5）时
此时必是由于插入新节点后node.left.right.height增加了1
而插入新节点前
node.left.left.height>node.left.right.height
插入新节点前后
node.left.left.height=node.left.right.height
所以插入新节点前后
max(node.left.left.height,node.left.right.height)未改变
所以插入新节点前后node.left.height的高度未改变
则node的平衡因子也未改变
而插入新节点前node是平衡的
故插入新节点之后node也是平衡的
此时node不可能满足条件①
故此时该情况不可能出现
·当node.left节点由式（7）变为式（6）时
此时该情况不可能出现
·当node.left节点由式（8）变为式（6）时
此时必是由于插入新节点后node.left.left.height增加了1
故此时插入的新节点必在node.left的左边
·当node.left节点由式（9）变为式（6）时
此时node.left.left.height 和node.left.right.heigh都未改变
所以node.left的高度也未发生改变
则node的平衡因子也没改变
而node插入新节点之前是平衡的
故插入新节点之后node也是平衡的
此时node不可能满足条件①。
故此时该情况不可能出现。
故： 新插入的节点必在node.left的左边。
综上： 新插入的节点必在node左子树的左边。
②getBalanceFactor(node)>=1 && getBalanceFactor(node.left)<0
（LR）
因为： 同LL
所以： 新插入的节点必在node左子树中
故： 新插入的节点必在node左子树中。
因为： 插入新节点之后对node.left节点有
getBalanceFactor(node.left)<0
即： node.left.left.height-node.left.right.height<0
因为： 插入新节点之后node.left节点是平衡的
所以： 插入新节点之后对node.left节点只有一种情况
node.left.left.height-node.left.right.height=-1 （10）
因为： 插入新节点之前node.left节点也是平衡的
所以： 插入新节点之前对node.left节点有
-1<=getBalanceFactor(node.left)<=1
即： 插入新节点之前对node节点有三种情况
node.left.left.height-node.left.right.height=-1 （11）
node.left.left.height-node.left.right.height=0 （12）
node.left.left.height-node.left.right.height=1 （13）
对于： 插入新节点之前和插入新节点之后
·当node.left节点由式（11）变为式（10）时
此时node.left.left.height 和node.left.right.heigh都未改变
所以node.left的高度也未发生改变
则node的平衡因子也没改变
而node插入新节点之前是平衡的
故插入新节点之后node也是平衡的
此时node不可能满足条件①。
故此时该情况不可能出现。
·当node.left节点由式（12）变为式（10）时
此时必是由于插入新节点后node.left.right.height增加了1
故此时插入的新节点必在node.left的右边
·当node.left节点由式（13）变为式（10）时
此时该情况不可能出现
故： 新插入的节点必在node.left的右边。
综上： 新插入的节点必在node左子树的右边。
③getBalanceFactor(node)<=-1 && getBalanceFactor(node.left)>=0
（RR）
因为： 同LL
综上： 新插入的节点必在node右子树的右边。
④getBalanceFactor(node)<=-1 && getBalanceFactor(node.left)>=0
（RL）
因为： 同LR
综上： 新插入的节点必在node右子树的左边。
312020-02-24
相似问题