数据结构第七章_search

整理了线性结构、 散列结构hash、平均查找长度、 树形结构等内容，有利于知识点的记忆和理解，考试复习使用，提高学习效率！

第7章 search

• 线性结构
  • 顺序查找 对链表只能顺序查找
    • 实现思路
      • 从头到jiao挨个对比
      • 带💂，从尾部往前扫描，返回0则查找失败
      • 时间复杂度O（n）
    • ASL
      • ASL成功=n+1/2
      • ASL失败=n+1
    • 优点
      • 对数据元素存储没有要求
      • 对表中记录有序性没有要求
    • 缺点
      • n大，平均查找长度大，效率低
  • 折半查找
    • 前提
      • 仅适用于有序的顺序表
    • 特点
      • 构建二叉平衡树 右子树比左子树大1或0
    • ASL
      • 平衡二叉树树高log2（n +1）向上取整 比较次数不会超过树的高度
    • 时间复杂度
      • O（log2n）
    • 缺点
      • 不适合链式存储结构 要求元素关键字有序排列
  • 分块查找
    • 特点
      • 块内无序，块间有序
    • ASL
      • 均匀的分成b块元素，每块s个记录 （b+1）/2+（s+1）2 s=根号n，平均查找长度最小值根号n+1 顺序存储的线性表
• 散列结构 hash
• 树形结构
  • 二叉排序树
    • BST
    • 特点
      • 左小于根小于右
      • 中序遍历是递增的有序序列
    • ASL
      • 成功找自身节点 失败找父节点
    • 查找效率分析
      • 最好o（log2n）
      • 最坏o（n）
  • 平衡二叉树
    • AVL
    • 平衡因子
      • -1，0，1
    • 平衡二叉树最大深度
      • o（log2n）
    • 查找的时间复杂度
      • o（log2n）
  • 红黑树
    • 特点
      • 左根右，根叶黑 不红红，黑路同
  • B树
  • Ｂ＋树
• 平均查找长度
  • ASL