数据结构之查找

查找

查找表是由同一类型的数据元素（或记录）构成的集合。
关键字是数据元素中某个数据项的值，也称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项，称为关键码。若此关键字可以唯一标识一个记录，则称为该关键字为主关键字。主关键字所在的数据项称为主关键码。
对于那些可以识别的多个数据元素或记录的关键字，称之为次关键字。
查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。
查找表按照操作方式来分由两大种：静态查找表和动态查找表。

静态查找表
只作查找操作的查找表。它的主要操作有：
（1） 查询某个“特定的”数据元素是否在查找表中
（2）检索某个“特定”的数据元素和各种属性

动态查找表
在查找过程中同时插入查找表不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。动态查找表的操作有：
（1）查找时插入数据元素
（2）查找时删除数据元素

为了提高查找的效率，需要专门为查找操作设置数据结构，这种面向查找的数据结构称为查找结构。

逻辑上，查找所基于的数据结构是集合，集合中的记录之间没有本质关联。为了得到较高的查找性能，就需要改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。

顺序表查找
顺序查找又叫线性查找，是最基础的查找技术，其查找过程： 从表中的第一个或最后一个记录开始，逐个查找记录的关键字和给定值进行比较，相等则查找成功，返回查找到的记录；直到最后一个或第一个记录，其关键字都不能和给定值匹配，则表中不存在所查找的记录，查找不成功。
顺序表查找的时间复杂度为O（n），当n较大时，查找效率低。

有序表查找
有序表是指数据元素已经按照某个顺序进行有序排列。在有序表的基础上，分为折半查找、插值查找、斐波那契查找。
折半查找
折半查找技术，又称为二分查找。前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。折半查找的基本思想： 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功，若给定值小于中间值，则在中间记录左半区查找；若大于中间值，则在中间记录右半区继续查找，不断重复上述过程，直到成功，或者所有区域为无记录，则不存在。
折半查找的时间复杂度为O（logn）
插值查找
插值查找根据要查找的关键字与查找表中的最大最小纪录的关键字比较之后的查找方法，根据要查找的值与最大最小值差的比例来分配下标和查找区域，在折半查找的基础上加以改进：
mid=low+((key-a[low])/(a[high]-a[low]))*(high-low)
该算法从时间复杂度来说也是O（logn），对于数据分布比较均匀的查找表其效率高于折半查找，但对于分布极不均匀的情况下并不太适合使用
斐波那契查找
斐波那契查找利用黄金分割原理实现。
其每次取的比较值的下标按照黄金分割比切开，分别比较左侧和右侧区域，因此首先根据查询数组的长度n在斐波那契数列中的位置，确定分割点的下标位置，并补齐数组长度n的后续位置，防止越界。如果比较结果给定值小于分割点下标对应值，则下一轮查询在左半区，查询个数为F[k-1],k为n在斐波那契数列中位置对应下标，如果比较结果给定值大于分割点下标位置，则下一轮查询在右半区进行，查询个数为F[k-2]，因为F[k]=F[k-1] +F[k-2]

线性索引查找
对于无序的大量数据查找，通过索引快速查找所需数据。
索引是为了加快查找速度而设计的数据结构，该过程通过把关键字与它对应的记录相关联。
一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为：线性索引、树形索引、多级索引。

线性索引是将索引项集合组织为线性结构，也称索引表。
常见的三种线性索引：稠密索引、分块索引、倒排索引。

稠密索引
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。

image
稠密索引中的索引项按照关键码有序排列。
索引项序列有序，因此在查找关键字时可以使用折半查找、插值查找、斐波那契查找等方法，提高查找效率。

分块索引
稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，对数据集进行分块，使其分块有序，对每一块建立索引项，从而减少索引项的个数。
分块有序，将数据集的记录分成若干块，并满足：

• 块内无序，每一块内的记录不要求有序。
• 块间有序，第二块的所有记录的关键字均要大于第一块的所有记录的关键字，后续类推

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。分块索引的索引项分为三个数据项：

• 最大关键码存储每一块数据集的最大关键字，使得下一块中最小关键码比这块的最大关键码要大
• 块中记录个数，便于循环时使用
• 指向块首的数据指针便于开始对这一块的数据进行遍历

image

分块索引表中查找分两步进行：

1. 在分块索引表中查找关键字所在的块，分块索引表是块间有序的，因此可以利用折半、插值等算法查找
2. 根据块首指针找到相应块，并在块中顺序查找关键码。块内可以是无序的，因此使用顺序查找。

分块索引的平均查找长度为 n^(1/2)+1 ,其搜索效率比起顺序查找O(n)效率要高，不过比不上折半查找的log(n)效率。

倒排索引
倒排索引的通用结构：

• 次关键码
• 记录号表

记录号表中存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或是该记录的主关键字）。使用这种方式的索引方法为倒排索引。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录地址，由于不是由地址来确定属性值，而是由属性值确定记录的位置，因此称为倒排索引。

二叉排序树
又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于根结构的值
• 若它的右子树不空，则右子树上所有结点的值均大于根结构的值
• 它的左右子树也分别是二叉排序树

