首页 > 代码库 > 【数据结构】简单谈一谈二分法和二叉排序树BST查找的比较
【数据结构】简单谈一谈二分法和二叉排序树BST查找的比较
二分法查找：
『在有序数组的基础上通过折半方法不断缩小查找范围，直至命中或者查询失败。』
二分法的存储要求：要求顺序存储，以便于根据下标随机访问
二分法的时间效率：O(Log(n))
二分法的空间效率：原地查询 O(1)
二分法对应的搜索树是确定的。
二叉排序树查找：
『借助二叉排序树进行搜索，但因为所建立的树本身不一定是轴对称的，所以每次比较并不能确保减小一半范围。』
二叉树的存储要求：需要树形结构，相比顺序存储需要占用更多的空间，但也有链接型数据结构灵活可拓展的有点。
二叉排序树查找的时间复杂度：平均情况下，O(Log(n))，但在单支树的情况下就变成了顺序遍历搜素，复杂度退化为O(n)。
二叉树的空间复杂度：因为需要建立排序二叉树，所以空间复杂度为O（n）
插入节点的平均时间复杂度为O（LogN），不过这里我们主要谈的是查找，所以其他方面暂且不聊了。后面为了减小时间复杂度，产生了二叉平衡树用于优化二叉树查找。
这里有一个经常提到的概念——查找长度，又分为失败查找长度，成功查找长度，即是为了得出查找结果需要进行的元素对比次数，要借助对应搜索树和树高来分析。
【数据结构】简单谈一谈二分法和二叉排序树BST查找的比较
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。