《数据结构》第七章-查找

《数据结构》第七章-查找知识梳理，包括查找的基本概念、顺序查找和折半查找、树型查找、散列表、B树和B+树等等。

查找

•  
• 查找的基本概念
  • 1）查找
    • 在数据集合中寻找满足某种条件的数据元素的过程
  • 2）查找表（查找结构）
    • 用于查找的数据集合
      • 静态查找表
        • 只用于查询
      • 动态查找表
        • 支持动态插入和删除
  • 3）关键词
    • 数据元素中唯一标识该元素的某个数据项的值
  • 4）平均查找长度
    • • n：查找表的长度
      • Pi：查找第i个元素的概率（一般是1/n）
      • Ci：找到第i个元素所需进行的比较次数
• 顺序查找和折半查找
  • 顺序查找
    • 一般线性表的顺序查找
      • 查找成功平均长度：（n+1）/ 2
      • 查找失败的平均长度：n+1
    • 有序表的顺序查找
      • 查找成功平均长度：（n+1）/ 2
      • 查找失败的平均长度：n/2+n/(n+1)
  • 折半查找（二分）
    •   PS：注意，折半查找中，mid值是向下还是向下取整，应始终保持一致
    • 基本思想
      • 仅适用于有序的顺序表，将key与中间位置元素比较，再根据大小递归地比较前半部分或后半部分的中间位元素，直到查找成功或失败
    • 实现代码
    • 判定树
      •    ＿
      • 用以描述折半查找的过程
      • • 最大分支高度
        • 由于判定树是平衡二叉树，故分支树高度差最大为1，即最大比较次数-最小比较次数=1
        • 判定树也是一棵二叉排序树（即左子树关键词<根节点<右子树，或相反）
    • 时间复杂度：
  • 分块查找
    • 基本思想
      • 又称索引顺序查找。将查找表分成若干块，前一块的关键字均小于后一块，但块内元素可以无序；建立索引表，每项指示各块的最大关键字和第一个元素的地址，索引表按关键字有序排列
      • 查找时，先再索引表中确定待查记录所在的块（采用顺序或折半查找索引表）；再在块内顺序查找
    • 平均查找长度=索引查找+块内查找
      • 均采用顺序查找
        • • 将长度位n的查找表均分为b块，每块有s个记录
      • 索引表采用折半查找，块内顺序查找
