《数据结构》查找

查找基本概念

• 查找
  • 在数据集合中寻找满足某种条件的数据元素的过程
• 查找表
  • 用于查找的数据集合
• 关键字
  • 数据元素中唯一标识该元素的某个数据项的值
• 平均查找长度
  • 所有查找过程中进行关键字比较次数的平均值

查找分类

• 静态查找表
  • 只作查找操作的查找表
    • 顺序查找
    • 二分查找
    • 插值查找
    • 斐波那契查找
    • 线性索引查找
• 动态查找表
  • 表结构本身是在查找过程中动态生成的
  • 查找时插入数据元素
  • 查找时删除数据元素
    • 二分排序树
    • 平衡二叉树
    • B树
    • 散列表

顺序查找

一般线性表的顺序查找

• $ASL_{成功}$ = $\frac{1+2+3+\cdots+n}{n} = \frac{n+1}{2}$
• $ASL_{失败} = n+1$
• 时间复杂度均为O(n)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

typedef Struct{
    ElemType *elem;
    int TableLen;
}SSTable
//
int Search.Seq(SSTable ST,ElemType key){
    ST.elem[0] = key;
    int i;
    for(i =ST.TableLen;ST.elem[i]! = key;--i);
    return i;
}

顺序查找的优化（对有序表）

查找目标 ：21

查找表：

查找判定树

性质：

$ASL_{失败} = \frac{1+2+3+\cdots + n + n}{n+1} = \frac{n}{2} + \frac{n}{n+1}$

成功结点的查找长度 = 自身层数[length(13) = 2]

失败结点的查找长度 = 父节点层数 [length(16) = 3]

折半查找

查找目标

查找：33

顺序表;

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

typedef Struct{
    ElemType *elme;
    int TableLen;
}SSTable;
//
int Binary_Search(SSTable L,ElemType ket){
    int low = 0,haigh = L.TableLen-1,mid = 0;
    while(low<=high){
        mid = (low+high)/2; //取中间位置
        if(L.elem[mid] == key)
            return mid;//查找成功则返回所在位置
        else if(L.elem[mid] > key)
            high = mid -1;//左边查找
        else 
            low = mid + 1;//右边查找
    }
    return -1;//查找失败
}

查找效率分析

$ASL_{成功} = (1 \cdot 1 + 2\cdot 2+3\cdot 4+4\cdot 4)/11 = 3$（有分支结点）

$ASL_{失败} = (4\cdot 3+8\cdot 4)/12 = \frac{11}{3}$（叶子结点）

折半查找判定树

• 折半查找树是平衡二叉树（左右子树高度之差不大于1）
• 折半查找判定树可以用二叉排序树来判别，其中序序列是一个有序序列
• 还有可能要判断取整方向是否一致
• 

常考结论

• 树的高度 h = 向下取整(log2n) + 1 = 向上取整(log2n+1)
• 时间复杂度O(log2 n)
• 查找不成功时比较次数最多即为高度h，注意最后一个数叶要比较
• 折半查找和二叉排序树最好的情况时平均查找长度都是O(log2 n)
• 二叉排序树最坏的情况形成单支树，查找长度为O(n)

分块查找

定义

1
2
3
4
5
6
7

//索引表
typedef Struct{
  ElemType maxValue;
  int low,high;
}Index;
//顺序表存储实际元素
ElemType List[100];

效率分析

设长度为n的查找表被均匀低分为6块，每个块包含s个元素

则：ASL(分块查找的平均查找长度) = $L_1（索引查找的平均查找长度）+L_s（块内查找的平均查找长度）$

顺序查找查找索引表

$L_1 = \frac{(1+2+\cdots)}{b} = \frac{b+1}{2}$

$L_s = \frac{(1+2+\cdots)}{s} = \frac{s+1}{2}$

则ASL=$\frac{b+1}{2} + \frac{s+1}{2} = \frac{s^2+2s+n}{2s}$，当$s = \sqrt{n}时，ALS_{min} = \sqrt{n} + 1$

折半查找查找索引表

$L_1 = [\log_2(b+1)],L_2 = \frac{(1+2+\cdots+s)}{s} = \frac{s+1}{2}$