二叉排序树首先一颗二叉树，采用递归的定义方法，它的结点间满足一定的次序关系，左子树结点一定比双亲结点值小，右子树结点一定比双亲结点大
二叉排序树的构造，并不是为了排序，而是为了提高查找、插入、删除关键字的效率。在一个有序数据集上的查找，其效率是要高于无序数据集的，同时二叉树这样的非线性结构，有利于插入和删除的实现。

二叉排序树通过链式存储，保持了链式存储在执行插入或删除时不用移动元素的优点，找到合适的插入和删除位置后，仅仅修改指针即可。对于二叉排序树的查找，走的是从根结点到目标节点的路径，比较次数为给定值的结点在二叉排序树的层数，极端情况为根结点即为要查找结点，这样只需一次，最多不会超过树的深度。因此二叉排序树的查找性能取决于二叉排序树的形状，如果是极端的左斜树或右斜树，那么其查找效率比不上左右相对平衡的二叉树。因此，最好将二叉树构建为平衡二叉树。

平衡二叉树
平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。平衡二叉树是一种高度平衡的二叉排序树。要么它是一棵空树，要么左子树和右子树都是平衡二叉树，且左子树和右子树的深度差绝对值不超过1。将二叉树上结点的左子树减去右子树深度的值称为平衡因子BF（Balance Factor）那么平衡二叉树的平衡因子只能是-1,0或1。也就是说，只要二叉树上有一个结点的平衡因子绝对值大于1，二叉树就是不平衡的。平衡二叉树的前提是：首先它是一颗二叉排序树

image.png

距离插入点最近的，且平衡因子绝对值大于1的结点为根结点的子树，称为最小不平衡子树

image

平衡二叉树实现原理
平衡二叉树构建的基本原理是在构建二叉排序树的过程中，每当插入一个结点时，检查是否因为新的插入而破坏了树的平衡性，如果是，找出最小不平衡子树。在保持二叉排序树的特性下，调整最小不平衡子树的各个节点之间的关系，进行相应的旋转，使之成为新的平衡子树。

image
image
image
image
image
二叉平衡树在构建过程中，如果出现最小不平衡子树，当最小不平衡子树的BF大于1时就右旋，如果小于-1就左旋，如果插入新节点后发现最小不平衡子树的BF与结点的BF符号相反，先将结点进行旋转，然后再反向旋转依次完成平衡操作。
对于数组int a[10] = { 3,2,1,4,5,6,7,10,9,8 };进行二叉平衡树算法得到的结果：
image

多路查找树(B树)
之前涉及的树结构，都是一个节点可以有多个孩子，但自身只存储一个元素。而二叉树的限制更多，结点最多只能有两个孩子。一个结点只能存储一个元素。在元素数量非常多的时候，树的度要么很大，要么深度值很大，这样在数据的存取时，会成为时间效率上的瓶颈，这样需要打破一个结点只能存储一个元素的限制，对此引入多路查找树。
多路查找树，其每一个节点的孩子树可以多于两个，每个结点可以存储多个元素。而且它是查找树，所有元素之间存在特定的排序关系。
对于每一个结点存储多少个元素，以及孩子树的数量，有4种常用的特殊形式：2-3树、2-3-4树、B树和B+树。
2-3树
2-3树每一个节点都具有2个孩子（也称为2结点）或3个孩子（也称为3结点）。
一个2结点包含一个元素和两个孩子（或没有孩子），与二叉排序树类似，左子树包含元素小于该元素，右子树包含元素大于该元素。2结点要么有2个孩子，要么没有孩子。
一个3结点包含一大一小两个元素和三个孩子（或没有孩子），一个3结点要么有3个孩子，要么没孩子。如果3结点右孩子，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
2-3树的所有叶子结点都在同一层次。

image

2-3-4树
2-3-4树是2-3树的扩展概念，包括了一个4结点，4结点包含小中大三个元素和4个孩子（或没有孩子），4结点有孩子的话，左子树小于最小的元素，第二子树大于最小元素小于中间元素，第三子树大于中间元素小于最大元素，右子树大于最大元素。

B树（B-tree）
B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶，因此2-3树是3阶B树，2-3-4树是4阶B树。
一个m阶的B树具有如下属性：

• 如果根结点不是叶结点，则其至少有两颗子树
• 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<=k<=m。每一个叶子结点n都有k-1个元素，其中[m/2]<=k<=m（结点少于[m/2]就需要合并了）
• 所有叶子结点都位于同一层次
• 所有分支节点包含下列信息数据（n,A0,K1,A1,K2......,An,Kn），其中：Ki为关键字，Ki<Ki-1，Ai为指向子树根节点的指针，且指针Ai-1所指子树中的所有结点的关键字均小于Ki，An所指子树的所有结点的关键字均小于Kn
  image
  关于n个结点的m阶B树，需要查找的最坏的的情况：
  image
  个人认为查找不成功的结点为 n-1，而非是n+1

B+树
在B树结构中，如果要遍历B树，假设每个结点属于硬盘的不同页面，往返于每个结点之间意味着在硬盘的不同页面之间进行多次访问，如图：

