数据结构第七章（查找算法）

写在前面：

本系列笔记主要以《数据结构（C语言版）》为参考（本章部分图片来源于王道），结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言，如有错误欢迎指出。
视频链接：第01周a--前言_哔哩哔哩_bilibili
平衡二叉树部分的代码参考了一位小伙伴分享的代码，特此说明一下，其它C代码均由笔者根据书上的类C代码进行编写。

一、查找的基本概念

1、查找表

（1）查找表是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

（2）对查找表经常进行的操作：

①查询某个“特定的”数据元素是否在查找表中。

②检索某个“特定的”数据元素的各种属性。

③在查找表中插入一个数据元素。

④删除查找表中的某个数据元素。

2、关键字

（1）关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。

（2）若一个关键字可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）；反之，称用以识别若干记录的关键字为次关键字。

3、查找

查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时查找的结果可给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。

4、动态查找表和静态查找表

若在查找的同时对表执行修改操作（如插入和删除），则称相应的表为动态查找表，否则称之为静态查找表。

5、平均查找长度

（1）为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度ASL（关键字的平均比较次数）。

（2）对于含有n个记录的表，查找成功时的平均查找长度为 $ASL=\sum_{i=1}^{n}P_{i}C_{i}$ ，其中 $P_{i}$ 为查找表中第i个记录的概率， $C_{i}$ 为找到表中其关键字与给定值相等的第i个记录时和给定值已进行过比较的关键字个数。

二、线性表的查找

1、顺序查找

（1）顺序查找的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等则查找成功，若查找整个表后仍未找到关键字和给定值相等的记录则查找失败。

（2）以顺序表作为存储结构时实现的顺序查找算法：

①顺序表及数据元素类型的定义：

typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;        //关键字域
	InfoType otherinfo; //其它域
}ElemType;

typedef struct
{
	ElemType* R;   //存储空间基地址
	int length;    //当前长度
}SSTable;

②在第二章中也有查找算法的具体实现，但是在当时的算法中每一步都要检测整个表是否查找完毕，也就是需要让循环变量i和顺序表的长度进行比较。为了改善算法的运行效率，可以闲置数组R的0号元素不用于存储，进入查找算法后把需要查找的值赋给0号元素，然后从顺序表的最后一个元素开始，逐个元素与0号元素比较，查找到目标元素后当即结束查找并返回元素的下标，当目标元素不在顺序表中时，查找算法遍历所有元素后最终会访问0号元素，这时必定会结束查找并返回0，代表要查找的元素不在顺序表中，如此，可以免去查找过程中每一步都要检测整个表是否查找完毕，不过需要牺牲一个元素的存储空间。

③算法具体实现：

int Search_Seq(SSTable ST, KeyType key)    //顺序查找
{
	ST.R[0].key = key;      //监视哨
	int i;
	for (i = ST.length; ST.R[i].key != key; i--);   //从后往前查找
	return i;
}

（3）顺序查找的优缺点：

①优点：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构（链式结构不用设置监视哨），无论记录是否按关键字有序均可应用。

②缺点：平均查找长度较大，查找效率较低，对于元素不在表中或者目标位置与开始查找位置相距较远的情况比较不友好。

（4）提高查找效率的办法：

①当记录的查找概率不相等时（比如某个人的知名度高，公示信息经常被其他人查找），可按查找概率的高低存储，查找概率越高，比较次数越少。

②如果记录的查找概率无法测定时（比如通讯录中的一部分电话号码需要经常拨打，一部分基本不拨打，一段时间后过去某个常拨打的电话可能也基本不拨打），可按查找概率动态调整记录顺序，这需要在每个记录中设一个访问频度域，始终保持记录按非递增有序的次序排列（以访问频度排序），或者每次查找后均将刚查到的记录直接移至表头。

2、折半查找

（1）折半查找也称二分查找，它是一种效率较高的查找方法，但是折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在下面及后续的讨论中，均假设有序表是有序递增的。

（2）折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等则查找成功，如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

（3）折半查找每一次查找都使查找范围缩小一半，与顺序查找相比，显著地提高了查找效率。

（4）折半查找过程可用二叉树来描述，树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。把当前查找区间的中间位置作为根，把左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树称为折半查找的决策树。

①折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而决策树的形态只与表记录个数n相关，与关键字的取值无关，具有n个结点的决策树的深度为 $\left \lfloor log_{2}n \right \rfloor+1$ ，所以对于长度为n的有序表，折半查找法在查找成功时和给定值进行比较的关键字个数至多为 $\left \lfloor log_{2}n \right \rfloor+1$ 。