$ASL = [\log_2(b+1)]+\frac{s+1}{2}$

常考结论

• 顺序查找效率最快时，块数 = $\sqrt{n}$
• 数据分成若干块，每块内数据不必有序，但块间必须有序，但块内最大/最小的数据组成索引块

树型查找

常考结论

• 二叉排序树
  • 当二叉树的叶子节点全部都在相邻的两层时，深度最小。理想情况是从第一层到第二层为满二叉树，$h = 向上取整(\log_2n+1)$
  • 当输入序列是有序序列时，构造的二叉排序树是一支单支树，查找一个关键词最多需要比较n次
  • 按中序遍历二叉排序树得到的序列是一个有序序列
  • 二叉排序树中，关键字值最大的节点右指针一定为空
• 平衡二叉树
  • 平衡二叉树任意节点的做优子树高度差不超过1
  • 平衡二叉树节点递推公式：$n_0=0,n_1=1,n_2=2,n_h=n_{h-2}+n_{h-1}+1\cdots(斐波那契数列，n_1为第一层)$
  • ALV是高度平衡的二叉树，查找效率最高
  • ALV和红黑树查找，删除，插入的平均时间复杂度都相同
• 红黑树
  • 一颗含有n个节点的红黑树的高度至多为$2\log_2(n+1)$
  • 如果一个节点是红色的，则它的父节点和子节点都是黑色的
  • 从一个节点到其子孙节点的所有路径上包含相同数量的黑节点
  • 红黑树是适度平衡的二叉树，查找效率低于平衡二叉树
  • 红黑树可能会出现超出2次旋转的操作
  • 红黑树的任意节点的左右子树高度之差不超过2倍
  • 如果红黑树的所有节点都是黑色的，则它一定是满二叉树

二叉排序树BST

查找

 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

typedef Struct BSTNode{
  int key;
  Struct BSTNode *lchild,*rchild;
}BTNode,*BSTTree;
//在二叉排序树中查找值为key的结点
//最坏空间复杂度O(1)
BSTNode *BST_Search(BSTTree T,int key){
  while(T! = Null&&key! = T->key){
    if(key<T->key) //小于，查询左子树
    {
      T = T->lchild;
    }
    else  //大于，查询右子树
    {
      T = T->rchild;
    }
    return T;
  }
}

//在二叉排序树中查找值为key的结点（递归方式）
//最坏空间复杂度O(h)
BSTNode *BSTSearch(BSTTree T,int key){
  if(T = Null)
    return Null;
  if(key = T->key)
    return T;
  else if (key < T->key)
    return BSTSearch(T->lchild,key);
  else
    return BSTSearch(T->rchild,key);
}

插入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

//在二叉排序树中插入关键字为key的新结点（递归）
int BST_Insert(BSTTree &T,int k){
  if(T==Null){ //原树为空，新插入的结点为根结点
    T = (BSTTree)malloc(sizeof(BSTNode));
    T->key = k;
    T->lchild = T->right = Null;
    return 1;
  }
  else if (k==T->key) //树中存在相同关键字的结点，插入失败
    return 0;
  else if(k< T->key)
    return BST_Insert(T->lchild,k);
  else
    return BST_Insert(T->rhchild,k);
}

构造

按{50,66,60,26,21,30,70,68}建立BST

1
2
3
4
5
6
7
8
9

//按照str[]中的关键字序列建立二叉排序树
void Create_BST(BSTTree &T,int str[],int n){
  T = Null;
  int i = 0;
  while(i<n){
    BST_Insert(T,str[i]);
    i++;
  }
}

删除

查找效率分析

$ASL_{成功} = \frac{(1\times1 + 2\times2 + 3\times4 +4\times1)}{8} = \frac{21}{8}$

$ASL_{失败} = \frac{(3\times7+2\times4)}{9} = \frac{29}{9}$

$ASL_{成功} = \frac{(1\times1 + 2\times2 + 3\times1 +4\times1+5\times1+6\times1+7\times1)}{8} = \frac{30}{8}$

