【数据结构】简单谈一谈二分法和二叉排序树BST查找的比较 二分法查找： 『在有序数组的基础上通过折半方法不断缩小查找范围，直至命中或者查询失败。』 二分法的存储要求：要求顺序存储，以便于根据下标随机访问 二分法的时间效率：O(Log(n)) 二分法的空间效率：原地查询 O(1) 二分法对应的搜索树是确定的。 二叉排序树查找： 『借助二叉排序树进行搜索，但因为所建立的树本身不一定是轴对称的，所以每次比较并不能确保减小一半范围。』 二叉树的存储要求：需要树形结构，相比顺序存储需要占用更多的空间，但也有链接型数据结构灵活可拓展的有点。 二叉排序树查找的时间复杂度：平均情况下，O(Log(n))，但在单支树的情况下就变成了顺序遍历搜素，复杂度退化为O(n)。 二叉树的空间复杂度：因为需要建立排序二叉树，所以空间复杂度为O（n） 插入节点的平均时间复杂度为O（LogN），不过这里我们主要谈的是查找，所以其他方面暂且不聊了。后面为了减小时间复杂度，产生了二叉平衡树用于优化二叉树查找。 这里有一个经常提到的概念——查找长度，又分为失败查找长度，成功查找长度，即是为了得出查找结果需要进行的素对比次数，要借助对应搜索树和树高来分析。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/88322.html
