首页 > 其他分享 >数据结构基础第7讲

数据结构基础第7讲

时间:2024-07-27 14:31:18浏览次数:17  
标签:10 结点 删除 基础 二叉 插入 查找 数据结构

数据结构基础第7讲 查找

img

考点一:查找的基本概念

1.概念

  1. 静态查找

    img

  2. 动态查找

    img

  3. 分类

    img

2.查找性能计算

  1. 平均查找长度:

    img

考点二:顺序查找

1.顺序查找

img

2.优劣

img

考点三:折半查找(二分搜索)

1.概念

img

2.过程

img

img

img

3.构建为判定树

  1. 构建
    img

    img

    向上取整:左少右多向右偏

    向下取整:左多右少向做左偏

    img

  2. 结论

    查找比较次数=层次高度

    查找路径是一条从根到该点的参次路径,该路径有且仅有一条

    img

  3. 查找成功平均比较次数

    查找成功平均比较次数:拿层高乘以每层结点个数累加再除以元素个数

    img

  4. 查找不成功平均比较次数

    img

顺序查找及折半查找均为静态查找手段

考点四:二叉排序树

1.二叉排序树定义

注意:二叉排序树中没有相同关键字的结点

img

2.二叉排序树的查找

查找过程:

查找过程永远是一条层次路径的形态
img

3.二叉排序树的插入

插入过程:

img

img

4.二叉排序树的删除

img

4种情形:

img

  1. 删除叶子

    img

  2. 删除结点只有右子树

    img

  3. 被删除的结点只有左子树

    img

    img

  4. 被删除同时具有左右子树

    用中序直接前驱或中序直接后继代替

    img

    img

  5. 二叉排序树的构造

    img

    依次作为叶子结点插入

    元素相同顺序不同,构成的二叉排序树也不同

    img

    img

6.二叉排序树的性能分析

相同结点,树形结构不同,也会导致平均比较次数不同

img

img

img

img

考点五:平衡二叉树

1.平衡二叉树概念

  1. AVL树引入

    img

  2. 平衡因子

    img

  3. 最小不平衡子树

    以距离插入结点最近的,且失衡的结点为根的子树

    img

2.平衡二叉树的旋转及实现

  1. 导致不平衡原因

    插入与删除可能导致失衡

    1. 插入结点:

      插入只会改变它所在层次路径的平衡因子

      img

    2. 删除结点:

      删除可能会改变父亲所在层次路径的平衡因子

      img

    插入看自己,删除看兄弟(父亲)

    删除改变的一定是兄弟子树因此从兄弟往上找

  2. 不平衡的4种情况

    img

  3. 不平衡情况判断

    插入:

    从自己开始向上查找,找到不平衡那个点,以那个点的层次路径即为最小不平衡子树

    img

    删除:

    从兄弟向上去找,找到第一个不平衡点;

    从该点开始画层次路径,层次路径可能有多个;

    当层次路径高相同时都可以,不同时谁高看谁

    img

  4. 如何调整

    全把落单的当叶子结点重新插进去

    以最小不平衡子树根节点开始,向下子节点位置命名

    1. LL

      落单的拿出来,剩下的按平衡二叉树规则变形。

      重新把R当叶子结点插入回去

      R比10大比11小,插入11左边

      img

    2. LR

      先把10放到中间构成LL

      接着掰弯

      img

      当有左右子树时

      把L,R落单,剩余按平衡二叉树规则处理。

      再把L,R当作叶子结点插回去

      L比9大比10小,插入到9左边

      R比10大比11小,插入到11右边

      img

    3. RR

      img

      10有左子树

      L比10小,比9大,插入到9左边

      img

    4. RL

      img

      有L,R情况

      L比9大,比10小,放9左边

      R比10大,比11小,放11右边

      img

考点七:索引查找

1.B-树的定义和性质

用关键字分割子树

  1. 索引查找引入
    img

  2. B树的定义
    img
    img
    img
    img
    img
    img

性质总结:

img

2.B-树的查找

  1. 查找过程

    img

    img
    img

  2. B-插入

    img

  3. B-删除

    m为B树阶数

    img

    1. 删除非叶子中的key
      img

      任意非叶子都有左子树

      用中序直接前驱或中序直接后继代替之。

      即用左子树最大值或右子树最小值代替。

      删除看下界

      img

      不够找兄弟借,借左兄弟最大值,或右兄弟最小值,把父亲拽下来把兄弟升上去。

      img

      都不够
      将自己父亲左兄弟合并,或自己有兄弟合并

      img

      img

    总结:

    img

    ex:

    img

    img

