7.1 查找的基本概念
查找。在数据聚集中探求满足某种条件的数据元素的过程称为查找。查找的结果一样平常分为两种：一是查找成功，即在数据聚集中找到了满足条件的数据元素；二是查找失败。
平均查找长度。在查找过程中，一次查找的长度是指需要比力的关键字次数，而平均查找长度则是所有查找过程中举行关键字的比力次数的平均值，其数学界说为
式中，n是查找表的长度；P;是查找第i个数据元素的概率，一样平常以为每个数据元素的查找概率相称，即P;=1/n;C;是找到第i个数据元素所需举行的比力次数。平均查找长度是衡量查找算法服从的最主要的指标。
7.2 顺序查找和折半查找
7.2.1 顺序查找
顺序查找又称线性查找，它对顺序表和链表都是实用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针 next 来依次扫描每个元素。顺序查找通常分为对一样平常的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。
7.2.2 折半查找
折半查找又称二分查找，它仅实用于有序的顺序表。
折半查找的基本思想：①首先将给定值 key与表中中间位置的元素比力，若相称，则查找成功，返回该元素的存储位置；②若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分(比方，在查找表升序排列时，若 key大于中间元素，则所查找的元素只可能在后半部分),然后在缩小的范围内继续举行同样的查找。重复上述步调，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
折半查找的过程可用图7.2所示的二叉树来描述，称为判定树。树中每个圆形结点表示一个记载，结点中的值为该记载的关键字值；树中最下面的叶结点都是方形的，它表示查找失败的区间。
7.2.3分块查找
分块查找又称索引顺序查找，它罗致了顺序查找和折半查找各自的长处，既有动态布局，又适于快速查找。
分块查找的基本思想：将查找表分为多少子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记载的关键字，第二个块中的最大关键字小于第三个块中的所有记载的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
分块查找的过程分为两步：第一步是在索引表中确定待查记载所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。
比方，关键码聚集为{88,24,72,61,21,6,32,11,8,31,22,83,78,54},按照关键码值24,54,78,88,分为4个块和索引表，如图7.3 所示。
7.3 树形查找
7.3.1二叉排序树(BST)
1.二叉排序树的界说
二叉排序树(也称二叉查找树)或者是一棵空树，或者是具有下列特性的二叉树：
- 若左子树非空，则左子树上所有结点的值均小于根结点的值。
- 若右子树非空，则右子树上所有结点的值均大于根结点的值。
- 左、右子树也分别是一棵二叉排序树。
2.二叉排序树的查找
二叉排序树的查找是从根结点开始，沿某个分支逐层向下比力的过程。若二叉排序树非空， 先将给定值与根结点的关键字比力，若相称，则查找成功；若不等，若小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。
3.二叉排序树的插入
插入结点的过程如下：若原二叉排序树为空，则直接插入；否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。如图 7.5 所示在一棵二叉排序树中依次插入结点 28 和结点 58,虚线表示的边是其查找的路径。
4.二叉排序树的构造
从一棵空树出发，依次输入元素，将它们插入二叉排序树中的符合位置。设查找的关键字序列为{45,24,53,45,12,24},则生成的二叉排序树如图7.6所示。
5.二叉排序树的删除
在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操纵的实现过程按3种环境来处置惩罚：
- 若被删除结点z是叶结点，则直接删除，不会粉碎二叉排序树的性质。
- 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，更换z的位置。
- 若结点z有左、右两棵子树，则令z的直接后继(或直接前驱)更换z,然后从二叉排序
树中删去这个直接后继(或直接前驱),这样就转换成了第一或第二种环境。
图7.7表现了在3种环境下分别删除结点45,78,78的过程。
6.二叉排序树的查找服从分析
二叉排序树的查找服从，主要取决于树的高度。若二叉排序树的左、右子树的高度之差的绝对值不凌驾1(均衡二叉树，下一节),它的平均查找长度为 O(logn)。若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表),则其平均查找长度为O(n)。
就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除作，平均实行时间为O(logn)。二分查找的对象是有序顺序表，如有插入和删除结点的操纵，所花的代价是O(n)。当有序表是静态查找表时，宜用顺序表作为其存储布局，而采用二分查找实现其找操纵；如有序表是动态查找表，则应选择二叉排序树作为其逻辑布局。
7.3.2均衡二叉树
1.均衡二叉树的界说
为了制止树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证恣意结点的左、右子树高度差的绝对值不凌驾1,将这样的二叉树称为均衡二叉树(BalancedBinary Tree),也称 AVL树。界说结点左子树与右子树的高度差为该结点的均衡因子，则均衡二叉树结点的均衡因子的值只可能是-1、0或1。
2.平街二叉树的插入
均衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径 上的某个结点不再均衡，则需要做出相应的调整。可将调整的规律归纳为下列4种环境：
LL均衡旋转(右单旋转)。
RR均衡旋转(左单旋转)。
LR均衡旋转(先左后右双旋转)。
L均衡旋转(先右后左双旋转)。
3.均衡二叉树的删除
与均衡二叉树的插入操纵类似，以删除结点w为例来说明均衡二叉树删除操纵的步调：
1)用二叉排序树的方法对结点w实行删除操纵。
2)若导致了不均衡，则从结点 w开始向上回溯，找到第一个不均衡的结点z(即最小不均衡子树);y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。
3)然后对以z为根的子树举行均衡调整，其中x、y和z可能的位置有4种环境：
- y是z的左孩子，x是y的左孩子(LL,右单旋转);
- y是z的左孩子，x是y的右孩子(LR,先左后右双旋转);
- y是z的右孩子，x是y的右孩子(RR,左单旋转);
- y是z的右孩子，x是y的左孩子(RL,先右后左双旋转)。
7.3.3红黑树
1.红黑树的界说
为了保持 AVL 树的均衡性，在插入和删除操纵后，会非常频繁地调整全树整体拓扑布局，代价较大。为此在 AVL树的均衡尺度上进一步放宽条件，引入了红黑树的布局。
一棵红黑树是满足如下红黑性质的二叉排序树：
- 每个结点或是赤色，或是黑色的。
- 根结点是黑色的。
- 叶结点(虚构的外部结点、NULL结点)都是黑色的。
- 不存在两个相邻的红结点(即红结点的父结点和孩子结点均是黑色的)。
- 对每个结点，从该结点到恣意一个叶结点的简单路径上，所含黑结点的数量相同。
7.4 B树和 B+树
7.4.1 B树及其基本操纵
所谓 m阶B树是所有结点的均衡因子均等于0的m路平街查找树。
一棵m阶B树或为空树，或为满足如下特性的m叉树：
- 树中每个结点至多有m棵子树，即至多有m-1个关键字。
- 若根结点不是叶结点，则至少有2棵子树，即至少有1个关键字。
- 除根结点外的所有非叶结点至少有「m/2]棵子树，即至少有「m/2]-1个关键字。
- 所有非叶结点的布局如下：
7.4.2 B+树的基本概念
B+树是应数据库所需而出现的一种 B树的变形树。
一棵m阶 B+树应满足下列条件：
- 每个分支结点最多有m棵子树(孩子结点)。
- 非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。
- 结点的子树个数与关键字个数相称。
- 所有叶结点包含全部关键字及指向相应记载的指针，叶结点中将关键字按巨细顺序排列，而且相邻叶结点按巨细顺序相互链接起来(支持顺序查找)。
- 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。
m阶 B+树与m阶B树的主要差异如下：
- 在 B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
- 在 B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出如今叶结点中：而在B树中，最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
- 在 B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有对应记载的存储地址。这样能使一个磁盘块存储更多的关键字，使得磁盘读/写次数更少，查找速率更快。
- 在 B+树中，用一个指针指向关键字最小的叶结点，将所有叶结点串成一个线性链表。
图7.32所示为一棵4阶B+树。可以看出，分支结点的关键字是其子树中最大关键字的副本。通常在 B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对B+树举行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。
B+树的查找、插入和删除操纵和 B 树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在 B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