②在决策树中所有结点的空指针域上加一个指向一个方形结点的指针，并且称这些方形结点为决策树的外部结点（与之相对，称那些圆形结点为内部结点），那么折半查找时查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数，因此折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过 $\left \lfloor log_{2}n \right \rfloor+1$ 。

（5）算法具体实现：

①非递归实现：

int Search_Bin(SSTable ST, KeyType key)    //折半查找的非递归算法
{
	int left = 1;            //最左端
	int right = ST.length;   //最右端
	while (left <= right)     //查找区间不为空（左指针不大于右指针）
	{
		int mid = (left + right) / 2;
		if (key == ST.R[mid].key)   //查找成功
			return mid;
		else if (key < ST.R[mid].key)   //目标值在当前位置左侧，右指针左移
			right = mid - 1;
		else                            //目标值在当前位置右侧，左指针右移
			left = mid + 1;
	}
	return 0;  //查找区间为空，说明欲查找的值不在表中，返回0
}

②递归实现：

int Search_Bin(SSTable ST, KeyType key, int low, int high)  //折半查找的递归算法
{
	
	if (low > high)
		return 0;  //查找区间为空，说明欲查找的值不在表中，返回0
	int mid = (low + high) / 2;
	if (key == ST.R[mid].key)
		return mid;
	else if (key < ST.R[mid].key)
		return Search_Bin(ST, key, low, mid - 1);
	else
		return Search_Bin(ST, key, mid + 1, high);
}

（6）折半查找的优缺点：

①优点：比较次数少，查找效率高，该算法的时间复杂度为 $O(log_{2}n)$ 。

②缺点：对表结构要求高，只能用于顺序存储的有序表，所以该算法不太适用于数据元素经常变动的线性表（因为要经常排序）。

3、分块查找

（1）分块查找又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的查找方法。在此查找方法中，除表本身以外，尚需建立一个“索引表”。表本身可分为若干个子表（子表中记录数不宜过少），对每个子表（或称块）建立一个索引项（存储在索引表中），其中包括两项内容——关键字项（其值为该子表内的最大关键字）和指针项（指示该子表的第一个记录在表中的位置）。

（2）索引表按关键字有序，则表有序或者分块有序（块内无序、块间有序）。所谓“分块有序”指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，依次类推。

（3）由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找或折半查找，而块中的记录是任意排列的，则在块中只能用顺序查找。

（4）设表中有n个记录均匀分成b块，每块有s个记录。

（5）分块查找的优缺点：

①优点：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

②缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。

三、树表的查找

1、二叉排序树

（1）二叉排序树或是一棵空树，或是具有下列性质的二叉树：

①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。

②若它的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值。

③它的左、右子树也分别为二叉排序树。

（2）中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。

（3）二叉树的二叉链表存储表示：

typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;        //关键字域
	InfoType otherinfo; //其它域
}ElemType;

typedef struct BSTNode
{
	ElemType data;                     //每个结点的数据域包括关键字和其它数据项
	struct BSTNode *lchild, *rchild;   //左右孩子指针
	int count;                         //查找次数计数（仅例3的函数T3使用）
	int b;                             //平衡因子（仅例4的函数T4使用）
}BSTNode, *BSTree;

（4）二叉排序树的查找：二叉排序树可以看成一个有序表，所以在二叉排序树上进行查找和折半查找类似，也是一个逐步缩小查找范围的过程。

①算法具体实现：

BSTree SearchBST(BSTree T, KeyType key)    //递归查找
{
	if ((!T) || key == T->data.key)  //查找成功则返回目标元素的结点指针，否则返回NULL
		return T;
	else if (key < T->data.key)
		return SearchBST(T->lchild, key);   //在左子树中继续查找
	else
		return SearchBST(T->rchild, key);   //在右子树中继续查找
}

②在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1（或结点所在层次数）。因此二叉排序树的查找和折半查找类似，与给定值比较的关键字个数不超过树的深度。

③含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为n，其平均查找长度为(n+1)/2（和顺序查找相同），这是最差的情况，而最好的情况是，二叉排序树的形态和折半查找的决策树的形态相似，其平均查找长度和 $log_{2}n$ 成正比。

