平衡二叉树的删除

删除结点后，要保持二叉排序树的特性不变(左<中<右)

若删除结点导致不平衡，则需要调整平衡

平衡二叉树的删除步骤

1. 删除结点(方法同"二叉排序树")
2. 一路向北找到最小不平衡子树，若没有找到，则不需要进行调整平衡
3. 找最小不平衡树下，“个头”最高的儿子、孙子
4. 根据孙子的位置，调整平衡(LL/RR/LR/RL)
5. 如果不平衡向上传导，继续2

AVL树删除操作——例1：删除9结点

1、寻找最小不平衡子树

2、没找到最小不平衡子树，结束查询

AVL树删除操作——例2：删除55结点 

1、删除结点55

2、寻找最小不平衡子树

3、找最小不平衡树下，“个头”最高的儿子、孙子

 4、根据孙子的位置，调整平衡(LL/RR/LR/RL)

 

5、检查不平衡性是否向上传导 

AVL树删除操作——例3：删除32结点  

1、删除结点

2、寻找最小不平衡子树

3、找最小不平衡树下，“个头”最高的儿子、孙子

 

 4、根据孙子的位置，调整平衡(LL/RR/LR/RL) 

 

 

5、检查不平衡性是否向上传导 

 AVL树删除操作——例4：删除32结点  

1、删除结点

2、寻找最小不平衡子树

3、找最小不平衡树下，“个头”最高的儿子、孙子

 4、根据孙子的位置，调整平衡(LL/RR/LR/RL) 

 

5、检查不平衡性是否向上传导 ,检查出来不平衡，继续2

 

 

 

 

 AVL树删除操作——例5：删除75结点   

1、删除结点（这里用前驱顶替）

 

 

2、寻找最小不平衡子树

3、找最小不平衡树下，“个头”最高的儿子、孙子

4、调整平衡

5、检查不平衡性是否向上传导

 AVL树删除操作——例5：删除75结点   

1、删除结点（这里用后继顶替）

 

2、寻找最小不平衡子树

3、找最小不平衡树下，“个头”最高的儿子、孙子

4.调整平衡 

 

5、检查不平衡性是否向上传导 

总结：