四川网站建设设计公司哪家好,学习网页设计的培训机构,网站服务器有哪些种类,网站搭建思路目录
二叉排序树的定义
二叉排序树的查找
二叉排序树的插入
二叉排序树的构造
二叉排序树的删除
查找效率分析
回顾 二叉排序树的定义 二叉排序树的查找
查找成功的情况 查找失败的情况 二叉排序树的插入 注意
#xff08;1#xff09;二叉排序树不允许出现重复的值…目录
二叉排序树的定义
二叉排序树的查找
二叉排序树的插入
二叉排序树的构造
二叉排序树的删除
查找效率分析
回顾 二叉排序树的定义 二叉排序树的查找
查找成功的情况 查找失败的情况 二叉排序树的插入 注意
1二叉排序树不允许出现重复的值不能插入相同的结点所以插入的元素如果是和之前的关键字相同则插入失败。
2递归实现的最坏空间复杂度是O(h)
3新插入的结点一定是叶子结点 二叉排序树的构造 二叉排序树的删除
1 2 比如删除13结点和60结点后的效果 3 方法1
找右子树的直接后继通过中序排列 要删除50用50的右子树将右子树中序排列60.61.63.65.66.70最先访问的结点60替代要删除的结点50的位置
删除结果为 方法2
找左子树的直接前驱中最大的值去替代要删除的结点要删除的结点50的左子树最大的值30所以用30代替50 删除后的结果如下 查找效率分析 对比1次就是一层2次就是第二层,依次类推......
比如对于70的查找长度就是3次三层
对比次数肯定不会超过树的高度
若树高h找到最下层的一个结点需要对比h次 查找最好情况就是像平衡二叉树那样
平衡二叉树树上任一个结点左子树和右子树的深度之差不超过1 回顾