（5）二叉排序树的插入：要将一个关键字为key的结点*S插入二叉排序树中，则需要从根结点向下查找，当树中不存在关键字等于key的结点时才进行插入。（新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点）

①算法具体实现：

void InsertBST(BSTree* T, ElemType e)      //插入元素
{
	if (!(*T))         //找到插入位置（可理解为空的叶子结点），递归结束
	{
		BSTNode* S = (BSTNode*)malloc(sizeof(BSTNode));  //生成新结点*S
		S->data = e;
		S->lchild = S->rchild = NULL;     //新结点是叶子结点
		*T = S;             //把新结点链接到已找到的插入位置
	}
	else if (e.key < (*T)->data.key)
		InsertBST(&((*T)->lchild), e);  //小于根结点的值，将*S插入左子树
	else if (e.key > (*T)->data.key)
		InsertBST(&((*T)->rchild), e);  //大于根结点的值，将*S插入右子树
}

②二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样，是 $O\left (log_{2}n \right )$ 。

（6）二叉排序树的创建：从空的二叉排序树开始的，每输入一个结点，经过查找操作，将新结点插入当前二叉排序树的合适位置。

①算法具体实现：

void CreatBST(BSTree* T)    //创建二叉排序树
{
	*T = NULL;   //将二叉排序树T初始化为空树
	ElemType e;
	scanf("%d %d", &e.key, &e.otherinfo);
	while (e.key != ENDFLAG)    //ENDFLAG为自定义常量，作为输入结束的标志
	{
		InsertBST(T, e);   //将新元素插入二叉排序树T中
		scanf("%d %d", &e.key, &e.otherinfo);
	}
}

②一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即对无序序列进行排序的过程。不仅如此，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针，使其由指向空结点变为指向非空结点即可，这就相当于在一个有序序列上插入一个记录而不需要移动其它记录。

③不同插入次序的序列会生成不同形态的二叉排序树。

（7）二叉排序树的删除：被删除的结点可能是二叉排序树中的任何结点，删除结点后，要根据其位置不同修改其双亲结点及相关结点的指针，以保持二叉排序树的特性。

①算法具体实现：

void DeleteBST(BSTree* T, KeyType key)    //删除结点
{
	BSTree p = *T;  //从根开始查找关键字为key的结点
	BSTree f = NULL;
	while (p)
	{
		if (p->data.key == key)    //找到结点则结束循环
			break;
		f = p;
		if (p->data.key > key)
			p = p->lchild;   //在*p的左子树中继续查找
		else
			p = p->rchild;   //在*p的右子树中继续查找
	}
	if (!p) return;   //找不到被删结点则返回
	/*考虑三种情况实现p所指子树内部的处理：目标结点左右子树均不空、无右子树、无左子树*/
	BSTree q = p;
	if ((p->lchild) && (p->rchild))   //被删结点左右子树均不空
	{
		BSTree s = p->lchild;
		while (s->rchild)         //在*p的左子树中继续查找其前驱结点，即最右下结点
		{
			q = s;s = s->rchild;            //向右到尽头
		}
		p->data = s->data;            //s指向被删结点的前驱
		if (q != p)                   //重接*q的左右子树
			q->rchild = s->lchild;
		else
			q->lchild = s->lchild;
		free(s);
		return;
	}
	else if (!p->rchild)              //被删结点无右子树，只需重接其左子树
		p = p->lchild;
	else if (!p->lchild)              //被删结点无左子树，只需重接其右子树
		p = p->rchild;
	//将p所指的子树挂接到其双亲结点*f相应的位置
	if (!f) *T = p;
	else if (q == f->lchild) f->lchild = p;
	else f->rchild = p;
	free(q);
}

②同二叉排序树插入一样，二叉排序树删除的基本过程也是查找，所以时间复杂度仍是 $O\left (log_{2}n \right )$ 。

2、平衡二叉树

（1）平衡二叉树或是空树，或是具有如下特征的二叉排序树：

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

②左子树和右子树也是平衡二叉树。

（2）若将二叉树上结点的平衡因子定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1，只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

（3）当在一棵平衡二叉树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点，这时需要对平衡二叉树进行调整，调整方法是找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树（当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可，因为经过旋转处理之后子树的深度和插入之前的相同，因而不影响插入路径上所有祖先结点的平衡度）。假设最小不平衡子树的根结点为A，则失去平衡后进行调整的规律可归纳为下列4种情况：

①LL平衡旋转（右单旋转）。由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作——将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

