1. 静态查找

数据集合是固定的

1.1 顺序查找

0下标设置为哨兵位，从n找到0，m=0表示查找不成功。

# include <iostream>
using namespace std;

template<class KEY, class OTHER>
struct SET{
	KEY key;
	OTHER other;
};

int seqSearch(SET<KEY,OTHER> data[],int size,const KEY& x){
	data[0].key=x;
	int i;
	for(i=size;data[i].key!=x;--i);
	return i;
}

时间复杂度：o(n)

1.2 折半查找

# include <iostream>
using namespace std;

struct SET{
	KEY key;
	OTHER other;
};

int binarySearch(SET<KEY,OTHER> data[], int size, const KEY &x){
	int low=1,high=size,mid;
	while(low<=high){
		mid=(high+low)/2;
		if(x==data[mid].key) return mid;
		else if(x<data[mid].key) high=mid-1;
		else low=mid+1;
	}
	return 0;
}

时间复杂度：$o(\log_{2}n)$

1.3 插值查找

计算方法：$mid=low+(high-low)((x-a[low]/a[high]-a[low]))$

#include <iostream>
using namespace std;

template<class KEY, class OTHER>
int interpolationSearch(SET<KEY, OTHER> data[], int size, const KEY& x){
	int low=1,high=size,pos;
	while(low<=high && x>= data[low].key && x<= data[high].key){
		if (data[high].key == data[low].key) break; 
		pos=low+(high-low)*((x-data[low].key/data[high].key-data[low],key));
		if (data[pos].key==x) return pos;
		else if(data[pos].key<x) low=pos+1;
		else high=pos-1;
	return 0;
}

与二分查找的代码区别：

需要判断x>= data[low].key && x<=data[high].key，因为pos计算的公式无法保证这一点，如data[1]=100, data[2]=101, data[3]=102 查找x=0，low=1，high=3，则pos计算值为-99，显然数组越界。
需要判断 data[high].key == data[low].key，否则下一步作为分母的计算无意义。

1.4 分块查找

把大的线性表分解成若干块，==块中数据可以无序随意存放但是块间必须有序==。
要建立一个索引表，把每块中最大关键字值作为索引表的关键字，从小到大顺序存放在一个辅助数组中。查找时，可以先在索引表中折半查找，确定要找的元素所在的块，然后在块中采用顺序查找，即可找到对应的元素。
一般适用于数据量很大的情况。

2. 动态查找

数据频繁插入删除，使用链式存储

3. 二叉查找树（掌握思想）

3.1 定义

对二叉树的每一个节点，==左子树上所有节点都比其小，右子树都比它大==。
数组序列中没有元素相等
基本操作：find，insert，remove
它的中序序列是从大到小排好序的

3.2 查找

递归方法：

根为空，查找失败
与根相同，成功
比根小，在左子树找
比根大，在右子树找

# include <iostream>
using namespace std;

SET<KEY,OTHER> *BinarySearchTree::find (KEY &x, BinaryNode *t){
	if(t==NULL) return NULL;
	if(x==t->data.key) return &(t->data);//返回对应数据指针
	else if(x<t->data.key) return find(x,t->left);
	else return find(x,t->right);
}

非递归方法：

若当前节点不为空，比较：值相等则查找成功；目标值比当前节点小，则左子为当前节点；目标值比当前节点大，右子为当前节点
反复至当前节点为空

#include<iostream>
using namespace std;

SET<KEY,OTHER> *BinarySearchTree<KEY,OTHER>::find(constKEY&x, BinayNode *t)const{
	if(t==NULL) return NULL;
	BinaryNode *p=t;
	while(p){
		if(x==p->data.key) return &(t->data);
		else if(x<p->data.key) p=p->left;
		else p=p->right;
	}
	return NULL
}

时间复杂度：时间复杂度即为二叉树高度，但是不是$o(\lg n)$，最坏情况下二叉树退化为单链表，此时为o(n)

3.3 插入

递归：

#include <iostream>
using namespace std;

void BinarySearchTree<KEY,OTHER>:: insert(const SET<KEY,OTHER>& x,BinaryNode *&t){
	if(t==NULL) t=new BinaryNode(x,NULL,NULL);
	else if(x.key<t->data.key) insert(x,t->left);
	else if(t->data.key<x.key) insert(x,t->right);
}

其中，==* &t中的&不能被省略==。通过对t的修改建立新结点和父结点的关系

非递归：（非必要不使用）

#include <iostream>
using namespace std;

void BinarySearchTree<KEY,OTHER>:: insert (const SET <KEY,OTHER> &x, BinaryNode *&T){
	BinaryNode **p = &t;
	while(*p!=NULL){
		if (x.key<(*p)->data.key) p=&(*p)->left;
		else if ((*p)->data.key<x.key) p=&(*p)->right;
		else return;
	}
	*p = new BinaryNode (x,NULL,NULL);
}

3.4 删除

递归方法：

待删除节点为叶子：释放待删除节点空间
待删除结点有唯一孩子：唯一孩子替代待删除结点位置
待删除节点有两个孩子：在右子树中找最左侧节点，或左子树里找最右侧结点，作为替身

递归实现：

template<class KEY, class OTHER>
void BinarySearchTree <KEY,OTHER>::remove(const KEY &x, BinaryNode *&t){
	if(t=NULL) return;
	if(x<t->data.key) remove(x,t->left);
	else if(t->data.key<x) remove(x,t->right);
	else if(t->left!=NULL && t->right!=NULL){
		BinaryNode *tmp=t->right;
		while (tmp->left!=NULL) tmp=tmp->left;
		t->data = tmp->data;
		remove(t->data.key, t->right);
	}
	else {
		BinaryNode *oldNode = t;
		t=(t->left!=NULL)? t->left:t->right;
		delete oldNode;
	}
}

非递归实现：

template <class KEY, class OTHER>
void BinarySearchTree <KEY,OTHER>::remove(const KEY &x){
	BinaryNode *current=root;
	BinaryNode *parent=NULL;
	while(current!=NULL && current->data.key!=x){
		parent=current;
		if(x<current->data.key) current=current->left;
		else current=current->right;
	}
	if(current==NULL) return;
	
	if(current->left!=NULL && current->right!=NULL){
		BinaryNode *tmp=current->right;
		BinaryNode *gp=current;
		while(tmp->left!=NULL){
			gp=tmp;
			tmp=tmp->left;
		}
		current->data=tmp->data;
		if(gp->left==tmp) gp->left=tmp->right;
		else gp->right=tmp->right;
		delete tmp;
	}
	
	else{
		BinaryNode *child=(current->left!=NULL)? current->left:current->right;
		if(parent==NULL) root=child;
		else{
			if(current==parent->left) parent->left=child;
			else parent->right=child;
		}
		delete current;
	}
}

4. 顺序统计（略)

