7.3.2_2平衡二叉树的删除
平衡二叉树的插入&删除操作：
平衡二叉树具有排序树的特性，即节点值左子树<根节点<右子树(左<中<右)，在二叉排序树的基础上保证每个节点都是平衡的，即每个节点的左右子树的高度之差不超过1
平衡二叉树的删除节点操作和插入操作节点类似，删除之后要满足二叉排序树特性即节点值左<中<右，且要满足平衡特性即删除节点之后某个节点的左右子树的高度之差>1了之后导致不平衡，要和插入节点操作一样去调整平衡
平衡二叉树删除操作步骤：
AVL树删除操作例1：
删除9节点叶子节点=====》不需要调整平衡
步骤1，平衡二叉树删除节点方法和二叉排序树删除节点同，删除是叶子节点9直接删除
步骤2，从删除节点一路向北不断找父节点，看这些节点有没有不平衡情况，没有就完结撒花，什么都不用动。如9节点一路向北先找13,13的平衡因子=0-1=-1平衡，然后25平衡因子=2-1=1平衡，然后50平衡因子=3-4=-1平衡，则均平衡完结撒花。
AVL树删除操作例2：
删除55节点叶子节点=====》需要调整平衡
步骤1，平衡二叉树删除节点方法和二叉排序树删除节点同，删除是叶子节点55直接删除
步骤2，从删除节点一路向北不断找父节点，看这些节点有没有不平衡情况，没有就完结撒花，什么都不用动。如55节点一路向北先找60,60的平衡因子=0-0=0平衡，然后75平衡因子=1-3=-2不平衡需要调整，即75是最小不平衡子树。
步骤3，找到最小平衡子树的下边高度最高的孩子节点，再从高度最高的孩子节点下边找到高度最高的儿子节点(即找到最小平衡子树下边高度最高的孩子和孙子节点)。如75最小平衡子树下边的孩子节点是60和80,60的高度是1,80的高度是3，则找到80节点，80节点下边再找高度最高的孩子节点(即75下边高度最高的孙子节点)，即80下边有77和90孩子节点，77节点高度1,90高度是2，则找到孙子节点90
步骤4，根据孙子位置，调整平衡。如孙子90的位置是75的右孩子80的右子树，即90处于RR位置，RR位置调整平衡让儿子80左单旋，即让80代替75成为根节点，75成为80的左子树，80的左子树77成为75的右子树，其他不变
步骤5，因为步骤4调整了平衡即改变了高度，则可能会导致该旋转节点的上层祖先父节点高度改变导致不平衡，则不平衡向上传递，所以要再看下该旋转节点80的其他祖先节点有没有不平衡，没有则完结撒花（应该是这样的。。。。。），个人理解就看调整旋转后的节点还没有其他父节点或祖先节点，如果有就把这些父节点或祖先节点的平衡因子计算一遍，不平衡再回到步骤2走一遍，没有就别计算了直接over
AVL树删除操作例3：
删除32节点叶子节点=====》需要调整平衡
步骤1，平衡二叉树删除节点方法和二叉排序树删除节点同，删除是叶子节点32直接删除
步骤2，从删除节点一路向北不断找父节点，看这些节点有没有不平衡情况，没有就完结撒花，什么都不用动。如32节点一路向北找父节点先找17,17的平衡因子=0-0=0平衡，然后44平衡因子=1-3=-2不平衡需要调整，即44是最小不平衡子树。
步骤3，找到最小平衡子树的下边高度最高的孩子节点，再从高度最高的孩子节点下边找到高度最高的儿子节点(即找到最小平衡子树下边高度最高的孩子和孙子节点)。如44最小平衡子树下边的孩子节点是17和78,17的高度是1,78的高度是3，则找到78节点，78节点下边再找高度最高的孩子节点(即44下边高度最高的孙子节点)，即78下边有50和88孩子节点，50节点高度2,88高度是1，则找到孙子节点50
步骤4，根据孙子相对于最小平衡子树节点的位置，调整平衡。如孙子50的位置是44的右孩子78的左子树，即50处于RL位置，RL位置调整平衡让孙子先右旋再左旋。即让50右单旋代替78成为根节点，78成为50的右子树，50的右子树62成为78的左子树，其他不变，再让50左旋代替44成为根节点，44成为50左子树，50的左子树成为44的右子树，简易版是50成为根节点，78是50的右子树，44是50的左子树，50的右子树成为78的左子树，50的左子树成为44的右子树，调整结束。
步骤5，因为步骤4调整了平衡即改变了高度，则可能会导致该旋转节点的上层祖先父节点高度改变导致不平衡，则不平衡向上传递，所以要再看下该旋转节点50的其他祖先节点有没有不平衡，没有则完结撒花（应该是这样的。。。。。，不行就都大概计算一遍平衡因子，应该好计算），个人理解是现在调整的节点50上边没有比它还祖先的节点，那自然不可能再不平衡传导了吧，所以不用看
AVL树删除操作例4：
删除32节点叶子节点=====》需要调整平衡
步骤1，平衡二叉树删除节点方法和二叉排序树删除节点同，删除是叶子节点32直接删除
步骤2，从删除节点一路向北不断找父节点，看这些节点有没有不平衡情况，没有就完结撒花，什么都不用动。如32节点一路向北找父节点先找17,然后17平衡因子=0-0=0平衡，再找44平衡因子=1-3=-2不平衡需要调整，即44是最小不平衡子树。
步骤3，步骤4和例子3同
步骤5，因为步骤4调整了平衡即改变了高度，(个人理解现在50上边还有个祖先节点33，就看33平衡不平衡吧)即祖先节点33的右孩子节点高度从4变成了3，则可能会导致该旋转节点的上层祖先父节点高度改变导致不平衡，则不平衡向上传递，所以要再看下该旋转节点50的其他祖先节点有没有不平衡，没有则完结撒花。50的祖先33平衡因子=5-3=2不平衡，则不平衡向上传导，则重新回到步骤2、步骤3、步骤4、步骤5，从刚才已经调整好的子树的根节点出发一路向北找到最小不平衡子树，即从50出发，先找33的平衡因子=5-3=2不平衡，即33是最小不平衡子树
重新回到步骤3，找高度最高的儿子和孙子。10和50是33的孩子节点，10高度最高为4，再从10找高度最高的孩子节点，5和20是10的孩子节点，20高度最高为4，则高度最高的孙子节点是20
重新回到步骤4，根据孙子相对于最小平衡子树节点的位置，调整平衡。20是33的左孩子10的右子树即20在LR位置，则开始跟例子3类似，进行孙子先左旋再右旋。简易版，孙子20左旋代替10成为根节点，10成为20左子树，20的左子树15成为10的右子树，20右旋代替33成为根节点，33成为20右子树，20的右子树25成为33的左子树，调整结束。
重新回到步骤5，因为步骤4调整了平衡即改变了高度，看看还有没有不平衡向上传导。个人理解现在20变成了根节点，已经再没有比20更祖先的节点了，所以无论怎样也不平衡传导不了了，所以肯定没有不平衡向上传导，至此结束。
AVL树删除操作例5：
删除75节点有2个子树，=====》需要调整平衡
在二叉排序树中找二叉排序树的某个节点的前驱，从该节点开始的左孩子出发一路往右往右下走到头的节点即可
步骤1，平衡二叉树删除节点方法和二叉排序树删除节点同，删除是有2个子树节点75，则用前驱或后继节点进行顶替，假设用75的前驱节点，先找75的前驱节点则从左孩子60出发，往60的右下找找到头，此时60的右下节点是null，则60节点就是75的前驱，则把60的数据复制到75所在位置，注意是复制，此时相当于有2份60的位置，一份75位置上的一份它本身60位置上的。然后又转换为删除前驱节点60节点的数据，即实际删除的是前驱节点60位置上的数据而不是75的数据。又转到步骤1相当于情况2，此时60节点下边只有一个子树55，则用子树55代替60的位置，注意此时是顶替不是复制，不是说把55位置上的数据复制到60位置上，而是把55节点的数据直接挂到以前节点值是75现在节点值是60位置上的左指针，然后让60位置上60的数据直接释放，注意此时删除的节点实际上是75的前驱节点60的位置上的数据，不是75也不是55，实际上删除的是60位置上的节点。。。。。。。。
步骤2，从删除节点一路向北不断找父节点，看这些节点有没有不平衡情况，没有就完结撒花，什么都不用动。实际删除的是前驱节点60节点(即现在55的位置)则要从55一路向北找父节点先找60,然后60平衡因子=1-3=-2不平衡需要调整，即60是最小不平衡子树。
步骤3，到最小平衡子树的下边高度最高的孩子节点，再从高度最高的孩子节点下边找到高度最高的儿子节点(即找到最小平衡子树下边高度最高的孩子和孙子节点)。如60最小平衡子树下边的孩子节点是55和80,55的高度是1,80的高度是3，则找到80节点，80节点下边再找高度最高的孩子节点(即60下边高度最高的孙子节点)，即80下边有77和90孩子节点，77节点高度1,90高度是2，则找到孙子节点90
步骤4，根据孙子相对于最小平衡子树节点的位置，调整平衡。如孙子90的位置是60的右孩子80的右子树，即50处于RR位置，RR位置调整平衡让儿子左单旋。即让80左单旋代替60成为根节点，60成为80的左子树，80的左子树77成为60的右子树，其他不变，调整结束。
步骤5，因为步骤4调整了平衡即改变了高度，个人理解现在旋转节点80上边还有个祖先节点50，就看50平衡不平衡吧，50的平衡因子=3-3=0平衡，则未出现不平衡向上传递，则完结撒花。
AVL树删除操作例6：
删除75节点有2个子树，=====》需要调整平衡
在二叉排序树中找二叉排序树的某个节点的后继，从该节点开始的右孩子出发一路往左往左下走到头的节点即可
步骤1，平衡二叉树删除节点方法和二叉排序树删除节点同，删除是有2个子树节点75，则用前驱或后继节点进行顶替，假设用75的后继节点，先找75的后继节点则从右孩子80出发，往80的左下找找到头可知是77，则77节点就是75的后继，则把后继节点77的数据复制到75所在位置，注意是复制，此时相当于有2份77位置上的数据，一份75位置上的一份它本身77位置上的。然后又转换为删除后继节点77位置上的数据，又转到步骤1相当于情况1，此时77节点下边没有子树即叶子节点，叶子节点直接删除，即直接释放77位置上的节点数据，注意此时删除的节点实际上是75的后继节点77的位置，不再是是75。。。。。。。。
步骤2，从删除节点一路向北不断找父节点，看这些节点有没有不平衡情况，没有就完结撒花，什么都不用动。实际删除的节点77(即现在77左孩子为空的位置)，则要从77左孩子为空的位置一路向北找父节点先找80,然后80平衡因子=0-2=-2不平衡需要调整，即80是最小不平衡子树。
步骤3，到最小平衡子树的下边高度最高的孩子节点，再从高度最高的孩子节点下边找到高度最高的儿子节点(即找到最小平衡子树下边高度最高的孩子和孙子节点)。如80最小平衡子树下边的孩子节点是90,则只能找到90节点，90节点下边再找高度最高的孩子节点(即80下边高度最高的孙子节点)，即90下边有85和95孩子节点，85节点高度1,95高度是1，俩高度相同则选哪个节点当孙子都行，假设选95节点的当做孙子节点，则找到孙子节点95
步骤4，根据孙子相对于最小平衡子树节点的位置，调整平衡。如孙子95的位置是80的右孩子90的右子树，即95处于RR位置，RR位置调整平衡让儿子左单旋。即让90左单旋代替80成为根节点，80成为90的左子树，90的左子树85成为80的右子树，其他不变，调整结束。
步骤5，因为步骤4调整了平衡即改变了高度，个人理解现在旋转节点90上边还有个祖先节点77和50，就看77、50平衡不平衡吧，77的平衡因子=2-3=-1平衡，50的平衡因子=3-4=-1平衡，则未出现不平衡向上传递，则完结撒花。
假设在步骤3中选择85节点做孙子节点，即在步骤3中儿子节点是90，孙子节点是85
2-步骤4，根据孙子相对于最小平衡子树节点的位置，调整平衡。如孙子85的位置是80的右孩子90的左子树，即85处于RL位置，RL位置调整平衡让孙子先右单旋再左单旋。即让85右单旋代替90成为根节点，90成为85的右子树，85的右子树成为90的左子树，85的右子树为空，再让85左单旋代替80成为根节点，80成为85的左子树，85的左子树(实际没有)成为80的右子树，其他不变，调整结束。
2-步骤5，因为步骤4调整了平衡即改变了高度，个人理解现在旋转节点85上边还有个祖先节点77和50，就看77、50平衡不平衡吧，77的平衡因子=2-3=-1平衡，50的平衡因子=3-4=-1平衡，则未出现不平衡向上传递，则完结撒花。
知识回顾：
这样记录真的有意义吗。。。。。。。。。。。。。。