• 树型查找
  • 二叉排序树（BST）
    • 定义
      • 二叉排序树（也称二叉查找树），或者是一棵空树，或者是具有下列特性的二叉树:
      • 1）若左子树非空，则左子树上所有结点的值均小于根结点的值。
      • 2）若右子树非空，则右子树上所有结点的值均大于根结点的值。
      • 3）左、右子树也分别是一棵二叉排序树。
      • 对二叉排序树进行中序遍历，得到一个递增的有序序列
    • 查找
    • 插入
      • 1）若关键字k小于根节点值，则插入到左子树；否则插入到右子树
      • 2）插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子
      • 3）在二叉排序中删除并再插入一个相同结点，若该结点原来是叶结点，则前后二叉树不变，反之则必然变化；对于平衡二叉树，无论删除的原结点是否是叶结点，前后的AVL都可能发生变化（or不发生）
    • 构造
      • 构造过程
      • 算法
    • 删除
      • ①若被删结点是叶结点，则直接删除即可
      • ②若被删结点z只有一棵左子树或右子树，则让其子树成为z父结点的子树
      • ③若z有左、右两棵子树，则让其直接后继（按中序序列计算）或直接前驱代替z，然后删除该后继结点，从而转换为前面的情况
    • 效率分析
      • 1）左右子树高度差不超过1，即平衡二叉树
        • 平均查找长度：
      • 2）只有右（左）孩子的单支树
        • 平均查找长度：
    • 和二分查找的对比
      • 1）二叉排序树的查找性能与数据的输入顺序有关，仅在最好情况下的查找性能与折半查找相同
      • 2）就维护表的有序性而言，二叉树无需移动结点，只需修改指针即可完成插入删除操作，时间复杂度为O(log2n)，而二分查找则需O(n)；当有序表是静态查找表时，宜用顺序表和二分查找，当其为动态时，宜用二叉排序树作为逻辑结构
  • 平衡二叉树
    • 定义
      • 定义结点左、右子树的高度差为平衡因子（左高-右高），则平衡二叉树结点的平衡因子只能是0、1、-1，即任意结点左右子树的高度差不超过1
    • 插入
      • 1）类似二叉排序树插入结点
      • 2）一旦插入的结点破坏了平衡，则找到最小的不平衡子树，进行旋转
        •  调整方法（非常重要！！！）： 找到最小的不平衡子树，从子树的根结点开始，顺着不平衡的方向遍历三个结点，将其中权重居中的结点置为子树的根结点，左右按序放置另两个结点
        • ①LL平衡旋转（右单旋转）
          • 在结点A的左孩子的左子树上插入新结点；需向右旋转，将A的左孩子B向上旋转成为根节点，A作为B的右子树的根节点，B的原右子树作为A的左子树
        • ②RR平衡旋转（左单旋转）
          • 在结点A的右孩子的右子树上插入新结点；需向左旋转，将A的右孩子B向坐上旋转成为根结点，A成为B的左子树的根结点，B的原左子树作为A的右子树
        • ③LR平衡旋转（先左后右双旋转）
          • 在A的左孩子的右子树上插入新结点，需先将A结点的左孩子B的右子树的根结点C向左上旋转到B的位置，再把C向右上旋转到A的位置
        • ④RL平衡旋转（先后左双旋转）
    • 删除
      • 1）用二叉排序树的方法对结点w执行删除操作。
      • 2）从结点w开始，向上回溯，找到第一个不平衡的结点z(即最小不平衡子树)；y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。
      • 3）然后对以z为根的子树进行平衡调整，其中x、y和z可能的位置有4种情况：
        • ① y是z的左孩子，x是y的左孩子(LL，右单旋转)；
        • ②y是z的左孩子，x是y的右孩子(LR，先左后右双旋转)；
        • ③y是z的右孩子，x是y的右孩子(RR，左单旋转)；
        • ④y是z的右孩子，x是y的左孩子(RL，先右后左双旋转)
        • og
    • 查找
      • 查找过程与二叉排序树相同，平均查找长度为O(log2n)
    • 结点数
      • • nh即高度为h的平衡二叉树最少的结点数
  • 红黑树
    • 定义
      • 一棵红黑树是满足如下红黑性质的二叉排序树：
      • ①每个结点或是红色，或是黑色的。
      • ②根结点是黑色的。
      • ③叶结点（虚构的外部结点、NULL结点）都是黑色的。
      • ④不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
      • ⑤对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。
        • 从某结点（不包括该结点）到达一个叶结点的任意简单路径上黑结点总数称为该结点的黑高（记为bh），根结点的黑高即为红黑树的黑高
    • 性质
      • 
      • 1. 从根结点到叶结点的最长路径不大于最短路径的两倍
      • 2. 有n个内部结点的红黑树高度
    • 插入
      • 
      • 用二叉查找树插入法插入，并将新结点z着为红色
        • 若z为根结点，将其着为黑色，结束
        • 若z不是根结点
          • 若z的父结点是黑色的，无需调整
          • 若z的父结点是红色的
            • ①z的叔结点y是黑色的，且z是一个右孩子
              • LR（若z.p为右孩子，则是RL），左旋一次，变为②
            • ②z的叔结点y是黑色的，且z是一个左孩子
              • LL（若z.p为右孩子，则是RR），右旋一次，并交换z.p和z.p.p和颜色
            • ③若x的叔结点y是红色的
              • 将z.p和y都着为黑色，z.p.p着为红色，再将z.p.p作为新结点z来重复循环，直到满足①、②或z为根结点为止
    • 删除
      •  
      • 1）删除过程先执行二叉查找树的删除方法，若待删结点有两个孩子，则将其与中序后继结点交换（即右子树中最小的结点），然后转换为删除该后继结点；后继结点最多仅一个孩子，故转换为待删结点无孩子或仅有一孩子的情况
      • 2）若待删结点只有右孩子或左孩子，由性质可知，其本身必为黑结点，孩子必为红结点
      • 3）若待删结点没有孩子
        • ①若结点为红色，则直接删除
        • ②若待删没有孩子，且为红色，记x是用来替代y的结点（x是黑色的null结点），为使黑高不变，将x定位为双黑结点，需将其恢复为普通结点
          • 1. x的兄弟结点w是红色的
            • 此时w必有黑色的左右孩子和父结点；交换w和x.p的颜色，然后左旋x.p，将情况1转换为2、3、4
          • 2. x的兄弟结点w是黑色的，w的左孩子是红色的，右孩子是黑色的
            • RL，即红结点是其爷结点的右孩子的左孩子。交换w和其左孩子的颜色，右旋w，转换为情况3
          • 3. x的兄弟结点w是黑色的，且w的右孩子是红色的
            • RR。交换w和x.p的颜色，将w的右孩子着为黑色，并对x.p左旋，将x变回单重黑色，结束
          • 4. x的兄弟结点w是黑色的，且w的两个孩子结点都是黑色的
            • 从x和w上都去掉一层黑色（即w变为红色），作为补偿，将x.p额外着一重黑色，以保持局部黑高
              • 若x.p原本为红色，将其变为黑色，结束
              • 若x.p原本为黑色，则将其作为新结点x进入循环