5. 平衡二叉查找树（AVL树）

5.1 定义

平衡因子：左子树高度-右子树高度
平衡二叉树：所有结点平衡因子只可能是-1,0,1
平衡二叉树的目标是限制二叉树的高度
平衡二叉树不一定是数最矮的情况，但是接近最矮
让查找效率到$o(\lg n)$

5.2 查找

完全同普通二叉查找树的查找

5.3 插入

插入后父节点平衡因子变为0，则说明本来左右子树不一样高，插入后一样高，再往上的平衡因子不变
若插入后不平衡，第一个平衡因子超过范围的结点称为冲突节点
孙子节点分为4种类型：LL、RR、LR、RL

LL 调整（右旋）：

template <class KEY, class OTHER>
void AvlTree<KEY,OTHER>::LL(AvlNode *&t){
	AvlNode *tl= t->left;
	t->left=tl->right;
	tl->right=t;
	t->height=max(height(t->left),height(t->right))+1;
	tl->height=max(height(tl->left),height(t))+1;
	t=tl;
}

RR 调整（左旋）：

template <class KEY, class OTHER>
void AvlTree<KEY,OTHER>::RR(AvlNode *&t){
	AvlNode *tl= t->right;
	t->right=tl->left;
	tl->left=t;
	t->height=max(height(t->left),height(t->right))+1;
	tl->height=max(height(tl->right),height(t))+1;
	t=tl;
}

