在计算机许多应用领域中,查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能。比如说:
(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+树
。
分享到:
相关推荐
数据结构概论及算法分析 数据结构是一门研究计算机中对象及其关系的学科。数据结构的定义为(K, R),其中 K 是数据元素的集合,R 是数据元素之间的关系。数据结构的学习可以分为两大部分:静态数据结构和动态数据...
此外,数据结构还可以根据其在生命周期中是否变化分为静态结构(如固定大小的数组)和动态结构(如栈和队列,其大小可以根据需要动态调整)。 数据结构的研究涵盖了三个主要方面:一是逻辑结构,即数据元素之间的...
首先,我们从“概论”开始,理解数据结构的基本概念,包括数据、数据元素、数据对象、数据结构、逻辑结构和物理结构等。这里会讲解数据结构的重要性以及它在解决问题中的作用,同时也会介绍C语言的基本语法和特性,...
1. 概论:这部分内容主要介绍数据结构的基本概念,如数据、数据元素、数据结构、算法等。同时,会讲解时间和空间复杂度的度量,以及在设计算法时需要考虑的因素。 2. 线性表:线性表是最基础的数据结构之一,分为...
1. **第1章 概论**:这一章通常会介绍数据结构的基本概念,包括数据、数据元素、数据对象、数据结构的定义和分类,以及抽象数据类型(ADT)的概念。此外,还会涉及存储结构(顺序结构和链式结构)和算法设计与分析的...
本章还会讨论静态查找表和动态查找表的设计。 这些章节的内容涵盖了数据结构的基础知识,通过C语言实现,能够帮助读者理解数据结构的底层原理,并掌握其实现技巧。课后习题解答可以帮助巩固理论知识,提高实践能力...
查找部分包含静态和动态查找表,如顺序查找、折半查找、二叉排序树和哈希表。排序部分则讲解了多种排序算法,如直接插入排序、希尔排序、快速排序和堆排序。 课程设计还特别强调实践环节,通过问答形式、动画、比喻...
总结起来,JavaScript的面向对象编程更注重于动态性和灵活性,而基于静态类的语言则强调类型安全和结构稳定性。理解这两种不同的面向对象范式对于编写高效且易于维护的JavaScript代码至关重要。
1. **概论**:这部分内容简要介绍了数据结构的基本概念,如数据、数据元素、数据结构、算法、时间复杂度和空间复杂度的度量。这些基础知识是后续学习的基础,虽然考分不多,但理解它们对整个课程至关重要。 2. **...
1. 静态测试和动态测试:静态测试指的是不运行程序,通过阅读代码、设计文档等手段来检查程序的正确性。动态测试则是实际运行软件,检测软件在运行过程中是否存在错误。 2. 黑盒测试和白盒测试:黑盒测试关注于软件...
1. **概论**: - 数据结构的基本概念:数据结构是数据的组织形式,包括逻辑结构(如线性结构、树形结构、图形结构等)和物理结构(如顺序存储、链式存储)。 - 时间和空间复杂度:衡量算法效率的重要指标,时间...
首先,我们从第1章“概论”开始,这一章通常会介绍数据结构的基本概念,包括什么是数据结构,为什么需要学习数据结构,以及数据结构在编程中的重要性。C++作为一种强类型、静态编译的面向对象语言,非常适合实现复杂...
1. **概论**:这部分主要介绍数据结构的基本概念,如数据结构的分类(逻辑结构和物理结构),时间复杂度和空间复杂度的衡量,以及算法设计的基本原则。这部分内容相对较少,但理解它们对于后续章节的学习至关重要。 ...
1. **概论**:这部分通常介绍数据结构的基本概念,如数据、数据类型、数据结构、算法、时间和空间复杂度的衡量标准,以及算法设计时的考虑因素。这部分内容相对较少,但理解它们对后续学习至关重要。 2. **线性表**...
1. **概论**:这部分主要介绍数据结构的基本概念,如数据、数据元素、数据结构、抽象数据类型等,以及时间复杂度和空间复杂度的度量,这些都是评估算法效率的关键指标。 2. **线性表**:作为基础章节,线性表是所有...