沧州手机网站开发,网站如何做关键词优化,自己做设计图的app,展示型网站制作服务文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1、定义2、二叉排序树的常见操作3、性能分析二、平衡二叉树1、…
文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1、定义2、二叉排序树的常见操作3、性能分析二、平衡二叉树1、定义2、平衡二叉树的查找3、平衡二叉树的插入多路查找树一、B树1、定义2、B树与磁盘存取3、B树的查找4、B树的插入5、B树的删除二、B树1、定义散列表查找哈希表一、散列表查找的基本概念二、散列函数的构造方法1、直接定址法2、数字分析法3、平方取中法4、除留余数法三、处理散列冲突1、开放定址法2、链地址法拉链法3、公共溢出区法四、散列表查找实现1、算法2、性能分析附录什么是链表并用代码手动实现一个单向链表单向循环链表增加元素、删除元素、打印循环链表等功能什么是双向链表并用代码手动实现一个双向链表什么是双向循环链表以及实现过程线性表--栈和队列线性表--list详解建议收藏线性表--数组树(Tree)图(Graph)查找
【知识框架】
查找概论
一、查找的基本概念
查找(Searching)就是根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。
查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。
关键字(Key)数据元素中唯一标识该元素的某个数据项的值使用基于关键字的查找查找结果应该是唯一的。例如在由一个学生元素构成的数据集合中学生元素中“学号”这一数据项的值唯一地标识一名学生。
静态查找表(Static Search Table)只作查找操作的查找表。
主要操作 查询某个“特定的”数据元素是否在查找表中。检索某个“特定的”数据元素和各种属性。
动态查找表(Dynamic Search Table) 在查找过程中同时插入查找表中不存在的数据元素或者从查找表中删除已经存在的某个数据元素。
主要操作 查找时插入不存在的数据元素。查找时删除已存在的数据元素。
平均查找长度在查找过程中一次查找的长度是指需要比较的关键字次数而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值其数学定义为
式中n是查找表的长度Pi是查找第i个数据元素的概率一般认为每个数据元素的查找概率相等即Pi 1 / Ci 是找到第i ii个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。
顺序表查找
一、定义
顺序查找(Sequential Search) 又叫线性查找是最基本的查找技术作为一种最直观的查找方法其基本思想是从线性表的一端开始逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件则查找成功返回该元素在线性表中的位置若已经查找到表的另一端但还没有查找到符合给定条件的元素则返回查找失败的信息。
二、算法
下面给出其算法
/*有哨兵顺序查找*/
int Sequential_Search(int *a, int n, int key){int i;a[0] key; //设置a[0]为关键字称之为“哨兵”i n; //循环从数组尾部开始while(a[i] ! key){i--;}return i; //返回0则说明查找失败
}这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧看似与原先差别不大但在总数据较多时效率提高很大是非常好的编码技巧。 上述顺序表查找时间复杂度是O(n)。
有序表查找
一、折半查找
折半查找(Binary Search)技术又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序)线性表必须采用顺序存储。折半查找的基本思想是在有序表中取中间记录作为比较对象若给定值与中间记录的关键字相等则查找成功若给定值小于中间记录的关键字则在中间记录的左半区继续查找若给定值大于中间记录的关键字则在中间记录的右半区继续查找。不断重复上述过程直到查找成功或所有查找区域无记录查找失败为止。
算法如下
int Binary_Search(SeqList L, ElemType key){int low 0, high L.length - 1, mid;while(low high){mid (low hight)/2; //取中间位置if(L.elem[mid] key){return mid; //查找成功返回所在位置}else if(L.elem[mid] key){high mid - 1; //从前半部分继续查找}else{low mid 1; //从后半部分继续查找}}return -1; //查找失败返回-1
}折半查找的过程可用二叉树来描述称为判定树。 我们知道具有n个结点的二叉树的深度为⌈ log2(n1)⌉所以折半查找的时间复杂度为O(log2n)平均情况下比顺序查找的效率高。 因为折半查找需要方便地定位查找区域所以它要求线性表必须具有随机存取的特性。因此该查找法仅适合于顺序存储结构不适合于链式存储结构且要求元素按关键字有序排列。
二、插值查找
现在我们的新问题是为什么一定要折半而不是折四分之一或者折更多呢? 比如要在取值范围0 ~ 10000之间100个元素从小到大均匀分布的数组中查找5我们自然会考虑从数组下标较小的开始查找。 所以折半查找还是有改善空间的。 上述折半查找代码的第4行等式变换后可得到 mid(lowhigh)/2 low(high-low)/2 也就是m i d midmid等于最低下标low加上最高下标high与low 的差的一半。大佬们考虑的就是将这个1/2进行改进改进为下面的计算方案 midlow(high−low){(key−a[low])/(a[high]−a[low])} 也就是说我们把上述折半查找代码的第4行的代码改为
mid low(key-L.elem[low])/(L.elem[high] - L.elem[low]) * (high-low); //插值就得到了另一种有序表查找算法插值查找法。插值查找(Interpolation Search) 是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法其核心就在于插值的计算公式。应该说从时间复杂度来看它也是O(log2n)但对于表长较大而关键字分布又比较均匀的查找表来说插值查找算法的平均性能比折半查找要好得多。反之数组中如果分布类似0 , 1 , 2 , 2000 , 2001 , . . . . . . , 999998 , 99999 {0,1,2,2000,2001,…,999998, 99999}0,1,2,2000,2001,…,999998,99999这种极端不均匀的数据用插值查找未必是很合适的选择。
三、斐波那契查找
斐波那契查找(Fibonacci Search)它是利用了黄金分割原理来实现的。
关于斐波那契数列不了解的可点击这里做一个大致的了解
我们先定义一个斐波那契数组F
算法实现如下
/*斐波那契查找*/
int Fibonacci_Search(int *a, int n, int key){int low, high, mid, i, k;low 0; //定义最低下标为记录首位high n; //定义最高下标为记录末尾k 0;while(n F[k] - 1){//计算n位于斐波那契数列的位置k;}for(in; iF[k]; i){//在尾部补上F[k]-n-1个数大小等于尾部最大值否则会存在数组溢出a[i]a[n];}while(low hight){mid low F[k-1]-1; //计算当前分隔的下标if(key a[mid]){//若查找记录小于当前分隔记录hight mid - 1; //最高下标调整到分隔下标mid-1处k k - 1; //斐波那契数列下标减一位}else if(key a[mid]){//若查找记录大于当前分隔记录low mid 1; //最低下标调整到分隔下标mid1处k k - 2; //斐波那契数列下标减两位}else{if(mid n){return mid; //若相等则说明mid即为查找的位置}else{return n; //若midn说明是补全数值返回n}}}return -1;
}斐波那契查找算法的核心在于:
当keya[mid]时查找就成功当keya[mid]时新范围是第low个到第mid-1个此时范围个数为F[k-1]-1个当keya[mid]时新范围是第m1个到第high个此时范围个数为F[k-2]-1个。
也就是说如果要查找的记录在右侧则左侧的数据都不用再判断了不断反复进行下去对处于当中的大部分数据其工作效率要高一些而且斐波那契查找只是最简单加减法运算所以尽管斐波那契查找的时间复杂也为O ( l o g n ) O(logn)O(logn)但就平均性能来说斐波那契查找要优于折半查找。不过如果是最坏情况比如这里key1那么始终都处于左侧长半区在查找则查找效率要低于折半查找。
线性索引查找
现实生活中计算机要处理的数据量是极其庞大的而数据结构的最终目的是提高数据的处理速度索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程 一个索引由若干个索引项构成每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。 索引按照结构可以分为线性索引、树形索引和多级索引。
这里主要介绍线性索引所谓线性索引就是将索引项集合组织为线性结构也称为索引表。我们重点介绍三种线性索引稠密索引、分块索引和倒排索引。
一、稠密索引
稠密索引是很简单直白的一种索引结构。 稠密索引是指在线性索引中将数据集中的每个记录对应一个索引项而索引项一定是按照关键码有序的排列。如下图所示
索引项有序也就意味着我们要查找关键字时可以用到折半、插值、斐波那契等有序查找算法提高了效率。这是稠密索引优点但是如果数据集非常大比如上亿那也就意味着索引也得同样的数据集长度规模对于内存有限的计算机来说可能就需要反复去访问磁盘查找性能反而大大下降了。
二、分块索引
稠密索引因为索引项与数据集的记录个数相同所以空间代价很大。为了减少索引项的个数我们可以对数据集进行分块使其分块有序然后再对每一块建立一个索引项从而减少索引项的个数。
分块有序是把数据集的记录分成了若千块并且这些块需要满足两个条件
块内无序即每一块内的记录不要求有序。块间有序例如要求第二块所有记录的关键字均要大于第一块中所有记录的关键字第三块的所有记录的关键字均要大于第二块的所有记录关键字…因为只有块间有序才有可能在查找时带来效率。
对于分块有序的数据集将每块对应一个索引项 这种索引方法叫做分块索引。如下图所示我们定义的分块索引的索引项结构分三个数据项
最大关键码它存储每一块中的最大关键字这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大块长存储了块中的记录个数以便于循环时使用块首指针用于指向块首数据元素的指针便于开始对这一块中记录进行遍历。
在分块索引表中查找就是分两步进行:
在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的因此很容易利用折半、插值等算法得到结果。例如在上图的数据集中查找62我们可以很快可以从左上角的索引表中由576296得到62在第三个块中。根据块首指针找到相应的块并在块中顺序查找关键码。
我们来分析一下它的平均查找长度 分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的 平均查找长度分别为LI , LS则分块查找的平均查找长度为 ALSLILS 我们假设将长度为n nn的查找表均匀地分为b bb块每块有s ss个记录即b n / s bn/sbn/s在等概率情况下若在块内和索引表中均采用顺序查找则平均查找长度为 ASLLILS(b1)/2 (s1)/2 (s^22sn)/2s此时若s √n 则平均查找长度取最小值√n 1 若对索引表采用折半查找时则平均查找长度为 ASLLILS⌈log2(b1)⌉ (s1)/2
三、倒排索引
搜索引擎中涉及很多搜索技术这里介绍一种最简单也是最基础的搜索技术倒排索引。
我们举个简单的例子 假如下面两篇极短的文章。
Books and friends should be few but good.A good book is a good friend. 忽略字母大小写我们统计出每个单词出现在哪篇文章之中文章1、文章2、文章(12)得到下面这个表并对单词做了排序
有了这样一张单词表我们要搜索文章就非常方便了。如果你在搜索框中填写“book关键字。系统就先在这张单词表中有序查找“book 找到后将它对应的文章编号1和2的文章地址返回。
在这里这张单词表就是索引表索引项的通用结构是
次关键码例如上面的“英文单词”记录号表例如上面的“文章编号。
其中记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或者是该记录的主关键字)。这样的索引方法就是倒排索引(inverted index) 。
这名字为什么要叫做“倒排索引”呢 顾名思义倒排索引源于实际应用中需要根据属性(或字段、次关键码)的值来查找记录或主关键编码。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值而是由属性值来确定记录的位置因而称为倒排索引。
当然现实中的搜索技术是非常复杂的要考虑诸多因素用到诸多技术由于本文的侧重点并非搜索引擎所以于此不再赘述。
二叉树排序与平衡二叉树
一、二叉排序树
1、定义
二叉排序树(也称二叉查找树)或者是一棵空树或者是具有下列特性的二叉树:
若左子树非空则左子树上所有结点的值均小于根结点的值。若右子树非空则右子树上所有结点的值均大于根结点的值。左、右子树也分别是一棵二叉排序树。
根据二叉排序树的定义左子树结点值根结点值右子树结点值所以对二叉排序树进行中序遍历可以得到一个递增的有序序列。例如下图所示二叉排序树的中序遍历序列为123468。
2、二叉排序树的常见操作
构造一个二叉树的结构
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode
{int data; //结点数据struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *Bitree;1查找操作
/*
递归查找二叉排序树T中是否存在key
指针f指向T的双亲其初始调用值为NULL
若查找成功则指针p指向该数据元素结点并返回TRUE
否则指针p指向查找路径上访问的最后一个结点并返回FALSE
*/
bool SearchBST(BiTree T, int key, BiTree f, BiTree *p){if(!T){*p f;return FALSE;}else if(key T-data){//查找成功*p T;return TRUE;}else if(key T-data){return SearchBST(T-lchild, key, T, p); //在左子树继续查找}else{return SearchBST(T-rchild, key, T, p); //在右子树继续查找}
}2插入操作 有了二叉排序树的查找函数那么所谓的二叉排序树的插入其实也就是将关键字放到树中的合适位置而已。
/*
当二叉排序树T中不存在关键字等于key的数据元素时
插入key并返回TRUE否则返回FALSE
*/
bool InsertBST(BiTree *T, int key){BiTree p, s;if(!SearchBST(*T, key, NULL, p)){//查找不成功s (BiTree)malloc(sizeof(BiTNode));s-data key;s-lchild s-rchild NULL;if(!p){*T s; //插入s为新的根节点}else if(key p-data){p-lchild s; //插入s为左孩子}else{p-rchild s; //插入s为右孩子}return TRUE;}else{return FALSE; //树种已有关键字相同的结点不再插入}
}有了二叉排序树的插入代码我们要实现二叉排序树的构建就非常容易了几个例子
int i;
int a[10] {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T NULL;
for(i 0; i10; i){InsertBST(T, a[i]);
}上面的代码就可以创建一棵下图这样的树。
3删除操作 二叉排序树的查找和插入都很简单但是删除操作就要复杂一些此时要删除的结点有三种情况
叶子结点仅有左或右子树的结点左右子树都有的结点
前两种情况都很简单第一种只需删除该结点不需要做其他操作第二种删除后需让被删除结点的直接后继接替它的位置复杂就复杂在第三种此时我们需要遍历得到被删除结点的直接前驱或者直接后继来接替它的位置然后再删除。 第三种情况如下图所示 代码如下
/*
若二叉排序树T中存在关键字等于key的数据元素时则删除该数据元素结点
并返回TRUE;否则返回FALSE
*/
bool DeleteBST(BiTree *T, int key){if(!T){return FALSE; }else{if(key T-data){//找到关键字等于key的数据元素return Delete(T);}else if(key T - data){return DeleteBST(T - lchild, key);}else{return DeleteBST(T - rchild, key);}}
}下面是Delete()方法
/*从二叉排序树中删除结点p并重接它的左或右子树。*/
bool Delete(BiTree *p){BiTree q, s;if(p-rchild NULL){//右子树为空则只需重接它的左子树q p;p p-lchild;free(q);}else if(p-lchild NULL){//左子树为空则只需重接它的右子树q p;p p-rchild;free(q);}else{//左右子树均不空q p;s p-lchild; //先转左while(s-rchild){//然后向右到尽头找待删结点的前驱q s;s s-rchild;}//此时s指向被删结点的直接前驱p指向s的父母节点p-data s-data; //被删除结点的值替换成它的直接前驱的值if(q ! p){q-rchild s-lchild; //重接q的右子树}else{q-lchild s-lchild; //重接q的左子树}pree(s);}return TRUE;
}3、性能分析
二叉排序树的优点明显插入删除的时间性能比较好。而对于二叉排序树的查找走的就是从根结点到要查找的结点的路径其比较次数等于给定值的结点在二叉排序树的层数。极端情况最少为1次即根结点就是要找的结点最多也不会超过树的深度。也就是说二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于二叉排序树的形状是不确定的。 例如{ 62 , 88 , 58 , 47 , 35 , 73 , 51 , 99 , 37 , 93 } {62,88,58,47,35,73,51,99,37,93}{62,88,58,47,35,73,51,99,37,93}这样的数组我们可以构建如下左图的二叉排序树。但如果数组元素的次序是从小到大有序如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树如下面右图的二叉排序树
也就是说我们希望二叉排序树是比较平衡的即其深度与完全二叉树相同那么查找的时间复杂也就为O(logn)近似于折半查找。 不平衡的最坏情况就是像上面右图的斜树查找时间复杂度为O(n)这等同于顺序查找。 因此如果我们希望对一个集合按二叉排序树查找最好是把它构建成一棵平衡的二叉排序树。
二、平衡二叉树
1、定义
平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一种二叉排序树其中每一个节点的左子树和右子树的高度差至多等于1。
它是一种高度平衡的二叉排序树。它要么是一棵空树 要么它的左子树和右子树都是平衡二叉树且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) 那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1则该二叉树就是不平衡的。
2、平衡二叉树的查找
在平衡二叉树上进行查找的过程与二叉排序树的相同。因此在查找过程中与给定值进行比较的关键字个数不超过树的深度。假设以nh表示深度为h的平衡树中含有的最少结点数。显然有 n00,n11,n22n 并且有nhnh-1}nh-21。可以证明含有n nn个结点的平衡二叉树的最大深度为O ( l o g 2 n ) O(log2n)O(log2n)因此平衡二叉树的平均查找长度为O(log2n) 如下图所示。
3、平衡二叉树的插入
二叉排序树保证平衡的基本思想如下每当在二叉排序树中插入(或删除)一个结点时首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A再对以A为根的子树在保持二叉排序树特性的前提下调整各结点的位置关系使之重新达到平衡。
注意:每次调整的对象都是最小不平衡子树即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。
平衡二叉树的插入过程的前半部分与二叉排序树相同但在新结点插入后若造成查找路径上的某个结点不再平衡则需要做出相应的调整。可将调整的规律归纳为下列4种情况 LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点A的平衡因子由1增至2导致以A为根的子树失去平衡需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点将A结点向右下旋转成为B的右子树的根结点而B的原右子树则作为A结点的左子树。 如下图所示结点旁的数值代表结点的平衡因子而用方块表示相应结点的子树下方数值代表该子树的高度。 RR平衡旋转(左单旋转)。由于在结点A的右孩子®的右子树®上插入了 新结点A的平衡因子由-1减至-2导致以A为根的子树失去平衡需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点将A结点向左下旋转成为B的左子树的根结点而B的原左子树则作为A结点的右子树。 LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树®上插入新结点A的平衡因子由1增至2导致以A为根的子树失去平衡需要进行两次旋转操作先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置即进行一次RR平衡旋转(左单旋转)然后再把该C结点向右上旋转提升到A结点的位置即进行一次LL平衡旋转(右单旋转)。 RL平衡旋转(先右后左双旋转)。由于在A的右孩子®的左子树(L)上插入新结点A的平衡因子由-1减至-2导致以A为根的子树失去平衡需要进行两次旋转操作先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置即进行一次LL平衡旋转(右单旋转)然后再把该C结点向左上旋转提升到A结点的位置即进行一次RR平衡旋转(左单旋转)。 注意: LR和RL旋转时新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程而上图中是以插入C的左子树中为例。 举个例子 假设关键字序列为15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8}15,3,7,10,9,8通过该序列生成平衡二叉树的过程如下图所示。 多路查找树
多路查找树(muitl-way search tree) 其每一个结点的孩子数可以多于两个且每一个结点处可以存储多个元素。由于它是查找树所有元素之间存在某种特定的排序关系。 在这里每一个结点可以存储多少个元素以及它的孩子数的多少是非常关键的。常见的有4种特殊形式2-3树、2-3-4树、B树和B树。这里主要介绍B树和B树因为2-3树、2-3-4树都是B树的特例。 如下图所示是一颗2-3树 一、B树
1、定义
B树又称多路平衡查找树B树中所有结点的孩子个数的最大值称为B树的阶通常用m表示。一棵m m阶B树或为空树或为满足如下特性的m叉树
树中每个结点至多有m mm棵子树即至多含有m−1个关键字。若根结点不是终端结点则至少有两棵子树。除根结点外的所有非叶结点至少有⌈m/2⌉棵子树即至少含有⌈m/2⌉−1个关键字。所有非叶结点的结构如下
其中Ki(i1,2,…,n)为结点的关键字且满足K1K2…KnPi (i0,1,…,n)为指向子树根结点的指针且指针Pi−1 所指子树中所有结点的关键字均小于Ki 所指子树中所有结点的关键字均大于Ki即符合二叉排序树的左小右大n(⌈m/2⌉−1≤n≤m−1)为结点中关键字的个数。
所有的叶结点都出现在同一层次上并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失败结点实际上这些结点不存在指向这些结点的指针为空)。
B树是所有结点的平衡因子均等于0的多路平衡查找树。 下图所示的B树中所有结点的最大孩子数m 5 m5m5因此它是一棵5阶B树在m mm阶B树中结点最多可以有m mm个孩子。可以借助该实例来分析上述性质
结点的孩子个数等于该结点中关键字个数加1每一个空隙都存在一个分支。如果根结点没有关键字就没有子树此时B树为空如果根结点有关键字则其子树必然大于等于两棵因为子树个数等于关键字个数加1。除根结点外的所有非终端结点至少有⌈ m / 2 ⌉ ⌈ 5 / 2 ⌉ 3 ⌈m/2⌉⌈5/2⌉3⌈m/2⌉⌈5/2⌉3棵子树(即至少有⌈ m / 2 ⌉ − 1 ⌈ 5 / 2 ⌉ − 1 2 ⌈m/2⌉- 1⌈5/2⌉-12⌈m/2⌉−1⌈5/2⌉−12个关键字)至多有5棵子树(即至多有4个关键字)。结点中关键字从左到右递增有序关键字两侧均有指向子树的指针左边指针所指子树的所有关键字均小于该关键字右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内如第二层最左结点的关键字划分成了3个区间( − ∞ , 5 ) , ( 5 , 11 ) , ( 11 , ∞ ) (-∞, 5),(5, 11),(11, ∞)(−∞,5),(5,11),(11,∞)该结点3个指针所指子树的关键字均落在这3个区间内。所有叶结点均在第4层代表查找失败的位置。
2、B树与磁盘存取
B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。
我们的外存比如硬盘 是将所有的信息分割成相等大小的页面每次硬盘读写的都是一个或多个完整的页面对于一个硬盘来说一页的长度可能是211到214个字节。 在一个典型的B树应用中要处理的硬盘数据量很大因此无法一次全部装入内存。因此我们会对B树进行调整使得B树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001 (即1个结点包含1000个关键字)高度为2它可以储存超过10亿个关键字我们只要让根结点持久地保留在内存中那么在这棵树上寻找某一个关键字至多需要两次硬盘的读取即可。 通过这种方式在有限内存的情况下每一次磁盘的访问我们都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素所以与二叉树的操作不同它们减少了必须访问结点和数据块的数量从而提高了性能。可以说B树的数据结构就是为内外存的数据交互准备的。
3、B树的查找
在B树上进行查找与二叉查找树很相似只是每个结点都是多个关键字的有序表在每个结点上所做的不是两路分支决定而是根据该结点的子树所做的多路分支决定。 B树的查找包含两个基本操作①在B树中找结点②在结点内找关键字。由于B树常存储在磁盘上因此前一个查找操作是在磁盘上进行的而后一个查找操作是在内存中进行的即在找到目标结点后先将结点信息读入内存然后在结点内采用顺序查找法或折半查找法。 在B树上查找到某个结点后先在有序表中进行查找若找到则查找成功否则按照对应的指针信息到所指的子树中去查找。
例如在上图中查找关键字42 4242首先从根结点开始根结点只有一个关键字且42 22 42224222若存在必在关键字22 2222的右边子树上右孩子结点有两个关键字而36 42 45 36 42 45364245则若存在必在36 3636和45 4545中间的子树上在该子结点中查到关键字42 4242查找成功。若查找到叶结点时对应指针为空指针则说明树中没有对应的关键字查找失败。
4、B树的插入
与二叉查找树的插入操作相比B树的插入操作要复杂得多。在二叉査找树中仅需査找到需插入的终端结点的位置。但是在B树中找到插入的位置后并不能简单地将其添加到终端结点中因为此时可能会导致整棵树不再满足B树定义中的要求。将关键字key插入B树的过程如下
定位。利用前述的B树査找算法找出插入该关键字的最低层中的某个非叶结点(在B树中查找key时,会找到表示查找失败的叶结点,这样就确定了最底层非叶结点的插入位置。注意插入位置一定是最低层中的某个非叶结点)。插入。在B树中每个非失败结点的关键字个数都在区间[⌈m/2⌉−1,m−1]内。插入后的结点关键字个数小于m可以直接插入插入后检查被插入结点内关键字的个数当插入后的结点关键字个数大于m−1时必须对结点进行分裂。
分裂的方法是取一个新结点在插入key后的原结点从中间位置⌈m/2⌉将其中的关键字分为两部分左部分包含的关键字放在原结点中右部分包含的关键字放到新结点中中间位置⌈m/2⌉的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限则继续进行这种分裂操作直至这个过程传到根结点为止,进而导致B树高度增1。 对于m3的B树所有结点中最多有m−12个关键字若某结点中已有两个关键字则结点已满如下图a所示。插入一个关键字60后结点内的关键字个数超过了m−1如图b所示此时必须进行结点分裂分裂的结果如图c所示。 通俗点讲B树的插入结点不溢出时好说直接插入如果结点溢出那就分裂并把中间结点合并到父节点。
5、B树的删除
B树中的删除操作与插入操作类似但要更复杂一些即要使得删除后的结点中的关键字个数≥⌈m/2⌉−1因此将涉及结点的“合并”问题。 当被删关键字k不在终端结点(最低层非叶结点)中时可以用k的前驱(或后继) k ′ 来替替代k然后在相应的结点中删除k ′ 关键字k ′必定落在某个终端结点中则转换成了被删关键字在终端结点中的情形。在下图的B树中删除关键字80用其前驱78替代然后在终端结点中删除78。因此只需讨论删除终端结点中关键字的情形。 当被删关键字在终端结点(最低层非叶结点)中时有下列三种情况: ① 直接删除关键字。若被删除关键字所在结点的关键字个数≥⌈m/2⌉表明删除该关键字后仍满足B树的定义则直接删去该关键字。 ② 兄弟够借。若被删除关键字所在结点删除前的关键字个数⌈m/2⌉−1且与此结点相邻的右(或左)兄弟结点的关键字个数≥⌈m/2⌉则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)以达到新的平衡。在图(a)中删除B树的关键字65 6565右兄弟关键字个数≥⌈m/2⌉2将71取代原65的位置将74调整到71的位置。
③ 兄弟不够借。若被删除关键字所在结点删除前的关键字个数⌈m/2⌉−1且此时与该结点相邻的左、右兄弟结点的关键字个数均⌈m/2⌉−1则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并。在图(b)中删除B树的关键字5它及其右兄弟结点的关键字个数⌈m/2⌉−11故在5 55删除后将60合并到65结点中。 在合并过程中双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0 (根结点关键字个数为1时有2棵子树)则直接将根结点删除合并后的新结点成为根若双亲结点不是根结点且关键字个数减少到⌈m/2⌉−2则又要与它自己的兄弟结点进行调整或合并操作并重复上述步骤直至符合B树的要求为止。
其实通俗点讲B树的删除删除结点无非就是多留少补的情况多留不必多说少补复杂点当兄弟够借时就向左旋转一次即往左挪一个位置重构根节点关键字的前驱和后继当兄弟不够借时就拆根节点合并到兄弟结点合并拆分要始终保证B树平衡理清了就很容易理解。
二、B树
尽管B树的诸多好处但其实它还是有缺陷的。对于树结构来说我们都可以通过中序遍历来顺序查找树中的元素这一切都是在内存中进行。可是在B树结构中我们往返于每个结点之间也就意味着我们必须得在硬盘的页面之间进行多次访问。
如上图所示。我们希望遍历这棵B树假设每个结点都属于硬盘的不同页面我们中序遍历所有的元素
页面2→页面1→页面3→页面1→页面4→页面1→页面5
而且我们每次经过结点遍历时都会对结点中的元素进行一次遍历这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢? B树来了。
1、定义
B树是应文件系统比如数据库所需而出现的一种B树的变形树。
m阶的B树与m阶的B树的主要差异如下
有n棵子树的结点中包含有n个关键字;所有的叶子结点包含全部关键字的信息及指向含这些关键字记录的指针叶子结点本身依关键字的大小自小而大顺序链接;所有分支结点可以看成是索引结点中仅含有其子树中的最大(或最小)关键字。在B树中每个结点(非根内部结点)的关键字个数n的范围是⌈m/2⌉≤n≤m(根结点1≤n≤m)在B树中每个结点(非根内部结点)的关键字个数n nn范围是⌈m/2⌉−1≤n≤m−1 (根结点:1≤n≤m−1)。
下图所示为一棵4阶B树。
B树的结构特别适合带有范围的查找。比如查找我们学校18~22岁的学生人数我们可以通过从根结点出发找到第一个18岁的学生然后再在叶子结点按顺序查找到符合范围的所有记录。 B树的插入、删除过程也都与B树类似只不过插入和删除的元素都是在叶子结点上进行而已。 散列表查找哈希表
一、散列表查找的基本概念
散列表是根据关键字而直接进行访问的数据结构。也就是说散列表建立了关键字和存储地址之间的一种直接映射关系。我们只需要通过某个函数f使得 存储位置f(关键字) 那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。
散列技术既是一种存储方法 也是一种查找方法散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置f ( k e y ) f(key)f(key)。查找时根据这个确定的对应关系找到置上。
这里我们把这种对应关系f ff称为散列函数又称为哈希(Hash) 函数。按这个思想采用散列技术将记录存储在一块连续的存储空间中这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。
散列函数可能会把两个或两个以上的不同关键字映射到同一地址称这种情况为冲突这些发生碰撞的不同关键字称为同义词。一方面设计得好的散列函数应尽量减少这样的冲突另一方面由于这样的冲突总是不可避免的所以还要设计好处理冲突的方法。
理想情况下对散列表进行查找的时间复杂度为O ( 1 ) O(1)O(1)即与表中元素的个数无关。
二、散列函数的构造方法
在构造散列函数时必须注意以下几点
散列函数的定义域必须包含全部需要存储的关键字而值域的范围则依赖于散列表的大小或地址范围。散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中从而减少冲突的发生。散列函数应尽量简单能够在较短的时间内计算出任一关键字对应的散列地址。
下面介绍常用的散列函数。
1、直接定址法
直接取关键字的某个线性函数值为散列地址散列函数为
H(key)key或H(key)a∗keyb
式中a和b是常数。这种方法计算最简单且不会产生冲突。它适合关键字的分布基本连续的情况若关键字分布不连续空位较多则会造成存储空间的浪费。 举例0~100岁的人口数字统计表可以吧年龄数值直接当做散列地址。
2、数字分析法
例如当手机号码为关键字时其11位数字是有规则的此时是无需把11位数值全部当做散列地址这时我们给关键词抽取 抽取方法是使用关键字的一部分来计算散列存储位置的方法这在散列函数中是常常用到的手段。 数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀就可以考虑用这个方法。这种方法适合于已知的关键字集合若更换了关键字则需要重新构造新的散列函数。
3、平方取中法
这个方法计算很简单假设关键字是1234那么它的平方就是1522756再抽取中间的3位就是227用做散列地址。再比如关键字是4321那么它的平方就是18671041抽取中间的3位就可以是671也可以是710用做散列地址。平方取中法比较适合于不知道关键字的分布而位数又不是很大的情况。
4、除留余数法
这是一种最简单、最常用的方法假定散列表表长为m mm取一个不大于m mm但最接近或等于m mm的质数p pp利用以下公式把关键字转换成散列地址。散列函数为
H(key)key%p (pm)
事实上这方法不仅可以对关键字直接取模也可在折叠、平方取中后再取模。 除留余数法的关键是选好p pp使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址从而尽可能减少冲突的可能性。
5、随机数法 选择一个随机数取关键字的随机函数值为它的散列地址。也就是
H(key)random(key)
这里random是随机函数。当关键字的长度不等时采用这个方法构造散列函数是比较合适的。
三、处理散列冲突
任何设计出来的散列函数都不可能绝对地避免冲突。为此必须考虑在发生冲突时应该如何处理即为产生冲突的关键字寻找下一个“空”的Hash地址。
用Hi表示处理冲突中第i ii次探测得到的散列地址假设得到的另一个散列地址H1 仍然发生冲突只得继续求下一个地址H2以此类推直到Hk 不发生冲突为止则Hk为关键字在表中的地址。
1、开放定址法
所谓的开放定址法就是一旦发生了冲突就去寻找下一个空的散列地址只要散列表足够大空的散列地址总能找到并将记录存入。 它的公式是 Hi ( key ) ( f ( key ) di ) % m ( di 1 , 2 , 3 , . . . , m − 1 ) (d_i1,2,3,…,m-1) 式中H(key)为散列函数i0,1,2,…,k (km−1)m表示散列列表表长di为增量序列。
取定某一增量序列后对应的处理方法就是确定的。通常有以下4种取法
线性探测法。当di i0,1,2,…, m-1时称为线性探测法。这种方法的特点是:冲突发生时顺序查看表中下一个单元(探测到表尾地址m−1时下一个探测地址是表首地址0)直到找出一个空闲单元(当表未填满时一定能找到一个空闲单元)或查遍全表。 线性探测法可能使第i个散列地址的同义词存入第i1个散列地址这样本应存入第i1个散列地址的元素就争夺第i2个散列地址的元素的地址从而造成大量元素在相邻的散列地址上堆积大大降低了查找效率。平方探测法。当di02,12,-12,22,-22,…,k2, -k2 时称为平方探测法其中km/2散列表长度m必须是一个可以表示成4k3的素数又称二次探测法。 平方探测法是一种较好的处理冲突的方法可以避免出现“堆积”问题它的缺点是不能探测到散列表上的所有单元但至少能探测到一半单元。再散列法。当 di Hash2(key))时称为再散列法又称双散列法。需要使用两个散列函数当通过第一个散列函数H(key)得到的地址发生冲突时则利用第二个散列函数Hash2(key)计算该关键字的地址增量。它的具体散列函数形式如下 Hi (H(key) i*Hash2(key)) % m 初始探测位置 H0 H(key)。i是冲突的次数初始为0。在再散列法中最多经过m−1次探测就会遍历表中所有位置回到H0位置。伪随机序列法。当di伪随机数序列时称为伪随机序列法。 注意:在开放定址的情形下不能随便物理删除表中的已有元素因为若删除元素则会截断其他具有相同散列地址的元素的查找地址。因此要删除一个元素时可给它做一个删除标记进行逻辑删除。但这样做的副作用是执行多次删除后表面上看起来散列表很满实际上有许多位置未利用因此需要定期维护散列表要把删除标记的元素物理删除。 2、链地址法拉链法
不换地方。 转换一下思路为什么非得有冲突就要换地方呢如果不换地方该怎么处理于是我们就有了链地址法。
将所有关键字为同义词的记录存储在一个单链表中我们称这种表为同义词子表在散列表中只存储所有同义词子表的头指针。
例如关键字序列为{12,67,56,16,25,37,22,29,15,47,48,34}我们用除留余数法构造散列函数H (key)key%12用拉链法处理冲突建立的表如下图所示。 3、公共溢出区法
这个方法其实就更加好理解就是把凡是冲突的家伙额外找个公共场所待着。我们为所有冲突的关键字建立了一个公共的溢出区来存放。
就前面的例子而言我们共有三个关键字37 , 48 , 34 {37,48,34}37,48,34与之前的关键字位置有冲突那么就将它们存储到溢出表中如下图所示。
如果相对于基本表而言有冲突的数据很少的情况下公共溢出区的结构对查找性能来说还是非常高的。
四、散列表查找实现
1、算法
首先是需要定义一个散列表的结构以及一些相关的常数。其中HashTable就是散列表结构。结构当中的elem为一个动态数组。
#define SUCCESS 1;
#define UNSUCCESS 0;
#define HASHSIZE 12; //定义散列表表长为数组的长度
#define NULLKEY -32768; //代表空地址
typedef struct{int *elem; //数组元素存储基址动态分配数组int count; //当前数据元素个数
}HashTable;
int m0; //散列表表长全局变量有了结构的定义我们可以对散列表进行初始化。
/*初始化散列表*/
bool InitHashTable(HashTable *H){int i;mHASHSIZE;H-countm;H-elem(int *)malloc(m*sizeof(int));for(i0; im; i){H-elem[i]NULLKEY;}return TRUE;
}为了插入时计算地址我们需要定义散列函数散列函数可以根据不同情况更改算法。
/*散列函数*/
int Hash(int key){return key % m; //除留余数法
}初始化完成后我们可以对散列表进行插入操作。假设我们插入的关键字集合就是前面的{12,67,56,16,25,37,22,29,15,47,48,34}。
/*插入关键字进散列表*/
void InsertHash(HashTable *H, int key){int addr Hash(key); //通过散列函数求散列地址//如果不为空。则冲突while (H-elem[addr] ! NULLKEY){addr (addr 1) % m; //开放定址法的线性探测}H-elem[addr] key; //直到有空位后插入关键字
}代码中插入关键字时首先算出散列地址如果当前地址不为空关键字则说明有冲突。此时我们应用开放定址法的线性探测进行重新寻址此处也可更改为链地址法等其他解决冲突的办法。
散列表存在后我们在需要时就可以通过散列表查找要的记录。
/*
散列表查找关键字
找到后用addr保存地址
*/
bool SerachHash(HashTable H, int key, int *addr){*addr Hash(key); //通过散列函数求得散列地址//如果不为空则有同义词冲突while(H.elem[*addr] ! key){*addr (*addr1) % m; //开放地址法的线性探测if(H.elem[*addr] NULLKEY || *addr Hash(key)){//如果循环到空址或回到原点return FALSE; //则说明关键字不存在}}return TRUE;
}查找的代码与插入的代码非常类似只需做一个不存在关键字的判断而已。
2、性能分析
从散列表的查找过程可见
虽然散列表在关键字与记录的存储位置之间建立了直接映像但由于“冲突”的产生使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此仍需要以平均查找长度作为衡量散列表的查找效率的度量。散列表的查找效率取决于三个因素散列函数、处理冲突的方法和装填因子。若用ci 表示每一个关键字查找的次数则平均查找次数可表示为
装填因子。散列表的装填因子一般记为α定义为一个表的装满程度即
αn (表中记录数)/m (散列表长度)
散列表的平均查找长度依赖于散列表的装填因子α \alphaα而不直接依赖于n nn或m mm。直观地看α \alphaα越大表示装填的记录越“满”发生冲突的可能性越大反之发生冲突的可能性越小。
不管记录个数n nn有多大我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内此时我们散列查找的时间复杂度就真的是O ( 1 ) O(1)O(1)了。 为了做到这一点通常我们都是将散列表的空间设置得比查找集合大此时虽然是浪费了一定的空间但换来的是查找效率的大大提升总的来说还是非常值得的。
附录
数据结构系列文章 什么是链表并用代码手动实现一个单向链表 单向循环链表增加元素、删除元素、打印循环链表等功能 什么是双向链表并用代码手动实现一个双向链表 什么是双向循环链表以及实现过程 线性表–栈和队列 线性表–list详解建议收藏 线性表–数组 树(Tree) 图(Graph)
数据结构与算法专栏
数据结构专栏
参考资料 1、严蔚敏、吴伟民《数据结构C语言版》 2、程杰《大话数据结构》 3、王道论坛《数据结构考研复习指导》 4、托马斯·科尔曼等人《算法导论》