②RR平衡旋转（左单旋转）。由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。——将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

③LR平衡旋转（先左后右双旋转）。由于在A的左孩子（L）的右子树（R）上插入新结点，A也有可能是插入到C的左子树的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转——先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。

④RL平衡旋转（先右后左双旋转）。由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转——先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。

（4）调整算法的具体实现：

①平衡二叉树的二叉链表存储表示：

#define LH 1 //平衡因子1
#define EH 0 //平衡因子0
#define RH -1 //平衡因子-1
typedef int AVLElemtype;
typedef struct AVLNode
{
	AVLElemtype key;           //关键字域
	int bf;                    //平衡因子
	AVLNode *lchild, *rchild;  //左右孩子指针
}AVLNode, *AVLTree;

②旋转算法的实现：

void LeftRotate(AVLTree *T)   //左旋
{
	AVLTree Rchild = (*T)->rchild;
	(*T)->rchild = Rchild->lchild;
	Rchild->lchild = *T;
	*T = Rchild;
}
void RightRotate(AVLTree *T)   //右旋
{
	AVLTree Lchild = (*T)->lchild;
	(*T)->lchild = Lchild->rchild;
	Lchild->rchild = *T;
	*T = Lchild;
}

③核心算法（平衡调整）实现：

[1]LL、LR：

void LeftBalance(AVLTree *T)
{
	AVLTree L = (*T)->lchild;  //最小不平衡树根的左孩子
	AVLTree Lr;
	switch (L->bf) 
	{
	case LH:  //左孩子平衡因子为1，属于LL情况
		//LL旋转
		(*T)->bf = L->bf = EH;  //树根和它的左孩子的平衡因子改为0
		RightRotate(T);  //右旋
		break;
	case RH:  //左孩子平衡因子为-1，属于LR情况
		//LR旋转
		Lr = L->rchild;  //树根的左孩子的右孩子
		switch (Lr->bf)
		{
		case LH:  //树根的左孩子的右孩子的左边插入了新结点
			(*T)->bf = RH;
			L->bf = EH;
			break;
		case EH:
			(*T)->bf = L->bf = EH;
			break;
		case RH:  //树根的左孩子的右孩子的右边插入了新结点
			(*T)->bf = EH;
			L->bf = LH;
			break;
		}
		Lr->bf = EH;
		LeftRotate(&(*T)->lchild);  //左旋
		RightRotate(T);             //右旋
	}
}

[2]RL、RR：

void RightBalance(AVLTree *T)
{
	AVLTree R = (*T)->rchild;  //最小不平衡树根的右孩子
	AVLTree Rl;
	switch (R->bf)
	{
	case RH:   //右孩子平衡因子为-1，属于RR情况
		//RR旋转
		(*T)->bf = R->bf = EH;
		LeftRotate(T);
		break;
	case LH:   //右孩子平衡因子为1，属于RL情况
		//RL旋转
		Rl = R->lchild;
		switch (Rl->bf)
		{
		case LH:  //树根的右孩子的左孩子的左边插入了新结点
			(*T)->bf = EH;
			R->bf = RH;
			break;
		case EH:
			(*T)->bf = R->bf = EH;
			break;
		case RH:  //树根的右孩子的左孩子的右边插入了新结点
			(*T)->bf = LH;
			R->bf = EH;
			break;
		}
		Rl->bf = EH;
		RightRotate(&(*T)->rchild);  //右旋
		LeftRotate(T);               //左旋
	}
}

（5）平衡二叉搜索树的插入：

①算法步骤：

[1]若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1。

[2]若e的关键字和BBST的根结点的关键字相等，则不进行插入。

[3]若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理：

#1 BBST的根结点的平衡因子为-1（右子树的深度大于左子树的深度）：将根结点的平衡因子更改为0，BBST的深度不变。

#2 BBST的根结点的平衡因子为0（左、右子树的深度相等）：将根结点的平衡因子更改为1，BBST的深度增1。

#3 BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1，则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变。

#4 若BBST的左子树根结点的平衡因子为-1，则需进行先向左、后向右的双向旋转平衡处理，并且在旋转处理之后修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

[4]若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+1)时，分别就下列不同情况处理：

#1 BBST的根结点的平衡因子为1（右子树的深度小于左子树的深度）：将根结点的平衡因子更改为0，BBST的深度不变。

#2 BBST的根结点的平衡因子为0（左、右子树的深度相等）：将根结点的平衡因子更改为1，BBST的深度增1。

