基本概念

  • 查找是在数据集合中寻找满足某种条件的数据元素的过程
  • 查找表：用于查找的数据集合称为查找表
  • 关键字：数据元素中可以唯一标识某个数据项的值
  • 平均查找长度（ASL)：在所有的查找的过程中进行比较的次数,ASL反应了查找算法的时间复杂度

顺序查找

1
从头到尾进行查找的操作
  • 适用于顺序表、链表，元素是否无序无关紧要
  • 不管怎样对顺序查找进行优化，时间复杂度的量级都是O(n)
  • 查找成功时的平均查找长度是（n+1)/2

二分查找（折半查找）

  • 必须是有序的顺序表
  • 仅适合顺序存储的结构
  • 二分查找的时间复杂度是O(log2n)
  • 折半查找的判定树log(2(n+1))向上取整
  • 折半查找查找成功时的平均查找长度是 log2(n+1)-1

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//折半查找核心代码
int  Binary_Search(SeqList L,Elemtype key)
{
	int low=0,high=L.length-1,mid;
	while(key<=high)
	{
		mid=(low+high)/2;
		if(key==mid)
			return mid;
		else if(L.elem[mid]>key)
			high=mid-1;    //在左半部分进行查找 
		else 
		    low=mid+1;    //在右半部分进行查找 
	}
 }

分块查找（索引顺序查找）

  • 块内是无序的，但是块间是有序的
  • 每个块内有一个最大关键字

二叉排序树

二叉排序树又称为二叉查找树

  • 左子树结点值<根节点值<右子树结点值
  • 通过中序遍历（左根右）可以得到一个递增的序列

二叉排序树的实现

  • 采用非递归方式时的最坏的空间复杂度是O(1)
  • 采用递归方式时的最坏时间复杂度是O(n)

二叉排序树的插入

  • 新插入的结点都是叶子结点
  • 不能存在相同的结点，若树中已经存在了，就插入失败。

二叉排序树的删除

1
二叉排序树的删除后的结果需要仍然保持二叉排序树的特性
  • 如果删除的是叶子结点，可以直接删除，不会破坏二叉排序树的性质
  • 如果删除的结点有左孩子或者是右孩子，那么让其子代替它的位置。
  • 若果删除的这个结点同时含有左子树和右子树，将这个结点的直接后继或者直接前驱替代这个节点，然后要保证仍然维持二叉排序树的特性。（注：二叉排序树的中序遍历去求后继和前驱）

二叉排序树的查找效率

  • 最坏的情况，每个结点都只有一个分支，树高h=结点数n，平均查找长度为O(n)
  • 平均的查找长度是O(log2n)
  • 树的最小的高度是log2n向下取整+1
  • 二叉排序树的最理想的深度是log2(n+1)向上取整
  • 具有n个结点的二叉排序树查找某个关键词时，最多进行n次比较（注意：不是平衡二叉树）

image-20230810195638522

平衡二叉树

1
平衡二叉树，简称平衡树，树上的任一结点的左子树和右子树的高度只差不超过1
  • 结点的平衡因子=左子树高度-右子树高度
  • 平衡二叉树的平衡因子只能是-1、0、1
  • 当平衡因子的绝对值大于1时，就不能构成平衡二叉树

平衡二叉树的插入

注：每次调整的对象是“最小的不平衡子树”

  • LL型（右旋）:A结点的左孩子的左子树插入了新的结点导致了不平衡，需要让A的左孩子B向右上旋转，B称为根结点，A称为B的右孩子，BL不动，BR变成A的左子树。（操作的点是最小不平衡子树的根结点的左孩子结点）

    image-20230810210944608

  • RR型（左旋）：在结点A的右孩子的右子树上插入了新结点，将A的右孩子进行左上旋操作，B变为根结点，A变为B的左孩子结点，其余的按平衡二叉树的性质进行排序存放。（操作的点是最小不平衡子树的根结点的右孩子结点）

    image-20230810211430960

  • LR型（先左旋后右旋）：平衡二叉树根结点的左孩子的右子树上插入了新的元素导致了不平衡。先让C进行左旋操作，B称为C的左孩子，接着让C进行右旋操作，此时C变为树的根结点，A成为C的右孩子结点，其余按平衡二叉树进行填充。（操作的点是最小不平衡子树的根结点的左子树的右孩子结点）

    image-20230810212121795

  • RL型（先右旋后左旋）：平衡二叉树根结点的右孩子的左子树上插入了新的元素导致了不平衡。先让C进行右旋操作，B称为C的右孩子，接着让C进行左旋操作，此时C变为树的根结点，A成为C的左孩子结点，其余按平衡二叉树进行填充。（操作的点是最小不平衡子树的根结点的右子树的左孩子结点）

    image-20230810212352805

