数据结构-查找

查找相关概念：

• 查找表：

  • 静态查找表：仅作查询操作
  • 动态查找表：作插入和删除的查找表

• 平均比较次数（ASL）:

  

线性表的查找

顺序查找

• 说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

• 基本思想：从数据结构线形表的一端开始，顺序扫描（习惯从右向左），依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

• 复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
  • 平均查找长度：（1+2+….+n)/n=(n+1)/2

• 改进及优缺点：

  • 改进：设置”哨兵”，在0的位置存放key值，作为哨兵。可以减少每次越界判断。
  • 优缺点：
    • 适用场景多，逻辑次序无要求
    • ASL太长，时间效率低

折半查找

• 说明：元素必须是有序的，如果是无序的则要先进行排序操作。
• 基本思想：用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

​ 可以将查询顺序生产二叉判定树。查询的次数小于等于树的深度：h=log2（n+1）
$$
\lfloor\log_2^{n} \rfloor+1
$$

• 复杂度分析：
  • 时间复杂度：O(lgn)
  • 空间复杂度：O(1)
  • 平均查找长度：log2（n+1）-1

分块查找

• 条件：分块有序，方便建立索引表
• 查询过程：

• 复杂度

  • 时间复杂度：O(m+k),m索引表长，k是块长

  • 空间复杂度：O(m)

  • 平均查找长度：

• 优缺点

  • 插入删除比较容易
  • 增加索引表，并排序，空间和时间测消耗
  • 适用场景：经常动态变化的线性表

数表的查询

二叉排序树

• 左子树所有节点小于根节点，右子树节点大于等于根节点

• 中序遍历结果是递增有序的序列

• 算法描述：

  

• 平均查找长度与树的形态有关

平衡二叉树

• 首先是二叉排序树
• 左右子树高度之差的绝对值不超过1

B Tree和B+Tree

• B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历