0%

数据结构复习笔记7-查找

8.查找

顺序表查找;有序表查找;索引顺序表查找

顺序表查找


1
2
3
4
5
6
7
8
9
10
11
12
// 算法 9.1
// 在顺序表 ST 中顺序查找其关键字等于 key 的数据元素。若找到,
// 则函数值为该元素在表中的位置,否则为 0

int Search_Seq(SSTable ST, KeyType key)
{
ST.elem[0].key = key; // “哨兵”
// 从后往前找
for(i - ST.length; !EQ(ST.elem[i].key, key); --i);

return i; // 找不到时, i 为 0
}

有序表查找


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 算法 9.2
// 在有序表 ST 中折半查找其关键字等于 key 的数据元素。若找到,
// 则函数值为该元素在表中的位置,否则为 0

int Search_Bin(SSTable ST, KeyType key)
{
low = 1; high = ST.length; // 置区间初值

while(low <= high)
{
mid = (low + high) / 2;
if(EQ(key, ST.elem[mid],key))
return mid; // 找到待查元素
else if(LT(key, ST.elem[mid].key))// 在前半部分找
high = mid - 1;
else // 在后半部分找
low = mid + 1;
}

return 0;
}

索引顺序表查找

  • 存储结构:原表 + 索引表
    • 索引表的建立:对表进行从前到到后按原来的顺序分块,每块找出最大值(作为索引表的关键字),和块在表中的范围(如块起始地址)一起存储在另一个表中(这个表便叫做索引表)。对索引表按关键字排序,则可使得原表分块有序。
  • 查找流程:
    1. 先在索引表中查找(顺序、二分均可),根据待查关键字和索引的比较,确定下一步在原表中查找范围。
    2. 然后在上一步得到的范围基础上在原表对应位置区间顺序查找。

二叉排序树;平衡二叉树;B-树

二叉排序树

定义

  • 定义:二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树:
    • 若左子树非空,则左子树上所有结点的关键字值均小于根节点的关键字值
    • 若右子树非空,则右子树上所有结点的关键字值均大于根节点的关键字值
    • 左、右子树本身也分别是一棵二叉排序树
  • 重要结论(★★★):对二叉排序树进行中序遍历,可得到一个递增有序的序列

查找


1
2
3
4
5
6
7
8
9
10
BiTree SearchBST(BiTree T,KeyType key)
{ /* 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素, */
/* 若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。算法9.5(a) */
if((!T)||EQ(key,T->data.key))
return T; /* 查找结束 */
else if LT(key,T->data.key) /* 在左子树中继续查找 */
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key); /* 在右子树中继续查找 */
}

插入


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SearchBST1(BiTree *T,KeyType key,BiTree f,BiTree *p,Status *flag) /* 算法9.5(b)改 */
{ /* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素,若查找 */
/* 成功,则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上 */
/* 访问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL */
if(!*T) /* 查找不成功 */
{
*p=f;
*flag=FALSE;
}
else if EQ(key,(*T)->data.key) /* 查找成功 */
{
*p=*T;
*flag=TRUE;
}
else if LT(key,(*T)->data.key)
SearchBST1(&(*T)->lchild,key,*T,p,flag); /* 在左子树中继续查找 */
else
SearchBST1(&(*T)->rchild,key,*T,p,flag); /* 在右子树中继续查找 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Status InsertBST(BiTree *T, ElemType e)
{ /* 当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE, */
/* 否则返回FALSE。算法9.6(改) */
BiTree p,s;
Status flag;
SearchBST1(T,e.key,NULL,&p,&flag);
if(!flag) /* 查找不成功 */
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p)
*T=s; /* 被插结点*s为新的根结点 */
else if LT(e.key,p->data.key)
p->lchild=s; /* 被插结点*s为左孩子 */
else
p->rchild=s; /* 被插结点*s为右孩子 */
return TRUE;
}
else
return FALSE; /* 树中已有关键字相同的结点,不再插入 */
}

