数据结构(7.3_3)——平衡二叉树的删除

平衡二叉树的删除

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

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

平衡二叉树的删除步骤

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、检查不平衡性是否向上传导 

总结： 

原文地址：https://blog.csdn.net/m0_65240792/article/details/142314240

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！