如何证明getBalanceFactor(node.left) >= 0 就是向左子树的左边添加了元素

Answer 1

何时才能成大佬 2019-10-12 20:27:53

对于不平衡条件的证明：

对于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右子树的左边。

Answer 2

liuyubobobo 2019-08-19 03:15:05

因为 getBalanceFactor(node.left) >= 0 的意思就是node的左孩子的左子树高度大于等于右子树的高度。

我们的整棵树初始是平衡的，如果出现这种不平衡，一定是哪里不平衡，我们向哪里添加节点了。在这种情况下，一定是因为向node的左孩子的左子树添加节点了。

继续加油！：）

• 残天一月 #1

  “我们的整棵树初始是平衡的，如果出现这种不平衡，一定是哪里不平衡，我们向哪里添加节点了。在这种情况下，一定是因为向node的左孩子的左子树添加节点了。” 这句话让我恍然大悟，本来没想通为什么=0也要判断，这下知道了！赞！