数据结构--平衡二叉树

 目录 

平衡二叉树定义

平衡二叉树的插入

调整最小不平衡子树 

 LL型

RR型 

LR型​编辑

 RL型​编辑

练习

 查找效率分析​编辑

回顾知识点

平衡二叉树的删除

例1 

​编辑 例2​编辑

例3 

 例4​编辑

​编辑 平衡二叉树的删除回顾​编辑

---

• 定义
• 插入操作
• 插入新结点后如何调整“不平衡”问题
• 查找效率分析
• 平衡二叉树的删除（非重点）

平衡二叉树定义

平衡二叉树的插入

 

调整最小不平衡子树 

 

 LL型

 

RR型 

 

代码思路 

 

LR型

 

 

 RL型

 

总结 

 

练习

 

 

 

 

 

 

 查找效率分析

可以证明含有n个结点的平衡二叉树的最大深度为O(log2N), 平衡二叉树的平均查找长度为O(log2N)

（这log是以2为底n的对数）

回顾知识点

平衡二叉树的删除

 

 

例1 

 

 例2

 

 

 

例3 

 

 

 

 

 

 

 

 例4

 

 

 

 

 平衡二叉树的删除回顾