image-20230810212448701

注：在插入操作中，只要将最小不平衡调整为平衡，则其他的祖先结点都会恢复平衡。

练习

RR型调整

image-20230810221126409

LR型调整

image-20230810221141000

RL型调整

image-20230810221110628

散列查找

hash函数

hash函数又叫散列函数，可以将关键字按照关键字的值映射成关键字对应地址上的函数。

注：散列查找是典型的用空间换取时间的查找操作，只要涉及的散列函数是合理的，则散列表的长度 越长，冲突的概率就会越低。

冲突

关键经过hash函数的作用后，结果一样，就发生了冲突。发生冲突的关键字称为“同义词”

散列表

散列表进行查找的时间复杂度是O(1)

直接定址法

H(key)=key

除留余数法

H(key)=key%p,其中p取的是小于等于散列表长的最大质数。

平方取中法

数字分析法

处理冲突的方法

开放地址法

所谓的开放定值法就是存放新表项的空闲地址既向它的同义词开放，又向它的非同义词进行开放。

H=((h(key)+di))%m

d取0到m-1

线性探测法

平方探测法

伪随机序列法

拉链法

题目总结

7.2.4

image-20230809214301171

解析：折半查找一般情况下是优于顺序查找的

image-20230809214456847

image-20230809214514697

解析：

image-20230809220020432

image-20230809220035686

解析：使用平衡二叉树进行思考，比较简单

image-20230809220057543

image-20230809220149509

解析：ASL=(s*s+2s+n)/(2s)，s=123/3,n=123 ,解得ASL=23

image-20230815210638110

解析：索引顺序结构就是分块查找，分块的个数是根号n，所以是255块，接着在块内使用二分查找，二分查找最多是二分查找判定树的树高为log2(n+1)向下取整

下面这个二叉排序树的查找失败的平均查找长度是

image-20230810195238714

解析:最左下面的那个方框失败的话是比较了3次，同理同行的元素都是比较3次

查找失败：ASL=（7x3+2x4)/9=29/9

7.3.4

image-20230815224329606

解析：因为二叉排序树的查找是从根结点出发向下进行的，其查找的长度取决于树的高度

image-20230811221306621

解析：注意这是二叉排序树，不是平衡二叉树，高度可以是n，所以最多进行n次比较

image-20230811221421944

解析：n个结点的二叉排序树的最理想的深度是log2(n+1)向上取整

image-20230811221542650

解析：

1
2
3
4
5
递推公式
n0=0
n1=1
n2=2
nh=1+nh-1+nh-2

image-20230811221635946

1
2
3
4
5
递推公式
n0=0
n1=1
n2=2
nh=1+nh-1+nh-2

image-20230811222336678

解析：A选项是因为在访问91之后又访问24说明后面不会大于91，但是又出现了94比91大

image-20230811222357104

解析:A选项的的911后面是240，说明后面没有比911大的数字，但是出现了912

image-20230815224603643

解析：因为是二叉排序树不是平衡二叉树，不需要重新分裂和组合

7.5.4

image-20230815230320590

解析：散列表的堆积现象可以发生在同义词之间或者非同义词之间

image-20230815230421367

解析：同义词之间的冲突不是聚集现象，链地址法处理冲突是同义词放在一起的不会造成聚集现象

image-20230815230748033

解析：装填因子是记录个数比上散列表的长度，装填因子增大记录数增多，更加容易发生冲突。所应该减小装填因子。