删除


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Delete(BiTree *p)
{ /* 从二叉排序树中删除结点p,并重接它的左或右子树。算法9.8 */
BiTree q,s;
if(!(*p)->rchild) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */
{
q=*p;
*p=(*p)->lchild;
free(q);
}
else if(!(*p)->lchild) /* 只需重接它的右子树 */
{
q=*p;
*p=(*p)->rchild;
free(q);
}
else /* 左右子树均不空 */
{
q=*p;
s=(*p)->lchild;
while(s->rchild) /* 转左,然后向右到尽头(找待删结点的前驱) */
{
q=s;
s=s->rchild;
}
(*p)->data=s->data; /* s指向被删结点的"前驱"(将被删结点前驱的值取代被删结点的值) */
if(q!=*p)
q->rchild=s->lchild; /* 重接*q的右子树 */
else
q->lchild=s->lchild; /* 重接*q的左子树 */
free(s);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status DeleteBST(BiTree *T,KeyType key)
{ /* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */
/* 并返回TRUE;否则返回FALSE。算法9.7 */
if(!*T) /* 不存在关键字等于key的数据元素 */
return FALSE;
else
{
if EQ(key,(*T)->data.key) /* 找到关键字等于key的数据元素 */
Delete(T);
else if LT(key,(*T)->data.key)
DeleteBST(&(*T)->lchild,key);
else
DeleteBST(&(*T)->rchild,key);
return TRUE;
}
}

右子树空
左子树空
左右均不空

平衡二叉树(AVL)

定义

  • 任意节点的左、右子树高度差的绝对值不超过 1 的排序二叉树。

插入

  • 插入流程类似排序二叉树,但插入过程中需要保证其平衡,所以可能需要对树进行旋转。下面列举了各种旋转的情况:

    1. LL 平衡旋转
    LL平衡旋转
    1. RR 平衡旋转

      RR平衡旋转
    2. LR 平衡旋转

    LR平衡旋转
    1. RL 平衡旋转
    RL平衡旋转

查找

  • 查找过程与排序查找树类似
  • (★★★★★)重要结论 1 :假设以 \(n_h\) 表示深度为 \(h\) 的平衡树中含有的最少结点数,则有

\[ n_0 = 0,n_1 = 1,n_2 =2 \]

并且 \[ n_h=n_{h-1}+n_{h-2}+1 \]

  • (★★★★★)重要结论 2 :含有 \(n\) 个结点的平衡二叉树的最大深度为 \(O(log_2n)\)

B-树(部分书上写成 B 树)

定义

  • 一棵 m 阶 B 树或为空树,或为满足如下特性的 m 叉树
    1. 树的每个结点至多有 m 棵子树(即至多有 m-1 个关键字
    2. 结点不是终端结点,则至少有两棵子树(即至少有 1 个关键字
    3. 根结点外的所有非叶子结点至少有 \(\lceil \frac{m}{2}\rceil\) 棵子树(即至少有 \(\lceil \frac{m}{2}\rceil -1\) 个关键字
    4. 所有非叶子结点结构如下:
n \(P_0\) \(K_1\) \(P_1\) \(K_2\) \(P_2\) \(\cdots\) \(P_n\) \(K_n\)
关键字个数 指向子树的根结点指针 0 关键字 1 指向子树的根结点指针 1 关键字 2 指向子树的根结点指针 2 指向子树的根结点指针 n 关键字 n

其中 \(K_i<K_j, 当i<j​\)

\(P_{i-1}\) 所指子树中的所有结点的关键字均小于 \(K_i\)

\(P_i​\) 所指子树中的所有结点的关键字均大于 \(K_i​\)

(★★★★★)\(\lceil \frac{m}{2}\rceil -1\le n\le m-1​\)

高度

  • 不包括最后的不带任何信息的叶结点所处的那一层
  • (★★★★★)取值范围

\[ log_m(n+1)\le h \le log_{\lceil \frac{m}{2}\rceil}(\frac{n+1}{2})+1 \]

查找

  • 类似二叉查找树,只不过有多路分支

(★★★★★)插入

  • 插入流程
    • 定位:找到利用查找算法找到插入位置
    • 插入
      • 若插入后结点关键字个数 < m,可直接插入
      • 若插入后结点关键字个数 > m - 1,则需分裂
        • (★★★★★)分裂方法
          • 在插入位置处新建一个兄弟节点,从中间位置(\(\lceil \frac{m}{2}\rceil\)) 将关键字分为左右部分
          • 左部分放在原结点,右部分放在新结点,中间的结点放在父结点
          • 若此时使得父结点关键字也超过了上限,那么以此类推,直至传到根结点。
分裂

(★★★★★)删除

  • 当所删除的关键字 k 不在终端结点(这里的终端结点指最底层非叶子结点,下同)
    1. 小于 k 的子树中关键字个数 > \(\lceil \frac{m}{2}\rceil -1​\) ,则找出(中序)前驱值 k' ,并用 k' 取代 k ,再递归地删除 k' 即可
    2. 大于 k 的子树中关键字个数 > \(\lceil \frac{m}{2}\rceil -1\) ,则找出(中序)后继值 k' ,并用 k' 取代 k ,再递归地删除 k' 即可(前两点貌似与二叉排序树中的删除类似)
    3. 若前后两个子树中关键字个数 均为 \(\lceil \frac{m}{2}\rceil -1\) ,则直接将两个子结点合并,再直接删除 k 即可(如下图)
非终端合并
  • 当所删除的关键字 k 在终端结点
    1. 若被删除关键字所在结点的关键字个数 > \(\lceil \frac{m}{2}\rceil -1\) ,则直接删除
    2. 兄弟够借(如下图)
    3. 兄弟不够借(如下图)
终端兄弟借

哈希表的构造和冲突处理方法

哈希表的构造

  • 这里的构造通常指哈希函数的构造。下面是几种构造方法
    1. 直接定址法:取关键字或关键字的某个线性函数值为哈希地址
    2. 数字分析法:设关键字是 r 进制数,而 r 个数码在各位上出现的频率不一定相同。此时应该选取数码分布较为均匀的若干位作为散列地址。此法适用于已知关键字集合的情况。若换了关键字,则需重新构造散列函数
    3. 平方取中法:取关键字平方后的中间几位为哈希地址
    4. 折叠法:将关键字分割成位数相同的几部分,然后取这几个部分的叠加和(舍去进位)作为哈希地址。这种方法适用于关键字位数很多、而且关键字中每一位上数字分布大致均匀的情况
    5. 除留余数法:取关键字被某个不大于哈希表长的 p 除后所得余数作为哈希地址
    6. 随机数法

哈希冲突处理方法

  1. 开放定址法 \(H_i=(H(key)+d_i)%m\)
    1. \(d_i=0,1,2,\cdots\)时,称为线性探测法
    2. \(d_i=0^2,1^2,-1^2,2^2,-2^2,\cdots\)时,称为平方探测法
    3. \(d_i=Hash_2(key)\) 时,称为再散列,此时 \(H_i=(H(key)+i\times Hash_2(key )%m\)
    4. \(d_i\) 为伪随机数序列时,称为伪随机序列法
  2. 拉链法
    • 即把冲突的同义词连成一个链表。链表表头构成一个数组

解题技巧小结及结论补充

  • 折半查找在查找不成功给定值进行关键字的比较次数最多这两种情况,都是在求树的高度,即\(\lceil log_2(n+1)\rceil\)
  • 折半查找中平局查找长度的计算(画判定树求解)
    • 查找成功的平均查找长度
      • \(ASL=\frac{\sum每层结点数\times 当前层数(从1取)}{总判定树结点数}​\)
    • 查找失败的平均查找长度
      • \(ASL=\frac{\sum 判定失败的结点数\times 当前层数}{总判定失败结点数}​\)
  • (★★★★★)顺序查找成功的平均查找长度公式
    • \(ASL=\frac{n+1}{2}\) ,其中 n 为元素个数
  • n 个记录的索引顺序表最理想的块长为 \(\sqrt{n}\)
  • 索引顺序表的平均查找长度的计算
    • \(ASL= 块间顺序查找+快内顺序查找\)
    • 根据上述公式,将对应部分的元素个数带入公式即可
  • 如何判定序列满足折半查找或者二叉排序树序列?
    • 注意到两者的序列都可以表示成对一棵树的从根结点沿着某一路径一直访问到叶子结点。
    • 其中,这棵树满足任一节点大于左子树的任意一个结点,小于右子树的任意一个结点。
    • 根据序列第一个元素,确定根结点;根据下一个元素和当前位置的大小关系,确定下一个元素相对于当前元素的位置(左子树还是右子树)。确定位置后,注意检查,是否满足树的要求(即上述第二点的性质)
  • B- 树的正确理解
    • 5 阶 B- 树中各个结点包含的关键字为 2 时,也满足要求(不要误以为要至少存在一个含关键字 4 [ \(5-1\) ] 个的结点才满足)。也就是每个结点的个数在 \(\lceil \frac{m}{2}\rceil -1\le n\le m-1\) 范围内即可(其中,m 为阶数)
  • 在开址法中散列到同一地址二引起的“堆积”问题是由于同义词之间或非同义词之间发生冲突引起的(非同义词!!!)
  • 在开放定址法解决冲突的散列表查找中,发生聚集的原因主要是解决冲突的方法选择不当
  • 在散列表中,平局查找长度装填因子 \(\alpha\) 直接相关,不依赖于已有表项数或表长。若散列表中存放的都是某个地址的同义词,则平均查找长度为 \(O(n)\)
  • 用逐点法插入构造二叉树时,若先后插入的关键字有序,则二叉排序树深度最大

参考资料

  1. 数据结构(C语言版).严蔚敏等
  2. 2020年数据结构考研复习指导.王道论坛