当前课程知识点:数据库技术与程序设计 > 第五章 数据检索与查询文件 > 5.1 数据检索方法 > 【拓展阅读】二叉树查找算法
二叉树查找算法
一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
(4)没有键值相等的结点。
查找步骤:
若根结点的关键字值等于查找的关键字,成功。
否则,若小于根结点的关键字值,递归查左子树。
若大于根结点的关键字值,递归查右子树。
若子树为空,查找不成功。
平均情况分析(在成功查找两种的情况下):
在一般情况下,设 P(n,i)为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P(n,i)= P(6, 3) = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意:这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况,P(i)为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数
P(3) = (1+2+2)/ 3 = 5/3
P(2) = (1+2)/ 2 = 3/2∴ P(n,i)= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
∴ P(n)= P(n,i)/ n <= 2(1+I/n)lnn
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)
参考文献来源:百度百科,维基百科,ScienceDaily
https://blog.csdn.net/sinat_31089473/article/details/106629844
-知识点拼图+问题求解流程+软件工程开发教学流程——写给翻转课堂开课教师
-技术分享贴续篇:怎样用窗体显示一条记录存储的多张OLE图像文件?
-技术分享贴:复杂的SQL自体连接和嵌套查询,涨粉最多的用户ID和涨粉数
-往届竞赛获奖作品展示
-1.1 数据与数据管理
--【拓展阅读】到底什么是IT(Information Technology)
-1.2 DBS=DB+DBMS
-1.3 不以六律不能正五音——数据模型
-- 课件1.3.1 数据模型
-1.4 数据库系统结构
-本章小结
--第一章小结
-第一章作业
-2.1 数据库设计流程
-2.2 概念结构设计
-2.3 逻辑结构设计
-本章小结
--第二章小结
-第二章作业
-3.1 数据库管理系统
-3.2 创建数据库
-3.3 创建数据表
-3.4 维护数据表
-本章小结
--第三章小结
-第三章作业
-4.1 基本数据类型
-4.2 常量
--4.2.1 常量
-4.3 变量和数组
--4.3.1 变量
-4.4 表达式和函数
-本章小结
--第四章小结
-第四章作业
-【讨论帖:悬赏!谁能解决Round()函数Banker’s rounding算法的bug?】
-5.1 数据检索方法
-5.2 数据库查询文件
-5.3 选择查询
-5.4 参数查询
-5.5 操作查询
-本章小结
--第五章小结
-第5章作业
-6.1 SQL概述
-6.2 SQL数据定义语言
-6.3 SQL数据查询语言
-6.4 SQL数据操作语言
-本章小结
--第六章小结
-第6章作业
-【讨论帖:你是否听说过“自然语言检索”,你在什么地方见到过,或者使用过“自然语言检索”吗?】
-7.1 窗体设计
-7.2 报表设计
-本章小结
--第七章小结
-第七章作业
-【讨论帖:你能总结一下窗体和报表的共性和区别吗?在你的工作、学习或生活中,你都见到过哪些窗体和报表的实际应用?】
-8.1 VBA编程基础
-8.2 顺序结构及常用命令
-8.3 分支结构
--8.3.2 多路分支选择语句Select Case 和分支嵌套
--课件8.3.2 多路分支选择语句Select Case 和分支嵌套
-8.4 循环结构
-8.5 函数与过程
-8.6 VBA程序调试
-8.7 数组
-本章小结
--第八章小结
-第八章作业
-【讨论帖:我们学习了VBA面向过程的程序设计,你能结合实践,谈谈自己对算法和程序的理解吗?】
-9.1 面向对象的基本概念
-9.2 控件对象的属性和方法
-9.3 控件对象的事件
-9.4 窗体的面向对象程序设计
-【拓展阅读】【综合案例】Word中的查找与替换是如何实现的?
-本章小结
--第九章小结
-第九章作业
-【讨论贴:本章用小黄鸭类比了面向对象的各种概念,你能也用类比的方式谈谈你对面向对象的理解吗?】
-10.1 宏的基本概念
-10.2 宏的创建与调用
-10.3 数据宏
-10.4 宏的调试和转换
-【拓展阅读】【综合案例】一句代码不敲,就开发了一个航班查询系统?
-本章小结
--第十章小结
-第十章作业
-【讨论帖:王者、LOL、魔兽、DOTA……,说说你在虚拟世界里用宏(超级宏)所向披靡的故事吧!】
-11.1 数据库应用系统结构
-11.2 教学教务管理系统功能需求
-11.3 教学教务管理系统底层数据结构
-11.4 登录模块实现
-11.5 学生管理模块实现
-11.6 教学管理模块实现
-11.7 系统测试与发布
-本章小结
--第十一章小结
-课程综合设计
-综合练习题库