查找

408数据结构查找总结，全网知识点最全，知识体系最连贯，做题情况最全面的思维导图，能大大提高你的复习学习效率

查找

• 基本概念
  • 查找
    • 动态查找表
    • 动态查找表
  • 关键字
    • 唯一标志数据元素的关键项
      • 关键字可以唯一地标志一个记录，则称此关键字为主关键字 不同的记录，主关键字不相同，关键字所在的数据项称为主关键码。
  • 查找算法的效率评价
    • 查找成功的ASL
    • 查找失败的ASL
• 静态查找
  • 顺序查找
    • 算法思想
      • 从表中一端开始往另一端查，值相等，查找成功
    • 算法实现
      • 基本算法
        • int sequential search(int a[ ],int n, int key) { int i; for(i=1;i<=n;i++) {if(a[i]==key) return i; } return 0; }
        • 局限，每一次查找结束都要判断i是否越界。
      • 哨兵顺序法
        • int sequcesearch(int a[ ] ,int key,int n) { int i; a[0]=key; i=n; while(a[i]!=key) i--; return i; //返回0则说明查找失败 }
        • 改善了查找过程中每一次比较厚都要判断是否越界，总数据多的时候提高效率
    • 时间复杂度O(n)
    • ASL
      • 查找成功
        • 成功asl
          • 
      • 查找失败
        • n+1
    • 优化：有序表的顺序查找
      • 元素查找概率相同，改善查找失败的ASL
        • 
        • 为什么分母变成n+1
          • n个元素有n个查找不成功的情况
        • 为什么还要加个n
          • 最后一层情况有两种情况
      • 元素查找概率不相同，改善查找成功的ASL
        • 查找失败，就无优化效果
        • ASL=p*层数
  • 折半查找
    • 前提：线性表元素有序！
    • 实现代码
      • int brinary search( int a[ ],int n,int key)//a[ ]的元素从a[1]开始存储 {int mid,low,high; low=1; high=n; while(low<=high) // { mid=(low+high)/2; //这里mid是向下取整 if(a[mid]>key) low=mid+1; else if(a[mid]<key) high=mid-1; else return mid; //可以在这里加一个计数器，看查找了几次 }//while return 0;//查找失败 }
    • 时间复杂度
      • n对2取对数，向下取整。然后这个整体+1
      • logn
        • 并不意味着折半查找在任何时候都比顺序查找快，考虑查找的元素就是第一个元素
          • 2016年真题考的就是什么情况下顺序查找比折半查找更快
    • 画折半查找子树
      • 很容易误解这是一颗排序二叉树 但折半查找的判定树是一棵平衡二叉树。 由折半查找的定义，每次把一个数组从中间结点分割时，总是把数组分为结点数相差不超过1的两个子数组，从而使判定树的两棵子树的高度差绝对值不超过1，对应平衡二叉树
      • 通过根节点看向下取整还是向上取整
        • 向上取整
          • 
          • 左边结点比右边多
        • 向下取整
          • 
          • 右边结点比左边多
      • 判断符不符合向上取整和向下取整的统一性
        • 向上取整，即让较大的数优先被查到，或者说处于树的更高层，地位更高 向下取整，让较小的数优先被查到，处于树的更高层
        • 左右结点一样多的时候，有分叉直接排除
          • 不合理情况
            • 1
              • 
            • 2
              • 
            • 3
              • 
          • 合理情况
            • 1统一向上取整
              • 
            • 2向下取整
              • 
        • 左右结点不一样多，则整个树取整方式要统一
          • 合理情况
            • 
            • 左边节点多，向上取整
            • 整棵树都是向上取整的形状
          • 不合理情况
            • 
            • 右边结点多，向下取整
            • 整棵树却是向下取整的形状
      • 迭代就是AVL的插入
    • ASL
      • 必须画出判定树才能求解
    • 局限
      • 顺序存储作用，链式存储不作用
      • 静态的已排好的有序表比较适合，但是动态的维持有序的成本有点高
    • 补充
      • 插值查找
        • 插值公式
          • 不适用于数据分布不均匀的数组
      • 斐波那契数列查找
  • 分块查找
    • 分块
      • 数据集分成若干块
        • 块内无序
        • 块间有序
      • 每块有一个索引
        • 最大关键码
        • 块中记录的个数
        • 用于指向首快数据元素的指针
    • 查找
      • 1先找关键字所在的块
        • 很容易通过折半查找
      • 2.再找块间元素
        • 顺序查找
    • 查找长度
      • 分为索引查找和块内查找的平均查找长度之和
      • • 
    • 链式存储
      • 
      • 方便删除和插入
      • 无法进行折半查找
• 动态查找表
  • 二叉排序树
    • 定义
      • 左子树值<根节点<右子树结点值
      • 中序遍历可以得到一个递增的序列
      • 左右子树也是一个二叉排序树
    • 查找
      • BstNode *BST-search(BiTree T,ElemType key) { while(T!=Null&&key!=T->data) { if(key>T->data) T=T->rchild; else T=T->Lchild;} return T; }
      • 查找序列
        • 
        • 只用标出拐点的数值，且是从右向左的拐点的值，然后从上到下比较，满足大到小即可
      • 查找某个数，查找次数等于这个结点所在的深度
    • 插入
      • 插入的结点只能是叶子结点
        • 是查找失败时访问的最后一个结点的左（右）孩子
      • 插入顺序不同，得到不同的二叉树
        • 什么时候相同
          • 第二层相同
    • 删除
      • 不能全部直接删除，先把被删除结点从存储二叉排序树的链表中摘下，将因删除结点而断开的二叉链表重新连接，同时保证二叉树的性质
      • 一般做法：还原中序序列，找到被删除的结点前后两个结点，连接起来并且还原回排序二叉树
      • 可以利用BST性质简化的情况
        • 被删除的结点是叶子结点
          • 直接删除
        • 被删除的结点只有右子树
          • 用右子树补
        • 被删除的结点只有左子树
          • 用左子树补
      • 删除后某结点后又插入，序列不变，但是树的结构发生变化，不再是原来的树
        • 中序序列对应的树不唯一
    • 查找效率分析
      • 比平衡二叉树慢
        • 与二分查找的比较
          • 二分查找对应的判断树是平衡二叉树，一般比排序树查找效率高
          • 二分查找对应的顺序存储结构，而平衡二叉树增删比二分查找效率高
      • 比单支树快
  • 平衡二叉树
    • 与二叉排序树的关系
      • 是一种特殊的二叉排序树
        • 左右子树高度差不超过1
      • 优化，限制排序树高度增长过快
    • 定义
      • 排序树基本且满足左右高度差不超过1
      • 一定是折半查找的判定树
    • 平衡树的插入
      • 插入思想，每插入一个结点都要考虑这个操作是否导致不平衡
      • 不平衡，则调整结点所在的最小不平衡子树
        • 调整的对象是不包括插入结点在内的最小不平衡子树
        • 沿着插入路径找到中间大的数作为新的根节点，调整树
        • 调整完树以后再插入新值
        • 可能会有断链和新的连接关系
      • 调整的本质
        • 调整只是让插入后的树满足中序遍历后递增
    • 平衡二叉树的删除
      • 与调整的本质类似
    • 查找
      • 公式Nh=Nh-1+Nh-2+1
        • 
        • 这是深度为h的AVL树含有的最少结点数
      • 查找过程中，与key的比较次数不超过树的深度
        • 应用
        • 解决给定结点数的平衡二叉树的查找所需的最多比较次数Nh
        • 基本算数题
          • 含有20个结点的AVL至少有（）个结点
          • 具有5层结点的AVL至少有（）个结点
    • 平衡二叉树的构建
      • 要拒绝一个一个插入然后调整，直接通过中序遍历从上往下构造树（选填）
        • 
      • 大题要求依次构建只能迭代
  • B/B+树
    • B树
      • m阶b树
        • b树中所有结点孩子个数最大的那个值称为b树的阶
        • 阶是被子树的个数，例如5阶b树一定是区域被四个点化成了五个区域
      • B树的性质
        • 1.结点的孩子个数等于关键字个数+1
          • 和B树是几阶的无关
          • 结点的孩子是被划分的区间
          • 关键字是点坐标
        • 2.根结点
          • 至少两棵子树，如果有关键字
        • 3.分支节点
          • 子树数目
            • 最少：m/2向上取整
            • 最多：m
          • 关键字个数
            • 最少：m/2向上取整-1
            • 最多：m-1
        • 4.所有叶结点都在一层，表示查找失败，不算入树的高度
        • 5.B树的高度
          • 查找效率与B树的高度密切相关 b树中的大部分操作所需的磁盘存储次数与b树的高度成正比
          • 需要明确地信息，关键字的个数n，b树的阶数m，和所求的高度h
          • 最小高度
            • 类似于满二叉树
          • 最大高度
            • 第一层一个关键字
            • 第二层m/2课子树
            • 第三层2*（m/2）课子树
      • B树的查找
        • 在B树中查找结点
          • 在磁盘中进行
        • 在结点中查找关键字
          • 在内存中进行
            • 找到目标结点后，将结点信息读入内存，再在内存中才有顺序查找法和折半查找
      • B树的插入|构建
        • 
        • 1.新关键字插入的结点都是最后一层
        • 2.当结点中关键字数小于m-1时，直接插入该结点
        • 3，需要向上溢出，必然导致局部的分裂
          • 因为上层的关键字增多，子树增多
        • 若3,中父节点也超出上限，则对父节点进行分裂操作，传递到根节点，
          • 在根节点发生分裂的情况下，树高+1
      • B树的删除
        • 1. 删除的本质
          • 关键字的删除导致的是权利的下降，变局过大时，会有权利的上升
        • 2. 删除能简化
          • 删除的节点是叶子结点
            • 叶子结点中关键字数量大于1
              • 直接删
            • 叶子结点只有一个关键字
              • 双亲结点和左右兄弟结点中关键字都大于1
                • 从中借
              • 删完后不能借
                • 只能让父节点关建字-1，让最小或者最大那个下降合并
              • ！！！删完之后导致不平衡
                • 
                • 整颗b树整体结构都要改变
                  • 1.将中序遍历写出来
                  • 2.可以直接划掉底层的结构，因为删除不可能导致叶子结点上移
                  • 4.选择对整体改变小的关键字作为根节点
          • 删除的结点是中间结点
            • 找中序前驱（后驱）
              • 替换被删除的点
          • 删除的结点时跟结点
            • 1.将中序遍历写出来
            • 2.可以直接划掉底层的结构，确定根节点
            • 3，左右子树分别找可能的根节点，划分范围
              • 212,112，211,
              • 23,24
      • B树的局限和与B+树的发展
        • B树不方便遍历，需要频繁切换上下级，而切换上下级的实质是切换硬盘的页面和将读取，开销很大
        • B+树应该能满足方便地遍历B树中的元素，适合带有范围的查找
    • B+树
      • +的是多层索引和head指针遍历叶子结点
      • 1.关键字和孩子是一一对应的关系
        • 孩子通常是活动记录
        • n颗子树有n个关键字
      • 2.叶子结点有全部关键字的信息，并且在最后一层有序排列
        • 还包括指向记录活动的指针，相邻叶结点还有指针链接起来
      • 3.分支结点仅起索引作用，每个索引项只含有指向对应子树的指针和此子树的最大关键字，但不包含关键字指向的活动记录地址
      • 会导致B+树中有重复的关键字
• 散列表（哈希表）
  • 避免了动态查找表和静态查找表相当多的比较 但不是完全避免
  • 概念
    • 散列函数
      • 散列表地址和关键字值key的映射
    • 冲突
      • 不同的关键字经过一个散列函数映射到同一个地址，会发生地址冲突
        • 散列函数应该减少冲突
        • 设计好处理冲突的办法
    • 同义词
      • 发生冲突的不同关键字
  • 散列函数
    • 指定原则
    • 类别
      • 直接定址法
        • 取关键字的某个线性地址值为散列地址
        • 不会产生冲突
          • 适合关键字的分布基本连续的情况
          • 分布不连续会导致空位较多，空间浪费
      • 除留余数法
        • H(key)=key%p
          • p应该为最接近散列表表长m的一个质数
            • 会形成环
      • 数字分析法
      • 平方去中法
  • 处理冲突的方法
    • 任何散列函数都不能绝对地避免冲突
    • 开放定址法
      • 指可存放新表项的空闲地址既可以向它的同义词表项开放，也可以向非同义词表项开放 Hi=（H（key)+di)%m
      • di是递增序列，di的不同导致了处理方法的不同
        • 线性探测法
          • di取0,1,2,...,k
          • 会导致聚集（堆积）问题
            • 多个不同哈希函数值的记录争抢同一地址
          • 探测表尾元素的时候下一个探测地址是表头首地址0，直到找到空位查找失败
          • 查找到空闲地址或者查遍全表回到原处，查找失败
        • 平方探测法
          • di=k的平方
          • 散列表长度必须是4k+3的素数
          • 可以避免“堆积问题”
          • 不能探索所有单元
            • 至少一半单元
        • 双散列法
          • di=hash2（key）
        • 伪随机序列法
      • 不能随便物理删除表中元素，会阻断其他具有相同的散列地址的元素的查找
        • 逻辑删除，但是副作用明显
          • 散列表看起来很满，但是很多地方未利用
    • 拉链法
      • 为了避免非同义词发生冲突
      • 适用于经常发生删除和插入的情况
  • 散列表的查找
    • 查找失败
      • 理解
        • 查找失败时针对mod n而言的，所以查找失败的ASL分母一定是n，他说的是0-n-1的每一个位置都可以遇到查找失败的情况，所以上面就是每一个位置到最近空位（查找失败）的距离之和
      • 情况
        • 1
          • [0,n-1]内有空格
            • 表内循环找即可
        • 2
          • [0，n-1]无空格
            • 此时散列表长度m必然大于n，找离n最近的空格即可
        • 3
          • [0，n-1]之外有值
            • 不参与查找的计算，只对空格位置有影响
    • 查找成功
      • 理解
        • 查找成功是针对散列表中已经有的关键字而言的，它的ASL分子是每个关键字的查找次数之和，分母是散列表中已经有的关键字的个数；
    • 查找效率
      • 散列函数，处理冲突的方法和装填因子
        • 装填因子
          • 衡量表的装满程度， 越满，越容易发生冲突 越近，越