• 散列表
  • 基本概念
    • 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以是数组下标、索引或内存地址等）。
      • 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。
    • 散列表：根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
  • 散列函数的构造方法
    • 要求
      • 1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
      • 2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
      • 3）散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。
    • 常用的散列函数
      • 直接定址法
        • 基本思想
          • 直接取关键字的某个线性函数值为散列地址
        • 散列函数
          • H(key)=key或H(key)=a×key+b
        • 特点
          • 简单且不会产生冲突，适合关键字连续分布的情况，否则会浪费存储空间
      • 除留余数法
        • 基本思想
          • 记散列表表长为m，取一个小于且最接近或等于m的质数p，借助公式将关键字转换为散列地址
        • 散列函数
          • H(key)=key%p
        • 特点
          • 最常用且简单的方法
      • 数字分析法
        • 基本思想
          • 对于r进制数的r个数码，选取数码分布较为均匀的若干位作为散列地址
        • 特点
          • 适合已知的关键字集合，若更换了关键字，需重新构造新的散列函数
      • 平方取中法
        • 基本思想
          • 取关键字的平方值的中间几位作为散列地址
        • 特点
          • 只用于关键字的每位取值都不够均匀或均小于散列地址所需的位数
  • 处理冲突的方法
    • 开放定址法
      • 
      • 定义
        • 可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放
        • 递推公式
          • • Hi表示处理冲突中第i次探测得到的散列地址，m表示散列表表长，di为增量序列
      • 增量序列
        • 线性探测法
          • 基本思想
            • di=0, 1,……，m-1，即冲突发生时，顺序查看表中的下一个单元，直到找到一个空闲单元或查遍全表
          • 特点
            • 容易造成大量的元素在相邻的散列地址上“聚集”起来，大大降低了查找效率
            • 采用线性探测法时，即使不是同义词，也可能发生冲突
        • 平方探测法
          • 基本思想
            • di=0^2, 1^2, -1^2……,k^2,-k^2，其中k≤m/2，散列表长度m必须是一个可表示为4K+3的素数，又称二次探测法
          • 特点
            • 可避免“堆积”问题，但不能探测散列表上的所有单元（但至少能探测到一半单元）
        • 双散列法
          • 基本思想
            • di=Hash2(key)，即使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量
            • 散列函数
        • 伪随机序列法
          • di=伪随机数序列
    • 拉链法（链接法，chaining）
      • 将所有的同义词存储在一个线性链表中，该链表由其散列地址唯一标识；适用于经常进行插入和删除的情况
  • 散列查找及性能分析
    •  
    • 查找过程
      • ①检测查找表中地址为Addr的位置上是否有记录，若无记录，返回查找失败；若有记录,比较它与key的值，若相等，则返回查找成功标志，否则执行步骤②。
      • ②用给定的处理冲突方法计算“下一个散列地址"，并把Addr置为此地址，转入步骤①。
      • • • 平均查找长度ASL=2.5
    • 分类
      • 查找成功
        • 根据每个已知元素的查找长度
          • 查找成功的比较次数=冲突次数+1
      • 查找失败
        • 根据散列函数所确定的每个查找位置的查找长度
    • 查找效率的影响因素
      • 散列函数
      • 处理冲突的方法
      • 装填因子α=表中记录数n/散列表长度m
