数据结构——查找

发表于 2024-12-15 更新于 2025-06-26 分类于大二上，数据结构阅读次数：

查找的概念

查找(Searching) ：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。

查找表(Search Table) ：是由同一类型的数据元素(或记录)构成的集合。

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

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

平均查找长度 ：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度，则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为$\ ASL=\sum_{i=1}^{n}P_iC_i$

式中，n是查找表的长度;P是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即P,= 1/n;C;是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序表查找

顺序查找

/*有哨兵顺序查找*/
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) 。

折半查找

当查找表是有序表时，可采用折半查找的方法。

算法思路：

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
}

折半查找的过程可用二叉树来描述，称为判定树。

节点的树高代表该节点的查询次数

因此，长度为13的有序表进行折半查找的平均查找长度ASL=(1×1+2×2+3×4+4×6)/13 =41/13。

折半查找的时间复杂度为 O(log₂n)，平均情况下比顺序查找的效率高。

分块查找

为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若千块，并且这些块需要满足两个条件：

块内无序：即每一块内的记录不要求有序。
块间有序：例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字…因为只有块间有序，才有可能在查找时带来效率。

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。如下图所示，我们定义的分块索引的索引项结构分三个数据项：

最大关键码：它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
块长：存储了块中的记录个数，以便于循环时使用；
块首指针：用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

在分块索引表中查找，就是分两步进行: 1.在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。例如在上图的数据集中查找62，我们可以很快可以从左上角的索引表中由57<62<96得到62在第三个块中。 2.根据块首指针找到相应的块，并在块中顺序查找关键码。

树表的查找

二叉排序树

二叉排序树(也称二叉查找树)或者是一棵空树，或者是具有下列特性的二叉树:

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

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，下图所示二叉排序树的中序遍历序列为123468。

二叉排序树的插入和建立

在一棵二叉排序树中插入值为系的结点的步骤如下：

①若二叉排序树为空，则生成值为k的新结点s，同时将新结点s作为根结点插入。

②若k小于根结点的值,则在根的左子树中插入值为k的结点。

③若k大于根结点的值,则在根的右子树中插入值为k的结点。

④若k等于根结点的值，表明二叉排序树中已有此关键字，则无需插入。

二叉排序树插入算法

 //构造函数
 BiNode(int k) : key(k), lchild(nullptr), rchild(nullptr) {};
// 递归插入函数
    void Insert(BiNode*& ptr, int k) {
        if (ptr == nullptr) { // 如果当前指针为空，插入新节点
            ptr = new BiNode(k);
            return;
        }
        if (k < ptr->key) { 
            Insert(ptr->lchild, k); // 递归插入到左子树
        } else if (k > ptr->key) {
            Insert(ptr->rchild, k); // 递归插入到右子树
        }
        // 如果k等于当前节点值，则不插入（BST通常不允许重复值）
    }
// 插入值到BST
    void Insert(int k) {
        Insert(root, k);
    }

二叉排序树的建立

// 构造函数：利用数组 a[] 和大小 n 建立二叉排序树
    BiSortTree(int a[], int n) {
        root = nullptr; // 初始化根节点为空
        for (int i = 0; i < n; ++i) {
            Insert(root, a[i]); // 插入数组中的每个元素
        }
    }

二叉排序树的查找过程

根据二叉排序树的定义，在二叉排序树中查找给定值k的过程如下:

①若二叉排序树为空，则表明查找失败，返回空指针;否则，若给定值k等于根结点的值,则表明查找成功,返回根结点。

②若给定值k小于根结点的值,则继续在根的左子树中查找。

③若给定值k大于根结点的值,则继续在根的右子树中查找。

// 非递归查找函数
   BiNode* Search2(BiNode* ptr, int k) {
       while (ptr) {
           if (k == ptr->key) // 找到目标节点
               return ptr;
           else if (k < ptr->key) // 查找左子树
               ptr = ptr->lchild;
           else                  // 查找右子树
               ptr = ptr->rchild;
       }
       return nullptr; // 未找到
   }

若二叉排序树是平衡的(即形态均匀)，则进行查找的时间复杂度为 O(log₂n);若退化为一棵单支树（最极端和最差的情况)，则其时间复杂度为 O(n)。对于一般情况，其时间复杂度可以认为是 O(log₂n)。

二叉排序树的删除

二叉排序树的查找和插入都很简单，但是删除操作就要复杂一些，此时要删除的结点有三种情况：

叶子结点；
仅有左或右子树的结点；
左右子树都有的结点；

前两种情况都很简单，第一种只需删除该结点不需要做其他操作；第二种删除后需让被删除结点的直接后继接替它的位置；复杂就复杂在第三种，此时我们需要遍历得到被删除结点的直接前驱或者直接后继来接替它的位置，然后再删除。

第三种情况如下图所示：

代码如下：

/*
若二叉排序树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;
}

二叉排序树的查找性能取决于二叉排序树的形状。

例如{ 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},则二叉排序树就成了极端的右斜树，如下面右图的二叉排序树： f33a1ebf98e14082fb0df30072964e09

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂也就为 O(log₂n)，近似于折半查找。不平衡的最坏情况就是像上面右图的斜树，查找时间复杂度为O(n)，这等同于顺序查找。因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。