数据结构【六】:搜索

搜索的分类

---

静态搜索

静态搜索 ：只是对表中元素进行检索，不更改表信息；检索到，则返回成功；检索不到，则返回失败。

动态搜索

动态搜索：对表中元素进行检索，同时通过检索过程来实现表的更新；检索到，则返回成功（或删除）；检索不到，则将新元素插入到表中适当位置。

搜索算法的性能衡量

---

衡量搜索算法的时间效率的标准：在搜索过程中 关键码的平均比较次数，也称为平均搜索长度
ASL(Average Search Length)。

设数据表中有 n 个元素，搜索第 i 个元素的概率为 pi搜索到第 i 个元素所需比较次数为 ci，则搜索成功的
平均搜索长度:

搜索算法

---

Ⅰ、线性表查找

1.顺序搜索

从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

顺序查找算法的 时间复杂度 为O(n)。

优点：算法简单，且对表的结构无任何要求，无论用顺序表还是链表来存放结点，也无论结点是否按关键字有序，都同样适用。

缺点:查找效率低

2.有序顺序表的折半搜索算法（二分搜索）

有序表中的“有序”是逻辑意义上的有序，指表中的元素按某种规则已经排好了位置。顺序表中的“顺序”是物理意义上的

采用折半查找的条件：要求顺序存储且关键字值有序

1、待查找的值作为key

2、比较表中Mid的值和Key的值，若相等查找成功，若不等根据有序表的关系，确定下一个查找区间

3、重复上述操作直到查找完毕

/** 二分查找
 * @param arr  : 带查找数组
 * @param n ： arr[0]不做存储，待查数据产品那个arr[1]开始
 * @param key ：待查关键字
 * @return ：返回角标
 */
int binerySearch(int *arr,int n,int key){
    int low = 1; //从arr[1]开始查找
    int high = n;
    int mid;
    while(low <= high){
        mid = (low + high)/2;
        if(key < arr[mid]){
            high = mid-1;
        }else if(key > arr[mid]){
            low = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

代码源自:数据结构（四）查找

时间复杂度为O(log₂n)

折半查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

3.基于有序顺序表的其它搜索方法

• 斐波那契搜索
• 差值搜索

Ⅱ、树表查找

1.二叉搜索（排序）树

①定义

二叉搜索树或者是一棵空树；或者是具有下列性质的二叉树：

(1) 左子树上所有结点的值均小于等于它的根结点的值；

(2) 右子树上所有结点的值均大于它的根结点的值；

(3) 根结点的左、右子树也分别为二叉排序树。

按中序遍历该树所得到的中序序列是一个递增有序序列

②二叉搜索树的插入和生成以及搜索

二叉搜索树的结构是在搜索过程中逐步生成的，通过不断执行插入操作可以生成一棵二叉搜索树。

根据搜索二叉树的特点，新插入的结点一定是一个叶子结点

搜索过程和插入过程相差无几

template <class E, class K>
bool BST<E, K>::Insert (const E& e1, BSTNode<E, K> *& ptr) 
{	   
    if (ptr == NULL) {	   //新结点作为叶结点插入
        ptr = new BstNode<E, K>(e1);	  //创建新结点
        if (ptr == NULL)
            { cerr << "Out of space" << endl;  exit(1); }
	    return true;
		}
    else if (e1 < ptr->data) Insert (e1, ptr->left);	 		//左子树插入
		 else if (e1 > ptr->data) Insert (e1, ptr->right);		//右子树插入
		 else return false;	      //x已在树中,不再插入
};

③搜索二叉树的删除

在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。

所以分为四种情况:

• 删除叶结点：只需将其双亲结点指向它的指针清零，再释放它
• 被删结点右子树为空：可以拿它的左子女结点顶替它的位置，再释放它
• 被删结点左子树为空：可以拿它的右子女结点顶替它的位置，再释放它
• 被删结点左、右子树都不为空：在右子树上找中序下第一个结点填补（或者左子树找中序最后一个结点填补，一定要注意，右子树中序下一个节点，不是右孩子节点的左节点，而是右子树中最深的左分支的最后一个点“通俗的就是右子树的最偏左的点”，同理“左子树的最偏右的点”）

④N个结点二叉搜索树的种类和性能分析

对于有 n 个关键码的集合，其关键码有 n! 种不同排列，可构成不同二叉搜索树有（catalan函数）种

所以对于一组数据，我们可以构成多个搜索二叉树，而且效率不定相同。

对于树型结构的ASL计算我们根据树的特点和ASL定义，可以对每个结点计算概率×层数再求和，而查询失败长度相当于查询到了叶子结点的下一个结点（NULL）我们对每个该结点计算概率×（层数-1）再求和就得到了查询失败长度，之所以是（层数减1，是因为实际上我们实际上是比较到叶子节点，只不过结果是比较失败而已）。概率相等时：成功概率=1/数据结点数 失败概率=1/失败结点数（空指针域，也就是数据节点数+1）

例如（默认概率相等）：

对a：ASLsucc=1/3×3+1/3×2+1/3×1=6/3 ASLunsucc = 1/4×3×2+1/4×2+1/4×1 = 9/4

对b：ASLsucc = 1/3×2×2+1/3×1 = 5/3 ASLunsucc = 1/4×2×4 = 8/4

若不相等，则把给出的相应结点对于概率替换掉相等概率计算即可

一般把平均搜索长度达到最小的扩充的二叉搜索树称作最优二叉搜索树。

##### ⑤二叉排序树和堆的区别

结构上：

二叉排序树：左子树小于根节点，根节点又小于右子树。

堆（小堆）：根节点小于左右子树，但是左右子树没有大小之分。

作用上：

二叉排序树是用来做查找的，而堆是用来做排序的。

2.平衡二叉树（AVL树）

①定义

平衡二叉树首先是一棵二叉排序树

平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树:

其左子树和右子树的深度之差的绝对值不超过 1 ；

其左子树和右子树都是平衡二叉树 ；

平衡因子 ( Balance Factor，BF)定义为该结点的左子树的深度减去右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。

为了实现二叉排序树的平均查找长度和 log n 等数量级，需要对二叉排序树进行“平衡化”处理，即构造平衡二叉树。

##### ②平衡二叉树的构造

什么是平衡二叉树（AVL）

参考文章:

数据结构与算法 - 查找

数据结构与算法（10）：查找

数据结构（四）查找

什么是平衡二叉树（AVL）