#3 BBST的根结点的平衡因子为-1（左子树的深度小于右子树的深度）：若BBST的右子树根结点的平衡因子为-1，则需进行单向左旋平衡处理，并且在左旋处理之后，将根结点和其左子树根结点的平衡因子更改为0，树的深度不变。

#4 若BBST的右子树根结点的平衡因子为1，则需进行先向右、后向左的双向旋转平衡处理，并且在旋转处理之后修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

②算法的具体实现：

void Insert_AVL(AVLTree *T, AVLElemtype key, bool *taller) 
{
	//T为要插入结点的双亲结点，key为要插入数据的值
	if (!(*T))  //若T为空，则创建一个结点，并初始化
	{
		*T = (AVLTree)malloc(sizeof(AVLNode));
		(*T)->lchild = (*T)->rchild = NULL;
		(*T)->bf = EH;
		(*T)->key = key;
		*taller = true;
	}
	if (key < (*T)->key) 
	{   //如果插入值小于T的key值，则递归T的左子树，直到找到一个NULL结点
		Insert_AVL(&(*T)->lchild, key, taller);
		if (*taller) //判断树是否变高了
		{
			switch ((*T)->bf)  //以T为根插入结点，则T的平衡因子发生变化
			{
			case LH:  //如果T的平衡因子为-1，向T的左孩子插入结点，需要左平衡
				LeftBalance(T);
				*taller = false;  //经过平衡后taller = false，因为T经过左调整后，变得平衡了
				break;
			case EH:  //如果T的平衡因子为0，向T的左孩子插入结点
				(*T)->bf = LH;  //T的平衡因子改为1
				*taller = true;    //此时T的高度发生变化
				break;
			case RH:  //如果T的平衡因子为-1，向T的左孩子插入结点
				(*T)->bf = EH;  //T的平衡因子改为0
				*taller = false;  //高度未发生变化
				break;
			}
		}
	}
	else 
	{   //如果插入值大于T的key值，则递归T的右子树，直到找到一个NULL结点
		Insert_AVL(&(*T)->rchild, key, taller);
		if (*taller) //判断树是否变高了
		{
			switch ((*T)->bf)  //以T为根插入结点，则T的平衡因子发生变化
			{
			case LH:  //如果T的平衡因子为1，向T的右孩子插入结点
				(*T)->bf = EH;  //T的平衡因子改为0
				*taller = false;
				break;
			case EH:  //如果T的平衡因子为0，向T的右孩子插入结点
				(*T)->bf = RH;  //T的平衡因子改为-1
				*taller = true;
				break;
			case RH:  //如果T的平衡因子为-1，向T的右孩子插入结点，需要右平衡
				RightBalance(T);
				*taller = false;  //经过平衡后taller = false，因为T经过右调整后，变得平衡了
				break;
			}
		}
	}
}

3、B－树

（1）B－树又称多路平衡查找树，B－树中所有结点的孩子个数的最大值称为B－树的阶，通常用m表示，一棵m阶的B－树，或为空树，或为满足下列特性的m叉树：

①树中每个结点至多有m棵子树。

②若根结点不是叶子结点，则至少有两棵子树。

③除根之外的所有非终端结点至少有 $\left \lceil m/2 \right \rceil$ 棵树，也就是至少含有 $\left \lceil m/2 \right \rceil-1$ 个关键字。

④所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空，引入失败结点是为了便于分析B－树的查找性能）。

⑤所有的非终端结点最多有m-1个关键字。

（2）m阶B树的核心特性：

（3）含n个关键字的m阶B树，其高度h（不包括叶子结点）满足

（4）B－树的查找：

①例如，在下图所示的B－树上查找关键字47的过程如下：首先从根开始，根据根结点指针找到*a结点，因*a结点中只有一个关键字，且47>35，若查找的记录存在，则必在指针P1所指的子树内，顺指针找到*c结点，该结点有两个关键字（43和78），而43<47<78，若查找的记录存在，则必在指针P1所指的子树中。同样，顺指针找到*g结点，在该结点中顺序查找，找到关键字47，由此，查找成功。

②查找不成功的过程也类似，例如在同一棵树中查找23，从根开始，因为23<35，则顺该结点中指针P0找到*b结点，又因为*b结点中只有一个关键字18，且23>18，所以顺结点中第二个指针P1找到*e结点。同理，因为23<27，则顺指针往下找，此时因指针所指为叶子结点，说明此棵B－树中不存在关键字23，查找以失败而告终。