• B树和B+树
  • B树及其基本操作
    • 定义
      • B树，又称多路平衡查找树，其所有结点的孩子个数的最大值称为B树的阶，记为m，一棵m阶B树或为空树，或为满足如下性质的m叉树：
      • 1）树中每个结点至多有m棵子树，即至多含有m- 1个关键字
      • 2）若根结点不是终端结点，则至少有两棵子树
      • 3）除根结点外的所有非叶结点至少有「m/2]棵子树，即至少含有「m/2]-1个关键字。
      • 4）所有非叶结点的结构如下:
        • • Ki为结点的关键字，按升序排序
          • Pi为指向子树根结点的指针，Pi-1所指子树中所有结点的关键字均小于Ki
          • n为关键字的个数
      • 5）所有叶结点都出现在同一层次上，且不带信息（即外部结点，指向这些结点的指针都为空）
    • 性质（假定m=5）
      • 1）结点的孩子个数等于该结点中关键字个数加1。
      • 2）如果根结点没有关键字就没有子树，此时B树为空；如果根结点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加1。
      • 3）除根结点外的所有非终端结点至少有「m/2]-1=3棵子树，至多有5棵子树（即至多有4个关键字)。
      • 4）结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。
      • 5）所有叶结点均在第4层，代表查找失败的位置
    • B树的高度（磁盘存取次数）
      • 1）B树的每个结点最多有m棵子树，m-1个关键字，故一棵高度为h的m阶B树中关键字的个数应满足n≤(m-1)(1+m+m^2+……+m^(h-1))=m^h-1
      • 2）根结点至少有2棵子树，非根结点至少有「m/2]-1个关键字，第h+1层至少有2(「m/2])^(h-1)个结点，而叶结点个数为n+1
    • B树的查找
      • ①在B树中找结点
        • 在磁盘中进行，根据关键字比较找到对应结点
        • 若查找到叶结点（对应指针为空指针），说明树中没有对应的关键字，查找失败
      • ②在结点中找关键字
        • 在内存中进行，在结点内部采用顺序或折半查找法
    • B树的插入
      •  
      • 1）若插入后的结点关键字个数小于m，可以直接插入
      • 2）否则，取中间位置（「m/2]）的结点插入原结点的父结点，原结点分裂为两块；若进而导致了父结点的关键字个数溢出，则继续分裂，直至传到根结点为止，进而导致B树高度加1
    • B树的删除
      • 1）若被删关键字k不在终端结点（最低层非叶结点）中时，用k的前驱（或后继）k'来替代k，然后再相应结点中删除k'（k'必然落在某个终端结点中）
      • 2）若被删关键字k在终端结点中时
        • ①直接删除关键字。条件是该结点的关键字个数≥「m/2]，删除该关键字后仍满足B树的定义
        • ②兄弟够借。若该结点的关键字个数=「m/2]-1，且兄弟结点的关键字个数≥「m/2]，则调整该结点、右（左）兄弟结点及其双亲结点（父子换位法），以达新的平衡
          •  
        • ③兄弟不够借。若该结点及其左右兄弟结点的关键字个数均为「m/2]-1，则将关键字删除后与左（右）兄弟结点及双亲结点中的关键字进行合并
          • 
  • B+树的基本概念
    • B+树是B树的变形树，满足如下条件：
      • 1）每个分支结点最多有m棵子树（孩子结点)。
      • 2）非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。
      • 3）结点的子树个数与关键字个数相等。
      • 4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
      • 5）所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。
    • B+树与B树的差异：
      • 1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
      • 2）在B+树中，每个结点（非根内部结点）的关键字个数n的范围是「m/2]<n<m(根结点：2<n<m)；在B树中，每个结点（非根内部结点）的关键字个数n的范围是「m/2]-1<n<m-1（根结点：1≤n≤m- 1)。
      • 3）在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
      • 4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是不重复的。
    • 查找
      • ①B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点；因此可以对B+树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找
      • ②在B+树中查找时，无论是否成功，每次查找都是一条从根结点到叶结点的路径