LR 调整（先对左子树RR旋转，再对当前节点LL旋转）

template<class KEY, class OTHER>
void AvlTree <KEY,OTHER>::LR(AvlNode *&t){
	RR(t->left);
	LL(t);
}

RL 调整（先对右子树LL旋转，再对当前节点RR旋转）

template<class KEY, class OTHER>
void AvlTree <KEY,OTHER>::LR(AvlNode *&t){
	LL(t->right);
	RR(t);
}

由此，得insert函数的实现：

template<class KEY, class OTHER>
void AvlTree <KEY,OTHER>::insert(const SET<KEY,OTHER> &x,AvlNode *&t){
	if(t==NULL) t=new AvlNode(x,NULL,NULL);
	else if(x.key<t->data.key){
		insert(x,x->left);
		if(height(t->left)-height(t->right)==2){
			if (x.key<t->left->data.key) LL(t);
			else LR(t);
		}
	}
	else if(x.key>t->data.key){
		insert(x,t->right);
		if(height(t->right)-height(t->left)==2){
			if(x.key>t->right->data.key) RR(t);
			else RL(t);
		}
	}
	t->height=max(height(t->left),height(t->right))+1;
}

5.4 删除

先删除，删除后，从被删除节点的父节点开始，向上检查平衡性，必要时旋转。
remove 返回 true 表示不需要再向上调整，false 表示本层高度发生变化，需要父节点检查平衡。
![[6-AVL树删除.png]]
![[6-AVL树删除2.png|697]]

template <class KEY, class OTHER>
bool AvlTree<KEY,OTHER>::remove(const KEY&x, AvlNode *&t){
	if(t==NULL) return true;
	//true表示不需要调整
	if (x==t->data.key){
		if(t->left==NULL || t->right==NULL){
			AvlNode *oldNode=t;
			t=(t->left!=NULL)? t->left:t->right;
			delete oldNode;
			return false;
			// 子树变矮，返回false
		}
		else{
			AvlNode *tmp=t->right;
			while(tmp->left!=NULL) tmp=tmp->left;
			t->data=tmp->data;
			if(remove(tmp->data.key,t->right)) return true;
			return adjust(t,1);//"1"表示删除点在右边；
		}
	}
	if(x<t->data.key){
		if(remove(x,t->left)) return true;
		return adjust(t,0);
	}
	else{
		if(remove(x,t->right)) return true;
		return adjust(t,1);
	}
}

template<class KEY, class OTHER>
bool AvlTree<KEY,OTHER>::adjust(AvlNode *&t,int subTree){
// subtree为0：删除发生在左子树；为1：删除发生在右子树
	if(subTree){
		if (height(t->left)-height(t->right)==1) return true;
		if (height(t->right)==height(t->left)){
		--t->height;
		return false;
		}
		if(height(t->left->right)>height(t->left->left)){
			LR(t);
			return false;
		}
	
		LL(t);
		return height(t->right)!=height(t->left);
	}
	
	else{
		if(height(t->right)-height(t->left)==1) return true;
		if(height(t->right)==height(t->left)){
			--t->height;
			return false;
		}
		if(height(t->right->left)>height(t->right->right)){
			RL(t);
			return false;
		}
		
		RR(t);
		return height(t->right)!=height(t->left);
		// 对应5种情况
	}
}

6. 红黑树（略）

7. 外部查找

实际应用中，数据量很大，存储在外存储器的文件中，数据无法一次性一次载入内存。为加快数据的查找速度，建立检索文件是最普遍的方法。
索引文件，通常按关键字存储关键字和所属数据在原始文件中地址的对应关系。
主存储器：即内存，存储正在运行的代码及处理数据
外存储器：可储存长期保存的信息。常用的有磁盘、磁带、光盘、U盘；存储量大，永久保存；价格低廉，访问速度慢
考虑处理外存储器上的数据，应考虑如何减少访问次数。
外存储器中信息以文件为单位，外存储器以数据块为单位与内存交换信息

7.1 B树（B-树）（掌握思想，理解即可）

每个节点可以有多个子节点

