数据结构——查找

查找

1. 查找的基本概念

查找(Searching)：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。查找结果分为两种，一种是查找成果，一种是查找失败。

查找表(Search Table)：是由同一类型的数据元素(或记录)构成的集合。
关键字(Key)：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。

静态查找表(Static Search Table)：只作查找操作的查找表。主要操作有查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素和各种属性。

动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。主要操作有查找时插入不存在的数据元素；查找时删除已存在的数据元素。

平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度，则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为

$ASL=\sum_{i=1}^nP_iC_i$

式中， $n$ 是查找表的长度； $P_i$ 是查找第 $i$ 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_i=\frac{1}{n}$ ； $C_i$ 是找到第 $i$ 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

2. 顺序查找和折半查找

2.1 顺序查找

2.1.1 顺序查找定义

顺序查找(Sequential Search) 又叫线性查找，是最基本的查找技术，作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

2.1.2 顺序查找算法

/*有哨兵顺序查找*/
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则说明查找失败
}

2.1.3 顺序查找效率

查找成功时的ASL，考虑 $P_i=\frac{1}n$

$ASL_{成功}=\frac{1}{n}\sum_{i=1}^n(n-i+1)=\frac{n+1}{2}$

查找不成功比较 $n + 1$ 次，即：

$ASL_{不成功}=n+1$

2.2 有序查找

2.2.1 有序查找定义

有序查找可以使用顺序查找，但在这里我们一般使用二分查找。

折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序)，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

2.2.2 折半查找算法

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
}

2.2.3 折半查找效率

下面举一个例子来看看二分查找的过程。

二分查找的查找过程可以用一棵二叉树来描述。其中，树中的每个结点表示一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树。

以上面的例子建立判定树，显然这是一颗AVL树。

由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率
查找时，查找成功的平均查找长度为

$\mathrm{ASL}=\frac{1}{n}\sum_{i=1}^{n}l_{i}=\frac{1}{n}(1\times1+2\times2+\cdots+h\times2^{h-1})=\frac{n+1}{n}\mathrm{log}_{2}(n+1)-1\approx\mathrm{log}_{2}(n+1)-1$

式中， $h$ 是树的高度，并且元素个数为 $n$ 时树高 $h=\lceil\log_2(n+1)\rceil$ 。所以,折半查找的时间复杂度 $O (l o g n)$ 。

在上图所示的判定树中，查找成功的概率为 $ASL=(1\times1+2\times2+3\times4+4\times4)/11=3$ ，即查找圆形结点；查找失败的概率为： $ASL=(3\times 4+4\times 8)/12=11/3$ ，即查找方形结点。

2.3 分块查找

分块查找就是结合顺序查找和折半查找，如果数据被组织成分块有序表，将表分成几块，块内无序，块间有序，先确定待查记录所在块，再在块内查找。

分块查找的过程分为两步:第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为 $L_I$ 和 $L_S$ , 则分块查找的平均查找长度为

ASL=L_1+L_{{S}}

将长度为 $n$ 的查找表均匀地分为 $b$ 块, 每块有 $s$ 个记录, 在等概率情况下, 若在块内和索引表中均采用顺序查找，则平均查找长度为

ASL=L_1+L_{{S}}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2 s+n}{2 s}

此时, 若 $s=\sqrt{n}$ , 则平均查找长度取最小值 $\sqrt n+1$ 。

若使用折半查找：

虽然索引表占用了额外的存储空间, 索引查找也增加了一定的系统开销, 但由于其分块结构,使得在块内查找时的范围较小, 因此与顺序查找相比, 分块查找的总体效率提升了不少。

$ASL\approx log_2(\frac{n}s+1)+\frac{s} 2$

3. 树形查找

3.1 二叉排序树（BST）

在前面我们已经讲过二叉排序树的定义，二叉排序树(也称二叉查找树)或者是一棵空树，或者是具有下列特性的二叉树：

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。

根据它的性质，我们可以看到，二叉排序树的中序遍历是有序序列。下面来介绍二叉排序树的操作函数。

二叉排序树的查找

二.叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空,先将给定值与根结点的关键字比较，若相等，则查找成功:若不等，若小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。这显然是一个递归的过程。

// 非递归写法
BSTNode *BST_Search(BiTree T, ElemType key)
{// 若树空或等于根结点值，则结束循环while (T != NULL && key != T->data){// 小于，则在左子树上查找if (key < T->data)T = T->lchild; // 大于，则在右子树上查找elseT = T->rchild;}return T;
}

// 递归写法
BSTree SearchBST(BSTree T, char key)
{// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素// 若查找成功，则返回指向该数据元素结点的指针，否则返回空指针if ((!T) || key == T->data.key)return T; // 查找结束else if (key < T->data.key)return SearchBST(T->lchild, key); // 在左子树中继续查找elsereturn SearchBST(T->rchild, key); // 在右子树中继续查找
} // SearchBST

二叉排序树的插入

插入与查找类似，都是利用二叉搜索树的特点，然后来找到合适的位置，最后当一个结点为空，证明找到了插入位置，代码如下，如果使用C++语言以及类来封装，会显得更加简便与易懂。返回值为节点，如果不使用返回值，则需要二级指针，这是从学习链表开始就一直提到的问题。
```
BSTNode *BSTInsert(BSTNode *root, int key)
{if (root == NULL) // 如果为空就插入{BSTNode *node = (BSTNode *)malloc(sizeof(BSTNode));node->left = node->right = NULL;node->val = key;return node;}if (key < root->val)root->left=BSTInsert(root->left,key);elseroot->right=BSTInsert(root->right, key);return root;
}
```
二叉排序树的删除

二叉排序树的删除相对来说比较麻烦，因为需要考虑多种情况。通常分三种情况来处理。

①若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。

②若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。

③若结点z有左、右两棵子树，则令z的直接后继(或直接前驱)替代z，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况。

以下图为例：

BSTNode *findMin(BSTNode *root)
{while(root->left!=NULL){root=root->right;}return root;
}
BSTNode *BSTDelete(BSTNode *root,int key)
{if(root==NULL)return root;// 首先要找到结点if(key<root->val)root->left=BSTDelete(root->left,key);else if(key>root->val)root->right=BSTDelete(root->right,key);else{// 找到后开始删除，考虑不同的情况if(root->left==NULL) // 只有左子树为空{BSTNode *temp=root->right;free(root);return temp;}else if(root->right==NULL) // 只有右子树{BSTNode *temp=root->left;free(root);return temp;}// 若有两个结点else{BSTNode *temp=findMin(root->right);// 找到右子树最小值root->val=temp->val;root->right=BSTDelete(root->right,temp->val);// 然后把问题转化成前面两种情况}}return root;}

3.2 平衡二叉树

为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树(Balanced Binary Tree)，也称 AVL树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0或1。