image
当中序遍历所有结点时，需要从页面2->页面1->页面3->页面1->页面4->页面5
这样来回在硬盘的不停页面之间检索，时间性能低。
为了解决元素的遍历问题，在原有的B树结构基础上，加上新的元素组织形式，形成B+树。
B+树应文件系统所需而出的一种B树变形树。在B树中，每一个元素在该树中只会出现一次，可能在叶子结点，也可能在分支节点。在B+树中，出现在分支节点中的元素会被当作在该分支结点位置的中序后继者（叶子结点）中再次列出。每一个叶子结点都会保存一个指向后一叶子结点的指针。
image
一棵m阶的B+树和m阶的B树的差异在于：

• 有n棵子树的结点中包含有n个关键字（包含双亲的一个关键字）
• 叶子结点包含所有的关键字信息，以及指向包含关键字记录的指针，叶子结点本身根据关键字的大小从小到大进行顺序链接
• 所有的分支节点是索引，结点中仅包含其子树中的最大（或最小）关键字 ，不会存关键字记录的指针，所有的数据地址必须到叶子节点才能获取到，因此每次数据查询次数一样

散列表查找
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。查找时，根据确定的对应关系找到给定值key的映射f（key）,若查找集合中存在这个记录，则必定在f（key）的位置上。
这种对应关系f称为散列函数，又称为哈希函数（Hash）。按照这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表。关键字对应的记录存储位置称为散列地址。

散列过程

• 在存储时，通过散列函数计算记录的散列地址，并按照此散列地址存储记录
• 查找记录时，通过同样的散列函数计算记录的散列地址，按照此散列地址访问记录。

散列技术既是一种存储方法，又是一种查找方法。与线性表、树、图等结构不同的是，数据元素之间不存在某种逻辑关系，只与关键字关联。散列主要是面向查找的存储结构。
散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率会提高。
散列技术不适合一个关键字对应多条记录的情况，范围查找，表中记录排序等情况。

散列函数构造方法
两个原则：

• 计算简单
• 散列地址分布均匀

常用散列函数构造方法：

• 直接定址法
  取关键字的某个线性函数值为散列地址：
  f(key)=a*key+b
  需要事先知道关键字的分布情况，适合查找表较小且连续的情况。现实应用中，此法虽简单，并不常用。

• 数字分析法
  数字分析法适合处理关键字位数较多的情况，如事先知道关键字的分布且关键字若干位分布均匀，可以考虑此法。

• 平方取中法
  比如关键字1234 平方 1522756 取中：227
  此法比较适合不知道关键字分布，位数又不是很大的情况

• 折叠法
  折叠法将关键字从左至右分割成相等几部分叠加求和，按照散列表的长度，取后几位做为散列地址
  此法不需要知道关键字的分布，适合关键字位数较多的情况。

• 除留余数法
  该方法为最常用的构造散列函数的方法，对于散列表长度为m的散列函数公式为：
  f(key)=key mode p(p<=m)
  若散列表长度为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

• 随机数法
  选择一个随机数，取关键字的随机函数值作为其散列地址。也就是f(key)=random(key)。当关键字的长度不等时，可以采取此法。

处理散列冲突的方法

• 开放定址法
  一旦发生散列地址冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。其公式是：
  fi(key)=(f(key)+di) MOD m （di=1^2,-12...q^2,-q2,q<=m/2） 二次探测法
  fi(key)=(f(key)+di) MOD m （di是同一个随机种子生成的随机数） 随机探测法

• 再散列函数法
  事先准备多个散列函数：
  fi(key)=RHi(key) (i=1,2......k)
  RGi就是不同的散列函数，每次发生散列地址冲突时，就换一个散列地址，相应地会增加计算时间。

• 链地址法
  当发生地址冲突时，将所有关键字的同义词的记录存储在一个单链表中，这种表称为同义词子表，在散列表中只存储所有同义词表的头指针。如对关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}，使用除留余数，以12为除数，得到结构：
  

  image

• 公共溢出区法
  将所有冲突的关键字建立一个公共溢出区来存放

  image
  对给定值通过散列函数计算散列地址后，先与基本表的相应位置进行比对，如果想等，则查找成功，如果不相等，到溢出表进行顺序查找。相对于基本表而言，在冲突数据较少的情况下，公共溢出区的结构对查找性能来说还是较高。

散列查找表的性能分析
如果散列表中不存在冲突的情况，其查找效率是非常高效的，时间复杂度为O(1) 。实际应用中，冲突不可避免，散列查找的平均查找长度与以下因素有关：

• 散列函数是否均匀
  散列函数的均匀程度影响冲突的频繁程度

• 处理冲突的方法
  相同的关键字，相同的散列函数，处理冲突的方法不同，平均查找长度不同。比如线性探测会产生堆积，没有二次探测好，而链地址法处理不会产生冲突

• 散列表的装填因子
  装填因子=记录个数/散列表长度 ，表示装满的程度，不管记录个数多大，选取合适的装填因子可以使平均查找长度限定在一个范围内，通常散列表的空间设置比查找集合要大，这样冲突的可能性相对较小。