【数据结构】简单谈一谈二分法和二叉排序树BST查找的比较
2024-10-11 12:53:27
二分法查找:
『在有序数组的基础上通过折半方法不断缩小查找范围,直至命中或者查询失败。』
二分法的存储要求:要求顺序存储,以便于根据下标随机访问
二分法的时间效率:O(Log(n))
二分法的空间效率:原地查询 O(1)
二分法对应的搜索树是确定的。
二叉排序树查找:
『借助二叉排序树进行搜索,但因为所建立的树本身不一定是轴对称的,所以每次比较并不能确保减小一半范围。』
二叉树的存储要求:需要树形结构,相比顺序存储需要占用更多的空间,但也有链接型数据结构灵活可拓展的有点。
二叉排序树查找的时间复杂度:平均情况下,O(Log(n)),但在单支树的情况下就变成了顺序遍历搜素,复杂度退化为O(n)。
二叉树的空间复杂度:因为需要建立排序二叉树,所以空间复杂度为O(n)
插入节点的平均时间复杂度为O(LogN),不过这里我们主要谈的是查找,所以其他方面暂且不聊了。后面为了减小时间复杂度,产生了二叉平衡树用于优化二叉树查找。
这里有一个经常提到的概念——查找长度,又分为失败查找长度,成功查找长度,即是为了得出查找结果需要进行的元素对比次数,要借助对应搜索树和树高来分析。
最新文章
- 收集的React.JS资料
- 【C#】DataRowState演变备忘
- Android进程绝杀技--forceStop
- (转) CCEditBox 编辑框
- ldr和adr在使用标号表达式作为操作数的区别
- [原]SQLite的学习系列之获取数据库版本二
- 一.OSI与TCP
- Android消息机制——时钟显示和异步处理工具类(AsyncTask)
- Javascript手记-基本类型和引用类型
- java 中的匿名内部类
- [摘] SQLPLUS Syntax
- getchar()函数的返回值赋给char型,用if(ch=getchar() != EOF)测试,输入ctrl+z同样可以结束循环的分析
- Linux为用户设定环境变量
- 不可小觑的Web开发编码规范
- css ::before和::after伪元素的用法
- mariadb 长链接时间限制导致队列消费进程崩溃
- 如何选择分布式事务形态(TCC,SAGA,2PC,补偿,基于消息最终一致性等等)
- HDU 2639 01背包(分解)
- http请求的全过程
- (转)Paper list of Meta Learning/ Learning to Learn/ One Shot Learning/ Lifelong Learning
热门文章
- 给jquery-validation插件添加控件的验证回调方法
- 把UI图里的小图标制作成icon font
- Win10 UWP开发系列:使用VS2015 Update2+ionic开发第一个Cordova App
- flask+sqlite3+echarts2+ajax数据可视化报错:UnicodeDecodeError: 'utf8' codec can't decode byte解决方法
- 笔记:xubuntu下如何让系统默认使用nvidia显卡,而不是intel集显
- js的命名规范
- R语言:常用统计检验
- java多线程解读二(内存篇)
- 从 HTTP 到 HTTPS - 什么是 HTTPS
- GreenDao2.2升级GreenDao3.0的适配之路