③由此可见，在B-树上进行查找的过程是一个顺指针查找结点，和查找结点的关键字交叉进行的过程。

（5）B－树的插入：

①B－树是动态查找树，因此其是从空树起，在查找的过程中通过逐个插入关键字而得到。

②每次插入一个关键字，首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则表明结点已满，需要进行结点的“分裂”，将此结点在同一层分成两个结点。一般情况下，结点分裂方法是：以中间关键字为界把结点一分为二，并把中间关键字向上插入双亲结点上，若双亲结点已满，则采用同样的方法继续分裂，最坏的情况下会一直分裂到树根结点，这时B－树高度增加1。

③举例：下图所示为3阶的B－树，未画出叶子结点。

[1]在树中插入关键字30，首先从根*a开始查找，确定30应插在结点*d中，插入后*d中的关键字数目不超过2（即m-1），第一个关键字插入完成。

[2]在树中插入关键字26，通过查找确定关键字26应插在结点*d中，但插入后*d中的关键字数目大于2，需要将*d分裂为两个结点，关键字26及其前、后两个指针仍保留在结点*d中，关键字37及其前、后两个指针存储到新的结点*d'中，同时将关键字30和指示结点*d'的指针插入到其双亲结点中。

[3]在树中插入关键字85，通过查找确定关键字85应插在结点*g中，但插入后*g中的关键字数目大于2，需要将*g分裂为两个结点，关键字61及其前、后两个指针仍保留在结点*g中，关键字85及其前、后两个指针存储到新的结点*g'中，同时将关键字70和指示结点*g'的指针插入到其双亲结点中。完成一次分裂后，*e中的关键字数目大于2，需要将*e分裂为两个结点，关键字53及其前、后两个指针仍保留在结点*e中，关键字90及其前、后两个指针存储到新的结点*e'中，同时将关键字70和指示结点*e'的指针插入到其双亲结点中。

[4]在树中插入关键字7，需要进行三次分裂，由于影响到根结点，B－树的高度+1。

（6）B－树的删除：

①m阶B－树的删除操作，是指在B－树的某个结点中删除指定的关键字及其邻近的一个指针，删除后应该进行调整使该树仍然满足B－树的定义，也就是要保证每个结点的关键字数目区间为 $[\left \lceil m/2 \right \rceil-1,m]$ 。

②删除记录后，结点的关键字个数如果小于 $\left \lceil m/2 \right \rceil-1$ ，则要进行“合并”结点的操作。

[1]若该结点为最下层的非终端结点，由于其指针均为空，删除后不会影响其它结点，可直接删除。

[2]若该结点不是最下层的非终端结点，其邻近的指针则指向一棵子树，不可直接删除，此时可将要删除记录用其右（左）边邻近指针指向的子树中关键字最小（大）的记录（该记录必定在最下层的非终端结点中）替换；若与被删除关键字所在结点相邻的左、右兄弟结点的关键字个数均为 $\left \lceil m/2 \right \rceil-1$ ，则将关键字删除后与左或右兄弟结点及双亲结点中的关键字进行合并，在合并过程中，双亲结点中的关键字个数会减1，若其双亲结点是根结点且关键字个数减少至0（根结点关键字个数为1时，有2棵子树），则直接将根结点删除，合并后的新结点成为根，若双亲结点不是根结点，且关键字个数减少到 $\left \lceil m/2 \right \rceil-2$ ，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B－树的要求为止。

③举例：下图所示为3阶的B－树，未画出叶子结点。

[1]删除关键字12，不需要调整。

[2]删除关键字50，需要将其右兄弟结点中的61上移至*e结点中，而将*e结点中的53移至*f，双亲结点中的关键字数目不变。

[3]删除关键字53，*f结点中原本就只剩53一个元素，所以直接删去*f结点，并将其剩余信息（指针“空”）和双亲*e结点中的61一起合并到右兄弟结点*g中。

[4]删除关键字37，双亲结点*b中剩余信息（指针c）应和其双亲结点*a中关键字45一起合并至右兄弟结点*e中。

4、B＋树

（1）一棵m阶的B＋树需满足下列条件：

①每个分支结点最多有m棵子树（孩子结点）。

②非叶根结点至少有两棵子树，其他每个分支结点至少有 $\left \lceil m/2 \right \rceil$ 棵子树。

