查找概论
查找（Searching） 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
查找表（SearchTable） 是由同一类型的数据元素（或记录）构成的集合
关键字（Key） 是数据元素中某个数据项的值，又称为 键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为 关键码。
主关键字（PrimaryKey）: 此关键字可以唯一地标识一个记录。
次关键字（SecondaryKey）: 可以识别多个数据元素（或记录）的关键字。
查找表按照操作方式来分有两类：静态查找表和动态查找表。
顺序表查找
定义
顺序查找（SequentialSearch） 又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
算法
int Sequential_Search(int *a, int n, int key)
{
int i;
for(i = 1; i <= n; i++)
{
if(a[i] == key)
return i;
}
return 0;
}
是在数组a（注意元素值从下标1开始）中查看有没有关键字（key），当你需要查找复杂表结构的记录时，只需要把数组a与关键字key定义成你需要的表结构和数据类型即可。
有序表查找
折半查找
折半查找（BinarySearch） 技术，又称为 二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。
折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
int Binary_Search(int *a, int n, int key)
{
int low, high, mid;
low = 1; /* 定义最低下标为记录首位 */
high = n; /* 定义最高下标为记录末位 */
while(low <= high)
{
mid = (low + high)/2; /* 取中间位置 */
if(key < a[mid]) /* 待查找的元素小于中间位置的元素 */
high = mid-1; /* 最高下标调整到中间位置的前一个位置 */
else if(key > a[mid]) /* 待查找的元素大于中间位置的元素 */
low = mid+1; /* 最低下标调整到中间位置的后一个位置 */
else
return mid; /* 找到待查找的元素，返回其下标 */
}
return 0; /* 查找失败，返回0 */
}
们折半算法的时间复杂度为0（logn），它显然远远好于顺序查找的0（m）时间复杂度。
插值查找
插值查找（InterpolationSearch） 是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式
我们只需要在折半查找算法的代码中更改一下第8行代码如下：
mid=low+(high-low)*)(key-a[low])/(a[high]-a[low]);/*插值*/
斐波那契查找
斐波那契查找（FibonacciSearch） 是一种有序查找，它是利用了黄金分割原理来实现的。
int Fibonacci_Search(int *a, int n, int key)
{
int low,high,mid,i,k;
low = 1; /* 定义最低下标为记录首位 */
high = n; /* 定义最高下标为记录末位 */
k = 0; /* 定义斐波那契数列的下标 */
while(n > F[k] - 1) /* 计算斐波那契数列的下标 */
k++;
for(i = n; i < F[k]; i++) /* 将数组扩展到斐波那契数列的长度 */
a[i] = a[n];
while(low <= high) {
mid = low + F[k - 1] - 1; /* 计算中间位置 */
if(key < a[mid]) { /* 如果关键字小于中间值 */
high = mid - 1; /* 调整最高下标 */
k -= 1; /* 调整斐波那契数列的下标 */
} else if(key > a[mid]) { /* 如果关键字大于中间值 */
low = mid + 1; /* 调整最低下标 */
k -= 2; /* 调整斐波那契数列的下标 */
} else { /* 如果关键字等于中间值 */
if(mid <= n) /* 检查中间位置是否在原数组范围内 */
return mid; /* 返回中间位置 */
else
return -1; /* 返回-1表示未找到 */
}
}
return 0;
}
线性索引查找
索引就是把一个关键字与它对应的记录相关联的过程。
所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。
稠密索引
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引。索引项一定是按照关键码有序的排列。
分块索引
分块索引是将数据集分成若干块的查找方法，具有以下特点：
- 块内无序：每一块内部的元素可以是无序的
- 块间有序：块与块之间按照某种顺序排列（通常是按块内最大值排序）
- 索引表：为每一块建立索引项，包含块的特征信息
分块索引的结构
分块索引由两部分组成：
- 数据块
– 将原始数据分成若干块
– 块内元素可以无序
– 块间按照块内最大值（或最小值）有序排列
- 索引表
– 每个索引项对应一个数据块
– 索引项包含：
– 块内最大关键字值
– 该块的起始位置
– 该块包含的元素个数
应用场景
1. 数据库索引
– 用于构建二级索引
– 适合范围查询
2. 文件系统
– 管理大文件的索引信息
– 提高文件检索效率
3. 嵌入式系统
– 适合内存受限但需要一定查找效率的场景
– 可以根据内存情况调整块大小
4. 动态数据管理
– 频繁插入删除的数据集合
– 需要保持一定查找效率的场景
倒排索引
倒排索引（Inverted Index） 是信息检索领域中一种非常重要的数据结构，广泛应用于搜索引擎、数据库和文本检索系统中。
倒排索引是现代搜索引擎和信息检索系统的核心技术，通过将”文档→词汇”的正向关系转换为”词汇→文档”的倒排关系，实现了高效的文本检索。虽然实现相对复杂且需要额外的存储空间，但其在查询效率方面的优势使其成为处理大规模文本数据的首选方案。在嵌入式系统中，虽然应用场景有限，但在需要文本检索功能的小型系统中仍有其价值。
正向索引 vs 倒排索引
正向索引：以文档ID为索引，记录每个文档中包含的词汇。例如：
文档1: {苹果, 香蕉, 橙子}
文档2: {苹果, 葡萄, 西瓜}
文档3: {香蕉, 葡萄, 橙子}
倒排索引：以词汇为索引，记录包含每个词汇的文档列表。例如：
苹果: {文档1, 文档2}
香蕉: {文档1, 文档3}
橙子: {文档1, 文档3}
葡萄: {文档2, 文档3}
西瓜: {文档2}
倒排索引的结构
倒排索引主要由两部分组成：
- 词典（Dictionary）
存储所有不重复的词汇，通常按字典序排列，并包含指向倒排列表的指针。 -
倒排列表（Posting List）
对于词典中的每个词，存储包含该词的文档列表及相关信息：
- 文档ID
- 词频（Term Frequency）
- 位置信息（可选）
- 其他元数据
二叉排序树
二叉排序树（BinarySortTree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
– 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
– 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
– 它的左、右子树也分别为二叉排序树。
二叉排序树查找
/* 树节点结构体 */
typedef struct BiTNode {
int data; /* 节点数据 */
struct BiTNode *lchild, *rchild; /* 左右子节点指针 */
} BiTNode, *BiTree;
/* 递归查找二叉排序树T中是否存在key，*/
/* 指针F指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针D指向该数据元素结点，并返回TRUE */
/* 否则指针P指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree *F, BiTree *D, BiTree *P) {
if (T == NULL) {
*P = *F; // 如果没有找到，返回最后访问的节点
return FALSE;
}
if (key == T->data) {
*D = T; // 找到节点
return TRUE;
} else if (key < T->data) {
*F = T; // 更新父节点
return SearchBST(T->lchild, key, F, D, P); // 继续在左子树查找
} else {
*F = T; // 更新父节点
return SearchBST(T->rchild, key, F, D, P); // 继续在右子树查找
}
}
二叉排序树插入
/* 树节点结构体 */
typedef struct BiTNode {
int data; /* 节点数据 */
struct BiTNode *lchild, *rchild; /* 左右子节点指针 */
} BiTNode, *BiTree;
/* 当二叉排序树T中不存在关键字等于key的数据元素时，*/
/* 插入key并返回TRUE，否则返回FALSE */
Status 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; /* 树为空，插入为根节点 */
else if(key < p->data)
p->lchild = s; /* 插入为左子节点 */
else
p->rchild = s; /* 插入为右子节点 */
return TRUE; /* 插入成功 */
}
else
return FALSE; /* 插入失败，关键字已存在 */
}
二叉排序树创建
int i;
in a[10] = {};
BiTree T=NULL;
for(i=0;i<10;i++)
InsertBST(&T,a[i]);
二叉排序树删除
对于二叉排序树的删除，我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。
三种情况：
- 叶子结点；
- 仅有左或右子树的结点；
- 左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树 T 查找key，查找到时删除。
情况1:
如果需要查找并删除如37、51、73、93这些在二叉排序树中是叶子的结点，其他结点的结构并未受到影响。
情况2:
对于要删除的结点只有左子树或只有右子树的情况，结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。
情况3:
对于要删除的结点 p 既有左子树又有右子树：
使用中序遍历找到 P 的直接前驱或者直接后继 s，用 s来替换掉结点 p，然后在删除此结点 s。
/* 若二叉排序树T中存在关键字等于key的数据元素时，则刪除该数据元素结点，*/
/* 并返回TRUE；否则返回FALSE */
Status DeleteBST(BiTree*T, int key)
{
if(!*T) /* 不存在关键字等于key 的数据元素 */
return FALSE;
else{
if(key == (*T)->data) /* 找到关键字等于key 的数据元素 */
return DeleteNode(T);
else if(key < (*T)->data) /* 在左子树中查找 */
return DeleteBST(&((*T)->lchild), key);
else /* 在右子树中查找 */
return DeleteBST(&((*T)->rchild), key);
}
}
/* 二叉排序树中删除结点P，并重接它的左或右子树。*/
Status 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;
}
(*p)->data = s->data; /* 将最大结点的值赋给当前结点 */
if(q!=*p) /* 如果最大结点不是当前结点的左子树的根 */
q->rchild = s->lchild; /* 重接最大结点的左子树 */
else
q->lchild = s->lchild; /* 重接最大结点的左子树 */
free(s); /* 释放最大结点 */
}
return OK;
}
平衡二叉树（AVL树）
暂时不作学习。
多路查找树（B树）
多路查找树（muitl-waysearchtree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
2-3树
特点
每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）
– 一个 2结点 包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子。
- 一个 3结点 包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
-
树中所有的叶子都在同一层次上。
插入操作
情况1：
– 插入空树：插入一个2结点即可。
情况2：
插入结点到一个2结点的叶子上，需要将2结点升级为3结点。
如图：3 比 8 小，走左边，比 4 小，走左边，只能考虑插入1的位置。
情况3：
往3结点中插入一个新元素。因为3结点本身已经是2-3树的结点最大容量（已经有两个元素），因此就需要将其拆分，且将树中两元素或插入元素的三者中选择其一向上移动一层。复杂的情况也正在于此。
- 需要向左图中插入元素5。经过遍历可得到元素5比8
小比4大，因此它应该是需要插入在拥有6、7元素的3结点位置。问题就在于，6和7结点已经是3结点，不能再加。此时发现它的双亲结点4是个2结点，因此考虑让它升级为3结点，这样它就得有三个孩子，于是就想到，将6、7结点拆分，让6与4结成3结点，将5成为它的中间孩子，将7成为它的右孩子，如右图所示。
-
如图所示，需要向左图中插入元素11。经过遍历可得到元素
11比12、14小比9、10大，因此它应该是需要插入在拥有9、10元素的3结点位置。同样道理，9和10结点不能再增加结点。此时发现它的双亲结点12、14也是一个3结点，也不能再插入元素了。再往上看，12、14结点的双亲，结点8是个2结点。于是就想到，将9、10拆分，12、14也拆分，让根结点8升级为3结点，最终形成右图样子。
-
如图所示，需要在左图中插入元素2。经过遍历可得到元素2比4小、6比1大，因此它应该是需要插入在拥有1、3元素的3结点位置。与上例一样，你会发现，1、3结点，4、6结点都是3结点，都不能再插入元素了，再往上看，8、12结点还是一个3结点，那就意味着，当前我们的树结构是三层已经不能满足当前结点增加的需要了。于是将1、3拆分，4、6拆分，连根结点8、12也拆分，最终形成如右图样子。
通过这个例子，也让我们发现，如果2-3树插入的传播效应导致了根结点的拆分，则树的高度就会增加。
删除操作
- 删除元素位于一个3结点的叶子结点上，只需要在该结点处删除该元素即可，不会影响到整棵树的其他结点结构。
-
删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点。如果按照以前树的理解，删除即可，可现在的2-3树的定义告诉我们这样做是不可以的。比如图所示，如果我们删除了结点1，那么结点4本来是一个2结点（它拥有两个孩子），此时它就不满足定义了。
-
情形一，此结点的双亲也是2结点，且拥有一个3结点的右孩子。如图：删除结点1，那么只需要左旋，即6成为双亲，4成为6的左孩子，7是6的右孩子。
-
情形二，此结点的双亲是2结点，它的右孩子也是2结点。如图所示，此时删除结点1，如果直接左旋会造成没有右孩子，因此需要对整棵树变形，办法就是，我们目标是让结点7变成3结点，那就得让比7稍大的元素8下来，随即就得让比元素8稍大的元素9补充结点8的位置，于是就有了中间图，于是再用左旋的方式，变成右图结果。
-
情形三，此结点的双亲是一个3结点。如图所示，此时删除结点10，意味着双亲12、14这个结点不能成为3结点了，于是将此结点拆分，并将12与13合并成为左孩子。
-
情形四，如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整棵树不能满足2-3树的定义。如图所示，删除叶子结点8时（其实删除任何个结点都一样），就不得不考虑要将2-3的层数减少，办法是将8的双亲和其左子树6合并为一3个结点，再将14与9合并为3结点，最后成为右图的样子。
- 删除的元素位于非叶子的分支结点。此时我们通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可。
-
如果我们要删除的分支结点是2结点。如图所示我们要删除4结点，分析后得到它的前驱是1后继是6，显然，由于6、7是3结点，只需要用6来补位即可，如图右图所示。
-
如果我们要删除的分支结点是3结点的某一元素，如图所示我们要删除12、14结点的12，此时，经过分析，显然应该是将是3结点的左孩子的10上升到删除位置合适。
2-3-4树
是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子（或没有孩子），一个4结点要么没有孩子，要么具有4个孩子。如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。
插入演示
删除演示
B树
B树（B-tree）是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order），因此，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。
- 所有叶子结点都位于同一层次。
- 所有分支结点包含下列信息数据（n,Ao，K1，A1，K2，A2,…Kn，An），其中：Ki（i=1,2,…n）为关键字，且Ki<K(i+1)（i=1,2，…,n-1）；Ai（i=0,2，…,n）为指向子树根结点的指针，且指针A(i-1)所指子树中所有结点的关键字均小于Ki（i=1,2，n），A所指子树中所有结点的关键字均大于Kn，n（[m/21]-1≤n≤m-1）为关键字的个数（或n+1为子树的个数）。
例如，在讲2-3-4树时插入9个数后的图转成B树示意就如图的右图所示。左侧灰色方块表示当前结点的元素个数。
在B树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。比方说，我们要查找数字7，首先从外存（比如硬盘中）读取得到根结点3、5、8三个元素，发现7不在当中，但在5和8之间，因此就通过A2再读取外存的6、7结点，查找到所要的元素。
B+树
是在B树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问。
一棵m阶的B+树和m阶的B树的差异在于：
– 有n棵子树的结点中包含有n个关键字；
– 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；
– 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字。如图所示，就是一棵B+树的示意，灰色关键字即是根结点中的关键字
在叶子结点再次列出，并且所有叶子结点都链接在一起。
散列表查找（哈希表）概述
散列表查找定义
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。散列技术既是一种存储方法，也是一种查找方法。
对应关系f称为散列函数，又称为哈希（Hash）函数。
采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hashtable）。
散列技术最适合的求解问题是查找与给定值相等的记录.
我们时常会碰到两个关键字 key1 ≠ key2，但是却有f（key1）=f（key2），这种现象我们称为冲突（collision），并把key1和key2称为这个散列函数的同义词（synonym）。
散列表查找步骤
- 存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
- 查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录.
散列函数的构造方法
直接定址法
取关键字的某个线性函数值为散列地址。
f（key）=a x key + b（a、b为常数）
数字分析法
取方法是使用关键字的一部分来计算散列存储位置的方法
平方取中法
这个方法计算很简单，假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
除留余数法
此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：
f（key）= key mod p(p≤m）
mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f（key）= random（key）。这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
了解 Heiweilu的小世界 的更多信息
订阅后即可通过电子邮件收到最新文章。
