【数据结构】简单谈一谈二分法和二叉排序树BST查找的比较

二分法查找:
『在有序数组的基础上通过折半方法不断缩小查找范围,直至命中或者查询失败。』
 
二分法的存储要求:要求顺序存储,以便于根据下标随机访问
 
二分法的时间效率:O(Log(n))
 
二分法的空间效率:原地查询 O(1)
 
二分法对应的搜索树是确定的。
 
二叉排序树查找:
『借助二叉排序树进行搜索,但因为所建立的树本身不一定是轴对称的,所以每次比较并不能确保减小一半范围。』
 
二叉树的存储要求:需要树形结构,相比顺序存储需要占用更多的空间,但也有链接型数据结构灵活可拓展的有点。
 
二叉排序树查找的时间复杂度:平均情况下,O(Log(n)),但在单支树的情况下就变成了顺序遍历搜素,复杂度退化为O(n)。
 
二叉树的空间复杂度:因为需要建立排序二叉树,所以空间复杂度为O(n)
 
插入节点的平均时间复杂度为O(LogN),不过这里我们主要谈的是查找,所以其他方面暂且不聊了。后面为了减小时间复杂度,产生了二叉平衡树用于优化二叉树查找。
 
这里有一个经常提到的概念——查找长度,又分为失败查找长度,成功查找长度,即是为了得出查找结果需要进行的元素对比次数,要借助对应搜索树和树高来分析。
 
上一篇:[剑指Offer]33-根据后序序列判断是否能组成BST


下一篇:STM32 USB CAN 学习笔记 - 共享RAM的用法