③结点的子树个数与关键字个数相等。

④所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（说明支持顺序查找）。

⑤所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

（2）B＋树和B－树对比：

（3）在B＋树上进行随机查找、插入和删除的过程基本上与B－树类似，这里不再赘述。

四、散列表的查找

1、散列表的基本概念

（1）散列表（Hash Table），又称哈希表，是一种数据结构，占用一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录，通常散列表的存储空间是一个一维数组，散列地址是数组的下标。散列表的特点是数据元素的关键字与其存储地址直接相关。

（2）如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无须作比较或只需作很少的比较，按照这种关系直接由关键字找到相应的记录，这就是散列查找法的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较，因此，散列查找法又叫杂凑法或散列法。

（3）散列函数和散列地址：在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H(key)，称这个对应关系H为散列函数，p为散列地址。（每一个关键字只能有一个散列地址与之对应）

（4）冲突和同义词：对不同的关键字可能得到同一散列地址，这种现象称为冲突（冲突基本上不可避免，只能选择更优的散列函数尽可能地减少冲突的出现），具有相同函数值的关键字对该散列函数来说称作同义词（互为同义词）。

2、散列表的构造方法

（1）假设散列表表长为m，选择一个不大于m的数p，用p去除关键字，除后所得余数为散列地址，即H(key) = key % p，这个方法的关键是选取适当的p，一般情况下，可以选p为小于表长的最大质数。

（2）上面介绍的构造方法是除留余数法，实际上还有直接定址法、数字分析法和平方折中法等，但相比之下并不常用。

①直接定址法：H(key) = key 或 H(key) = a*key + b，其中a和b是常数。这种方法计算最简单，且不会产生冲突，它适合关键字的分布基本连续的情况，若关键字分布不连续，将会导致空位较多，造成存储空间的浪费。

②数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等，也可能在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

③平方取中法：取关键字的平方值的中间几位作为散列地址。，具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

（3）无论采用哪种构造方法，一般来说，应根据具体问题选用不同的散列函数，通常要考虑的因素有散列表的长度、关键字的长度、关键字的分布情况、计算散列函数所需的时间和记录的查找频率。

（4）构造一个“好”的散列函数应遵循以下两条原则：

①函数计算要简单，每一关键字只能有一个散列地址与之对应。

②函数的值域需在表长的范围内，计算出的散列地址的分布应均匀，尽可能减少冲突。（散列的地址空间也应尽量小）

3、插入元素过程中处理冲突的方法

（1）开放地址法：

①开放地址法的基本思想是：把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址 $H_{0}$ = H(key)发生冲突时，以 $H_{0}$ 为基础，采取合适方法计算得到另一个地址 $H_{1}$ ，如果 $H_{1}$ 仍然发生冲突，以 $H_{1}$ 为基础再求下一个地址 $H_{2}$ ，依此类推，直至Hk不发生冲突为止，则 $H_{k}$ 为该记录在表中的散列地址。

②通常把寻找“下一个”空位的过程称为探测，上述方法可用公式表示。

上式中H(key)为散列函数，m为散列表表长， $d_{i}$ 为增量序列，根据增量序列取值的不同可分为3种探测方法。

线性探测法的优点是只要散列表未填满，总能找到一个不发生冲突的地址，缺点是会产生“二次聚集”现象；二次探测法和伪随机探测法的优点是可以避免“二次聚集”现象，但其缺点也很显然，不能保证一定找到不发生冲突的地址。

（2）链地址法：

