本文主要是介绍折半查找和二叉排序树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.折半查找和二叉排序树的时间性能分析:
- 从查找过程看,二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树上的查找和二分查找差不多,但不完全一致;
- 折半查找的性能分析可以用二叉判定树来衡量,平均查找长度和最大查找长度都是O(logn);
- 二叉排序树的查找性能与数据的输入顺序有关,最好情况下的平均查找长度与折半查找相同,但最坏情况时,即形成单支树时,其查找长度为O(n)。
- 折半查找的判定树唯一,而二叉排序树不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树。
2.就维护表的有序性而言,二叉排序树无需移动节点,只需修改指针即可完成插入和删除操作,平均执行时间是O(logn)。二分查找的对象是有序顺序表,若有插入和删除结点的操作,所花的代价是O(n)。
3.当有序表是静态查找表时,宜用顺序表作为其存储结构,而采用二分查找实现其查找操作;若有序表是动态查找表,则应选择二叉排序树作为其逻辑结构。
4.折半查找过程所对应的判定树是一棵平衡二叉树:每次把一个数组从中间分割时,总是把数组分为结点数相差最多不超过1的两个子数组,从而使得对应的判定树的两颗子树高度差绝对值不超过1。
这篇关于折半查找和二叉排序树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!