==定义阶数m，内部结点至少有[m/2]（向上取整）个子结点，最多有m个子结点（即每个结点内关键字个数在$[m/2]$-1~$m-1$之间）==

B树的插入与删除

7.2 B+树

既可以随机查找，也可以顺序访问。
==只有叶子结点中有data，其他层都是索引==
非叶子结点至多保存M-1个键引导查找，键i表示子树i+1中键的最小值
非叶子结点个数为[M/2]~M 之间
所有叶子结点连接成单链表，可实现原始数据的顺序遍历

插入：

叶结点不满：插入叶子
叶结点装满：分裂叶子，形成两个半满的叶子来插入新的项，更新父结点，若父结点儿子数量已满，继续分裂父亲，最坏情况分裂根，根结点允许只有两个孩子

删除：

若叶子元素数正好满足要求的最小值，邻居借一个，若邻居也最小，两个结点合并，向上过滤只根。若过滤过程中根只剩下一个儿子，删除根让儿子作为新根

8. 哈希查找

8.1 基本概念

哈希法，也叫散列法，直接根据所求节点的关键字值KEY找到这个节点，时间复杂度为o(1)，但是用空间换时间

哈希函数：每个结点在表中的位置由一个函数H确定，该函数以结点关键字值为参数，计算出关键字对应节点的存储位置。该函数为哈希函数。值域为0-m-1 。哈希函数选择时注意要使计算速度快，散列地址尽可能均匀，冲突机会小。

8.2 常用哈希函数

8.2.1 直接地址法

H(key)=a×key+b;

8.2.2 除留余数法

H(key)=key MOD p+c 其中p选取小于等于m的素数，可以尽可能避免单元的浪费。

8.2.3 数字分析法

对关键字集合中的所有关键字，分析每一位上数字分布。取数字分布均匀的位作为地址的组成部分。

8.2.4 平方取中法

如果关键字中各位的分布都比较均匀，但关键字的值域比数组规模大，则可以将关键字平方后，取其结果的中间各位作为散列函数值。由于中间各位和每一位数字都有关系，因此均匀分布的可能性较大。

8.2.5 折叠法

如果关键字相当长，以至于和散列表的单元总数相比大得多时，可采用此法
选取一个长度后，将关键字按此长度分组相加

259

8.3 冲突问题（闭散列表）

template <class KEY, class OTHER>
class closeHashTable:public dynamicSearchTable<KEY, OTHER> {
    private:
        struct node { 
            SET <KEY, OTHER>  data;
            int    state;                                  
            //0 -- empty   1 -- active   2 – deleted
            node() {state = 0;}
       };
       node *array;
       int  size;
       int (*key)(const KEY &x);  
       static int defaultKey(const int &x) {return x;} 
	public: 
       closeHashTable(int length = 101, int (*f)(const KEY &x) = defaultKey) ;
       ~closeHashTable() {delete [] array;}
       SET<KEY, OTHER> *find(const KEY &x) const;
       void insert(const SET<KEY, OTHER> &x);
       void remove(const KEY &x) ;
};

template <class Type>
closeHashTable<Type>::closeHashTable (int length, int (*f)(const Type  &x) )
{
	size = length;
	array = new node[size];
	key = f;
} 

template <class KEY, class OTHER>
void closeHashTable<KEY, OTHER>::insert(const SET<KEY, OTHER> &x)
{
	int initPos, pos ;	
	initPos = pos = key(x.key) % size;
	do {  
        if (array[pos].state != 1) {// 找到空单元
            array[pos].data = x; 
            array[pos].state = 1; 
            return;
        }
		pos = (pos+1) % size;
    } while (pos != initPos);
}

template <class KEY, class OTHER>
void closeHashTable<KEY, OTHER>::remove(const KEY &x) 
{	   
	int initPos, pos ; 
	initPos = pos = key(x) % size;
    do {
        if (array[pos].state == 0) return;
 	    if (array[pos].state == 1 && array[pos].data.key == x) {  // 找到，删除
		    array[pos].state = 2;
		    return;
	    }
	    pos = (pos+1) % size;
    } while (pos != initPos);
}