①链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称之为同义词链表。有m个散列地址就有m个单链表，同时用数组HT[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插人以HT[i]为头结点的单链表。

②链地址法的操作步骤：取数据元素的关键字key，计算其散列函数值（地址），若该地址对应的链表为空，则将该元素插入此链表，若该地址对应的链表不为空，则利用链表的前插法或后插法将该元素插入此链表。

③链地址法的优点是非同义词不会冲突，无“聚集”现象，而且链表上的结点空间动态申请，更适合于表长不确定的情况。

（3）再散列法（再哈希法）：除了原始的散列函数H(key)之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止。

4、查找算法的实现

（1）以开放地址法（线性探测）为例，查找算法的具体实现：

#define M 20  //表长

typedef int KeyType;
typedef int InfoType;

typedef struct
{
	KeyType key;          //关键字项
	InfoType otherinfo;   //其它数据项
}HashTable[M];

int H(KeyType key)   //散列函数
{
	return key % (M - 3);
}

int SearchHash(HashTable HT, KeyType key)    //查找
{
	int H0 = H(key);   //计算散列地址
	if (HT[H0].key == NULLKEY)  //单元H0为空，所查元素不存在
		return -1;
	else if (HT[H0].key == key)
		return H0; //一次查找成功
	else
	{
		for (int i = 1; i < M; i++)
		{
			int Hi = (H0 + i) % M;        //按照线性探测法计算下一个散列地址Hi
			if (HT[Hi].key == NULLKEY)    //NULLKEY是单元为空的标记，自行定义
				return -1;
			else if (HT[Hi].key == key)  //第一次查找不成功，后来查找成功
				return Hi;
		}
	}
	return -1;  //查找失败
}

（2）查找过程中需和给定值进行比较的关键字的个数取决于3个因素，即散列函数、处理冲突的方法和散列表的装填因子，散列表的装填因子定义为（表中填入的记录数/散列表的长度），表示散列表的装填程度，装填因子越大，表中记录越多，插入新元素时发生冲突的可能性越大，查找时需要比较的关键字可能就越多。

五、算法设计举例

1、例1

（1）问题描述：设计一个判别给定二叉树是否为二叉排序树的算法。

（2）代码：

BiTree pre = NULL;
void T1(BiTree T, int* flag)
{
	if (T != NULL && flag)  //flag初始值为1
	{
		T1(T->lchild, flag);  //中序遍历左子树
		if (pre == NULL)      //中序遍历的第一个结点不必判断
			pre = T;
		else if (pre->data.key < T->data.key)
			pre = T;          //前驱指针指向当前结点
		else
			flag = 0;         //不是二叉排序树，递归结束
		T1(T->rchild, flag);  //中序遍历右子树
	}
}

2、例2

（1）问题描述：已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为(lchild,data,rchild)，设计递归算法从小到大输出二叉排序树中所有数据值大于等于x的结点的数据，要求先找到第一个满足条件的结点再依次输出其它满足条件的结点。

（2）代码：

void T2(BSTree T, int x)
{
	if (T != NULL)
	{
		T2(T->lchild, x);
		if (T->data.key >= x)
			printf("%d ", T->data.key);
		T2(T->rchild, x);
	}
}

3、例3

（1）问题描述：在二叉排序树中查找值为x的结点，若找到则计数count加1，否则将其作为一个新结点插入树中。

（2）代码：

void T3(BSTree &T, int x)
{
	BSTree s = (BSTree)malloc(sizeof(BSTNode));
	s->data.key = x;
	s->count = 0;
	s->lchild = s->rchild = NULL;
	if (T == NULL)              //如果该树为空，则创建新树，结束函数
	{
		T = s;
		s->count++;
		return;
	}
	BSTree f = NULL;
	BSTree q = T;
	while (q)
	{
		if (q->data.key == x)
		{
			q->count++;
			free(s);
			return;
		}
		f = q;
		if (q->data.key < x)    //当前结点值小于x，使指针指向右子树
		{
			q = q->rchild;
		}
		else                    //当前结点值大于x，使指针指向左子树
		{
			q = q->lchild;
		}
	}
	if (f->data.key > x)        //如果找不到，就将结点插入树中
	{
		f->lchild = s;
		s->count++;
	}
	else
	{
		f->rchild = s;
		s->count++;
	}
}

4、例4

（1）问题描述：假设一棵平衡二叉树中的每个结点都标明了平衡因子b，求平衡二叉树的高度（这里省略了判断是否为平衡二叉树的步骤）。

（2）代码：

int T4(BSTree T)
{
	if (T != NULL)
	{
		if (T->b <= 0)
			return T4(T->rchild) + 1;
		else
			return T4(T->lchild) + 1;
	}
	else
		return 0;
}

数据结构 第七章（查找算法）

一、查找的基本概念

1、查找表

2、关键字

3、查找

4、动态查找表和静态查找表

5、平均查找长度

二、线性表的查找

1、顺序查找

2、折半查找

3、分块查找

三、树表的查找

1、二叉排序树

2、平衡二叉树

3、B－树

4、B＋树

四、散列表的查找

1、散列表的基本概念

2、散列表的构造方法

3、插入元素过程中处理冲突的方法

4、查找算法的实现

五、算法设计举例

1、例1

2、例2

3、例3

4、例4

相关推荐

最近更新

热门阅读