$ASL_{失败} = \frac{(3\times2+1\times3+1\times4+1\times5+1\times6+2\times7)}{9} = \frac{38}{9}$

平衡二叉树ALV

调整最小平衡子树

平衡二叉树生成案例

{15,3,7,10,9,8}生成平衡二叉树的过程

平衡二叉树的查找

$n_h$表示深度为h的平衡树中含有的最少结点树

$n_0 = 0,n_1 = 1,n_2 = 2,n_3 = 4$

即 $n_h = n_{h-1}+n_{h-2}+1$

即含有n个结点的平衡二叉树最大深度为$O(\log_2n)$,平均查找长度为$O(\log_2n)$

平衡二叉树的删除

1. 删除结点（二叉排序树）
2. 向上寻找最小不平衡子树
3. 找最小不平衡子树中高度最大的儿孙
4. 依孙子位置调节平衡(LL/RR/LR/RL)
5. 调整后不平衡向上传导，重复第二步

红黑树

红黑树性质

1. 根结点到叶结点的最长路径不大于最短路径的2倍
2. 有n个内部节点的红黑树高度$h = 2\log_2(n+1)$,查找操作的时间复杂度$ = O(\log_2n)$

口诀：

左根右，根叶黑，不红红，黑路同

红黑树的插入

插入序列{20,10,5,30,40,57,3,2,4,35,25,18,22,23,24,19,18}

B树（B-tree）

• 概念
  • B树是一种自平衡树数据结构，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除
  • B树是二叉搜索树的一般化，因为节点可以有两个以上的子节点
  • B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统，它通常用于数据库和文件系统
• m阶的B树满足的条件
  • 每个节点最多只有m个子节点
  • 每个非叶子节点（除了根）具有至少[m/2]个子树
  • 根节点最多有m颗子树，至少有2个子树
  • 具有k个子节点的非叶节点包含k-1个键
  • 所有叶节点都在同一层次上
• 概念图
  • B树中一个节点的子节点数目的最大值，用m表示，假如最大值为4，则为4阶
  • 

B+树

• 特征
  • 有m个子树的中间节点包含有m个元素（B树为k-1个元素），每个元素不保存数据，只用来索引
  • 所有叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针
  • 叶子结点本身依关键字的大小自小而大的顺序链接
  • 所有的非终端节点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字
• 概念图
  • 
• B树和B+树的对比

散列表

• 概念
  • 散列查找一般适用于关键字集合与地址集合之间存在对应关系的情况下的查找
  • 散列查找的思想是计算出散列地址来查找，然后比较关键字以确定是否比较成功
  • 散列查找的平均查找长度与装填因子有关，与表长无关
  • 装填因子 = $\frac{表中记录数}{散列表长度}$
  • 冲突是不可避免的，与装填因子无关
  • 提高查找效率方法
    • 设计冲突少的散列函数
    • 处理冲突时避免产生堆积现象【装填因子是固有属性，不可变】
    • 产生了堆积即产生了冲突，他对存储效率，散列函数和装填因子没有什么影响，但ASL会随堆积现象而增大
• 两项基本工作
  • 计算位置
    • 构造散列函数确定关键词存储位置
  • 解决冲突
    • 应用某种策略解决多个关键词位置相同的问题
• 计算位置
  • 除留余数法
    • h(key) = key%p
  • 直接定址法
    • h(key) = a$\times$ key + b 【线性函数】
  • 平方取中法
    • key取平方再取中间几位
  • 数字分析法
    • 分析数字关键字在各位上的变化情况
    • 取比较随机的位作为散列地址
    • 如电话号码、身份证号码某几位会比较随机
• 解决冲突
  • 开放地址法
    • 一旦产生了冲突，就按某种规则去寻找另一空地址
    • 发生聚集的原因主要是解决冲突的方法选择不当
    • 线性探测
      • 
      • 
    • 平方探测
      • 
      • 有定理显示，如果散列表长度TableSize是某个4k+3(k是正整数)形式的素数时，平方探测就可以探查到整个散列表空间
  • 链地址法
    • 将相应位置上冲突的所有关键词存储在同一单链表中
    •