3.B+树的定义与性质

用关键字引导子树

img

考点八:散列查找

1.散列查找的基本思想

img

img

  1. 设计散列函数

    img

    1. 直接地址法
      img

    2. 平方取中法

      img

    3. (\(\bigstar\))除留余数法

      img

2.处理哈希冲突

  1. 开放定址法

    凡是空白空间均可使用。

    线性探查法:

    计算成功/失败的平均查找次数

    img

    失败标志,从算出哈希位置向后找到空

    img

  2. 二次探查法

    左右横跳,越跳越长

    img

  3. 拉链法

    将余数相同的所有元素放入单链表中

    img

    成功查找平均次数:

    img

    失败查找平均次数:

    img

  4. 装填因子

    img

  5. 复杂度

    img

标签:10,结点,删除,基础,二叉,插入,查找,数据结构
From: https://www.cnblogs.com/JUANFENHUI/p/18326908

相关文章

  • 计算机组成原理基础第1讲
    计算机组成原理基础第1讲计算机系统概述考纲要求考点一:预备知识1.计算机的组成由硬件系统和软件系统两部分组成2.系统软件\[系统软件\left\{\begin{align}操作系统\\实用程序\\编译程序\end{align}\right.\]操作系统语言处理程序3.计算机如何工作4.......
  • 数据结构基础第8讲
    数据结构基础第8讲排序考点一:排序的概念和性能分析1.排序的概念稳定性根据相对位置是否改变判断内排序2.排序的性能考点二:插入类排序1.直接插入排序\(复杂度O(n^2)\)3.折半插入排序改进了比较次数未改变移动次数,因此复杂度仍为\(O(n^2)\)3.希尔排序时......
  • 计算机组成原理基础第2讲
    计算机组成原理基础第2讲数值系统考纲:考点一:进制系统考点二:定点数表示核运算1.定点数的表示和范围定义有符号机器数2.定点机器数移位运算算数移位逻辑移位3.溢出问题左溢出变形补码的移位问题溢出概念和判别法4.定点机......
  • 计算机组成原理基础第6讲 系统总线
    计算机组成原理基础第6讲系统总线考点一:总线概述1.基本概念2.总线的分类3,总线特性4.性能指标考点二:总线控制......
  • 计算机组成原理基础第5讲 CPU系统
    计算机组成原理基础第5讲CPU系统考点一:CPU的功能和组成1.CPU的功能2.CPU的组成与结构系统总线CPU的内部结构3.CPU中的数据通路4.CPU中的寄存器用户可见控制和状态寄存器PC程序计数器用于存放下一条执行指令的地址IR指令寄存器用......
  • 计算机组成原理基础第4讲 指令系统
    计算机组成原理基础第4讲指令系统考点一:机器指令1.一般格式地址码考点二:指令设计指令字长操作数类型和操作种类3.操作类型数据传送算术逻辑操作移位操作转移输入输出考点三:寻址方式1.寻址方式概述2.数据寻址一.指令寻......
  • 计算机组成原理基础第3讲
    计算机组成原理基础第3讲主存储器考纲考点一:存储器的概念1.存储器的系统结构两级存储结构缓存——主存层次和主存——辅存层次2.存储器的分类按计算机系统中的作用分类按信息的存取方式分类,存储器课分为RAM,ROM,SAM和DAM按存储介质分类按信息的可用......
  • 计算机组成原理基础第7讲 输入输出系统
    计算机组成原理基础第7讲输入输出系统2.输入输出系统的组成考点二:I/O接口接口的功能和组成I/O接口的基本组成3.接口类型4.程序查询方式考点三:中断系统......
  • day0722~day0726Java基础
    目录异常编译异常(受检异常)  运行异常(非受检异常)异常处理捕获异常:try…catch try...catch支持多分支catch语句书写try...catch...finally语句 throws/throw关键字 自定义异常 线程线程调度线程的优先级创建线程1.Thread类线程类2.Runnable......
  • JAVA基础
    一.编程思维和算法构建  1.抽象基类      ①AbstractCollection      ②AbstractList      ③AbstractQueue      ④AbstractSequentialList      ⑤AbstractMap      ⑥AbstractSet      详情  2.SOLID原则      ......