template <class KEY, class OTHER>
SET<KEY, OTHER> *closeHashTable<KEY, OTHER>::find(const KEY &x) const
{ 	    
	int initPos, pos ; 
	initPos = pos = key(x) % size;
    do {
        if (array[pos].state == 0) return NULL;     // 没有找到
	    if (array[pos].state == 1 && array[pos].data.key == x)    // 找到
            return (SET<KEY,OTHER> *)&array[pos];
	    pos = (pos+1) % size;
    } while (pos != initPos);
}

8.3.1 线性探测法

当散列发生冲突时，探测下一个单元，直到发现一个空单元

8.3.2 二次探测法

地址序列为k+$1^2$,k+$2^2$,k+$3^2$ ……

8.3.3 再次散列法

有两个散列函数hash1和hash2
hash1用来计算探测序列的起始地址
hash2用来计算下一个探测位置的步长
第i次碰撞时，地址为f(i) = i×hash2(x)
建议采用hash2(x) = R - (x mod R)，其中R是小于表长的一个素数
设表长为M，插入元素为x，再次散列法的探测序列为： hash1(x), (hash1(x)+hash2(x))mod M, (hash1(x)+2×hash2(x))mod M, …

8.4 开散列表

开散列表是将所有散列到同一地址的元素链成一个单链表，于是需要定义一个单链表中的结点类
采用不带头结点的单链表
散列表保存在一个数组中，数组的每个元素是一个指针，指向对应的单链表的首地址

template <class KEY, class OTHER>
class openHashTable:public dynamicSearchTable<KEY, OTHER> {
	private:
	    struct node {
	        SET<KEY, OTHER>  data;
		    node    *next; 
		    node (const SET<KEY, OTHER> &d, node *n = NULL){ data = d;next = n; }
		    node () {next = NULL;}
		};
		node **array;//指针数组
		int  size;
		int (*key)(const KEY &x);
		static int defaultKey(const int &x) { return x; }
	public: 
	  	openHashTable(int length = 101, int (*f)(const KEY &x) = defaultKey);
		~openHashTable() ;
		SET<KEY, OTHER> *find(const KEY &x) const;
	    void insert(const SET<KEY, OTHER> &x);
	    void remove(const KEY &x) ;
	};
	
template <class KEY, class OTHER>
openHashTable<KEY, OTHER>::openHashTable (int length,  int (*f)(const KEY  &x) )
{
	size = length;
	array = new node*[size];
	key = f;
	for (int i = 0; i < size; ++i) array[i] = NULL;
}

template <class KEY, class OTHER>
openHashTable<KEY, OTHER>::~openHashTable()
{
	node *p, *q;
	for (int i = 0; i< size; ++i) {           
	    p = array[i]; 
	    while (p!=NULL) { q= p->next; delete p; p = q; } ;
   }
    delete [] array;
} 

template <class KEY, class OTHER>
void openHashTable<KEY, OTHER>::insert(const SET<KEY, OTHER> &x)
{
 	int pos ;
	node *p; 
    pos = key(x.key) % size;
	array[pos] = new node(x, array[pos]);
}

template <class KEY, class OTHER>
void openHashTable<KEY, OTHER>::remove(const KEY &x) 
{
 	int  pos ;
 	node *p, *q;
    pos = key(x) % size;
  	if (array[pos] == NULL) return;
    p = array[pos];
    if (array[pos]->data.key == x) {
	    array[pos] = p->next; delete p; return;}
    while (p->next != NULL && !(p->next->data.key == x) ) p = p->next;
    if (p->next != NULL) {
	      q = p->next;   p->next = q->next;   delete q;    }
}

template <class KEY, class OTHER>
SET<KEY, OTHER> *openHashTable<KEY, OTHER> ::find(const KEY &x) const
{
	int pos ;
    node *p;
    pos = key(x) % size;
    p = array[pos];
    while (p != NULL && !(p->data.key == x) ) p = p->next;
    if (p == NULL) return NULL;
    else return (SET<KEY, OTHER> *)p;
}

9. 总结

![[6-查找方法总结.png]]

http://chenjiayi0505.github.io/2026/07/02/数据结构第六章查找/

作者

Jiayi Chen

发布于

2026年7月2日

更新于

2026年6月23日

许可协议