在计算机许多应用领域中,查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能。比如说:
(1) 全文检索技术中对文本建立索引之后,对索引的查找效率将决定搜索引擎的质量。
(2) mysql数据库的索引就是B+树结构,查找效率极高。
(3) Windows OS的文件系统结构也是采用B+树进行存储的。
在《查找算法》系列文章中,我将主要介绍动态查找树结构。其他静态查找结构在下面简单的引出:
静态查找:数据集合稳定,不需要添加,删除元素的查找操作。
动态查找:数据集合在查找的过程中需要添加或删除元素。
静态查找结构概论
当把看似杂乱无章的数据组织成具有一定结构和一定规则的集合体时,查找的效率就会大不一样了。
【顺序查找】
大家都知道,最简单的查找方法就是顺序查找
(一个接一个得查下去)。这种线性结构的查找效率是最低的,时间复杂度在O(N)数量级,最坏的情况莫过于所有数据都找遍了,还是没找到。
难道真的每一个数据都必须找一次吗?
【折半查找】
很显然的一个例子就是利用折半查找(二分查找)
法对有序的线性数据进行查找。每一次都找1/2的部分,查找次数当然就大大减少了。时间复杂度在O(log2
N)数量级上。
折半查找实际就是一颗二叉树遍历,其中最中间的数据就是二叉树的根。但是问题又来了,如果这个根数据一年才查找一次,而这棵树的叶子数据1秒钟需要查找1W次(考虑数据的查找概率)。这种折半查找的效率又不行了?
【静态最优查找树/次优查找树】
考虑到上面折半查找在概率问题下的效率不行,我们就想能不能把折半查找二叉树中概率最大的数据放在根的位置上或者放在离根较近的位置上。基于此,静态最优查找树/次优查找树的思想就是在折半查找二叉树的基础上求解一个带权(数据概率)路径长度最小/近视最小的树。总体上说,静态最优/次优查找树的时间复杂度也在
O(log2
N)数量级上(特别是在数据具有查找概率的情况下也能保证这个效率)。
此外,还有一些别的静态查找结构:索引顺序表的分块查找,线性冲突再散列的hash表的查找(Hash表将在一个专题里面讲到)等。
上面介绍查找表都属于静态查找结构,也就是说当需要查找的数据集合动态变化的时候,这些结构都很不方便。
比如:
折半查找: 当查找过程中没有发现元素A的时候,需要动态添加元素A,此时整个有序表将面临重新排序的问题。
静态最优查找树: 新增元素不光要重新排序,而且原有的整棵带权路径长度最小值的树也将重建(最优解变化了)。这在代价上是沉重的,这也是为什么
静态最优查找树并不适合实际应用的巨大缺陷了。
正是由于实际应用中,很多时候需要在查找的同时进行添加,删除操作。因此便捷的动态查找结构就十分的总要了。下面我们用专题的形式详细讲解二叉查找树
,平衡二叉树
,红黑树
,B-树/B+树
。
分享到:
相关推荐
数据结构,静态查找表,C语言开发,界面友好,绝对有价值!!!
广工的数据结构实验报告-静态查找表,你懂得……
数据结构——二叉查找树(BST)静态查找表,使用数据结构实现BST
学数据结构写的东西--静态查找表的实现,希望对大家有点帮助!
静态顺序查找表结构的建静态顺序查找表结构的建立与销毁,静态按关键字非降序查找表的构造,查找表的关键字查找(顺序查找与折半查找),可作为学生管理系统的一项基本操作。 立与销毁
实验七 查找 一、实验目的 1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。 3、学会哈希函数的构造方法,处理冲突的机制以及哈希表的查找。 二、实验内容...
广工工业大学数找表ADT(代码及实验报告据结构静态查),完美代码+完美实验报告。(编译软件wintc)
静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法静态查找表。实现有序表的折半查找算法
2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。 3、掌握二叉排序树的生成、插入、删除、输出运算。 二、实验内容 1、有序顺序表的二分查找的递归算法
数据结构课件:第9章 查找1静态查找表.pptx
静态数据结构与动态数据结构 静态数据结构与动态数据结构 数据结构:计算机中组织和存储数据的⼀种特殊⽅式,以便能够有效地访问和修改数据,数据结构是数据值的集 合,它们之间的关系,以及可以应⽤于数据的函数或...
非常棒的数据结构程序演示 ,分为Pascal语言和C语言版,其中包含 顺序表 广义表 动态查找 静态查找 二叉树 链表 栈 串 稀疏矩阵 储存管理 内部排序 外部排序等等 只需解压即可
静态查找表算法
数据结构查找技术静态查找表PPT学习教案.pptx
静态查找表 课程设计 基本操作的实现 和 有关数据测试
①静态查找 折半查找和斐波拉契查找(有序) ②动态查找 二叉排序树的基本操作 任务: 编写算法实现对依次输入的关键字序列建立二叉排序树 并能实现二叉排序树的查找 插入和删除运算 ③散列法查找 在Hash...
数据结构 查找 ppt c语言版 包括静态查找 动态查找 与 hash查找
用c++的类实现,对于c++初学者帮助较大,主要熟悉静态变量 静态方法的使用 将练习与数据结构相结合
查找(1)静态查找.pdf