《算法与数据结构》第7章检索及基本算法ppt.ppt

算法与数据结构 第 7章 检索及基本算法 第 7章 检索及基本算法 7.1 检索的概念 7.2 线性表的检索 7.3 树表的检索 7.4 哈希检索 检索的概念 检索 （ searching） 也称作查找 ， 是一种常用的基本 运算 。 人们几乎每天都要做检索的工作 ， 如在电话号码薄 中查找某单位或某个人的电话号码 ， 在字典中查找 某个词的含义或读法 ， 在图书馆查找某本书刊的编 号 ， 上网在各种数据库中查找某些需要的文献资料 等等 。 在语言翻译的编译程序中要对符号表查找 ， 在数据 库系统中要用 SQL语言为各种应用设计查找程序 ， 如此等等 。 检索的概念 (续 ) 简言之 ， 检索 就是在 “ 大量信息 ” 中查找一个 “ 特定的 ” 信息 。 这里的大量信息是检索所依赖的数据结构 ， 称之 为 检索表 （ search table） ； 检索表是由同一类型的数据元素 （ 或记录 ） 组成 的集合 。 由于集合是一种松散型数据结构 ， 数据元素除了 同属于一个集合外再无别的关系 ， 所以检索表是 一种非常灵活的数据结构 。 检索的概念 (续 ) 对检索表常做的运算和操作有： 查找某个特定的数据元素是否在检索表中； 检索某个特定的数据元素的各种属性； 在检索表中插入一个数据元素； 从检索表中删去某个数据元素 。 若对查找表只作前两种统称为 “ 检索 ” 的操作 ， 称 此类检索表为 静态检索表 （ static search table） ； 若在检索的过程中同时插入表中不存在的数据元素 ， 或者从检索表中删除已存在的某个数据元素 ， 称此 类检索表为 动态检索表 （ dynamic search table） 。 检索的概念 (续 ) 所谓 特定的信息 ， 是指关键字值等于给定值的信 息 ， 信息的单位是数据元素或记录 。 关键字 （ key） 是数据元素 （ 或记录 ） 中某个数据 项的值 ， 用它可以标识一个数据元素 （ 或记录 ） 。 显然 ， 在一个记录中的每个数据项都可以作为标识 该记录的关键字 。 如人事档案记录结构为： 它含有五个关键字 ， 其中性别这个关键字标识了 一个职工的性别情况 。 检索的概念 (续 ) 主关键字 （ primary key） 是指能惟一标识一个 数据元素 （ 或记录 ） 的关键字 。 如上述记录中身 份证号码是主关键字 ， 可以惟一标识一条记录； 而姓名 、 性别 、 年龄 、 工资级别不能惟一标识一 条记录 ， 它们都不是主关键字 。 辅关键字 （ secondary key） 是用以标识若干数 据元素 （ 或记录 ） 的关键字 ， 也称作次关键字或 从关键字 。 如上述记录中的姓名 、 性别 、 年龄 、 工资级别都是辅关键字 。 检索的概念 (续 ) 检索 ， 就是根据给定的某个值 ， 在检索表中查找 一个关键字等于给定值的记录的运算或操作 。 若在检索表中存在这样的记录 ， 则称 检索成功 ， 检索的结果是找到记录的全部信息 （ 或找到记录 在检索表中的位置 ） ； 若检索表中不存在关键字值等于给定值的记录 ， 则称 检索失败 ， 给出在检索表中无要查找的记录 的信息提示 ， 并在动态检索时插入关键字等于给 定值的记录于检索表中 。 检索的概念 (续 ) 在检索表中查找某个数据元表 （ 或记录 ） 的过程 ， 依赖于这个数据元表 （ 或记录 ） 在查找表中所处 的位置；对检索表的检索方法取决于检索表中数 据元表 （ 或记录 ） 的组织策略 。 如在字典中查找一个英文单词 ， 由于字典是按字母顺 序编排的 ， 所以不需从第一个单词顺序查找 ， 而只是 按待查单词中每个字母在字母表中的位置快速找到该 单词； 而在数据元素 （ 或记录 ） 之间无任何关系组织起 来的集合中查找 ， 则需要从第一个元素 （ 或记录 ） 开始依次顺序查找 。 检索的概念 (续 ) 在计算机中进行检索是对已存入计算机中的数据 进行检索 ， 取决于采用何种数据结构来组织检索 表；往往需要在数据元素 （ 或记录 ） 之间人为地 加上一些关系 ， 即用非集合结构如数组 、 文件 、 二叉树 、 散列表等结构来组织检索表 ， 以便按某 种规律来进行检索 。 依数据组织方式不同 ， 检索分为 线性表检索 、 树 表检索 和 散列表检索 等 。 衡量一个检索算法的优劣 ， 主要依据在检索过程 中给定值和关键字的比较操作次数 。 为此 ， 我们 引入 平均检索长度 的概念 。 平均检索长度 检索算法的 平均检索长度 （ average search length） ， 即在检索过程中用给定值和关键字进 行比较的平均比较次数 ， 或者说是为找到具有给定值关键字的记录所需 要的比较次数的平均值 。 它是为确定记录在检索表中的位置 ， 需要和给 定值进行比较的关键字个数的期望值 。 平均检索长度（续） 对于含有 n个记录的检索表 ， 检索成功时的平均 检索长度为 其中 ， Pi为检索第 i个记录的概率 ， 且 ； 一般在不特殊说明的情况下均认为是等概率 ， 即 检索每个记录的概率相等 ， 。 Ci为找到第 i个记录需要和给定值比较的关键字的 个数 ， 它随检索方法的不同而不同 。 第 7章 检索及基本算法 7.1 检索的概念 7.2 线性表的检索 7.3 树表的检索 7.4 哈希检索 线性表的检索 在检索表的数据组织方式中 ， 线性表是最基本的 ， 也是最常用的一种组织方式 。 本节主要讨论在顺序 存储结构实现的线性表上的检索算法 ， 其类型定义 描述为 typedef struct keytype key; /*关键字类型 */ elemtype other; /*其它域 */ sqlist; sqlist Rn+1; /*顺序表 */ 本节介绍的线性表检索方法有 顺序检索 、 二分法检 索 、 黄金点检索 、 精算点检索 和 分块检索 等 。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 顺序检索 顺序检索 （ sequential search） 是一种最简单的基 本检索方法 。 其基本思路为： 从表的一端开始 ， 用给定值逐个与表中各记录的关键字 值比较 。 若找到某个关键字值等于给定值的记录 ， 则检索成功 ， 并给出该记录在表中的位置； 若检索完整个表仍未找到关键字值等于给定值的记录 ， 则检索失败 ， 并给出失败信息 。 顺序检索方法既适用于线性表的 顺序存储结构 ， 也适用于线性表的 链式存储结构 。 顺序检索举例 以顺序存储结构为例 ， 设数据元素存放在数组中 下标从 1到 n的记录中 ， 0号记录位置留作监视哨 ， 从下标为 n的一端开始向另一端检索 ， 顺序检索算 法可描述如下： int seqsearch(sqlist R,keytype k) int i=n; R0.key=k; /*设置 R0为监视哨 */ while(Ri.key != k) i-; return i; /*返回检索结果 i*/ 顺序检索举例（续） 算法中设置 监视哨 R0， 可以使得在检索成功和 检索失败时的处理一致 ， 在检索失败时也能在监视 哨位置找到关键字值为 k的记录 ， 可省去在 while循 环中的位置越界检查 （ i=1） 。 若从 R0处向后顺序检索 ， 监视哨可设置在 Rn处 。 算法执行之后 ， 非 0的函数值表示待查找记录在数 组中的位置 （ 下标 ） ；若函数值为 0说明检索表中 没有要查找的记录 。 顺序检索（续） 对于具有 n个记录的检索表 ， 若待查找记录在 Rn 处 ， 需要和给定值 k比较一次 ， 即 Cn=1； 若待查找记录在 Rn-1处 ， 需要和给定值 k比较两 次 ， 即 Cn-1=2； 一般地 ， 若待查找记录在 Ri处 ， 需和给定值 k比 较 n-i+1次 ， 即 Ci=n-i+1。 因此 ， 在等概率的情况下顺序检索的平均检索长 度为 顺序检索（续） 在检索成功时顺序检索的平均比较次数约为 表长 的一半 。 在检索失败时 ， 顺序检索需要进行 n+1次的比较 。 当 n很大时 ， 平均检索长度也很大 ， 检索效率较低 ， 这是顺序检索的主要缺点 。 但由于顺序检索对表的存储结构和元素存放次序 没有要求 ， 且算法简单 ， 在许多实际应用中常被 采用 。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 二分法检索 二分法检索 （ binary search） ， 也称作折半检索 ， 它是一种效率较高的检索方法 。 它要求检索表是用 顺序存储结构表示 ， 且数据元素的存放要按关键字 值有序排列 。 二分法检索的基本思想是： 在有序表中先取中间位置作为比较对象 ， 若给定值与中 间记录的关键字值相等 ， 则检索成功； 若给定值小于中间记录的关键值则在表的左半区查找 ， 若给定值大于中间记录的关键字值则在表的右半区查找 。 就这样经过一次的比较缩小一半的检索区间 ， 在每一个 检索区间都是选取中间位置作为比较对象 ， 不断地重复这 样的检索过程直到检索成功 ， 或者检索区间已无记录时检 索失败 。 二分法检索举例 例如 ：已知一个含 15个记录的有序表 ， 其关键字序 列如下： （ 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52） 现在要检索给定值 k为 19、 46和 11的记录 ， 其检索 过程如下： 用 low和 high分别表示检索区间的下界和上界； 用 mid指示中间位置 ， 即 mid=(low +high)/2； 检索开始时 low=1， high=n；即检索区间为 1， n。 二分法检索举例 检索 k=18 检索 k=18的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 high=15 检索开始时 ， low=1， high=15， mid=(1+15)/2=8。 由于 k=1829=R8.key， 所以应在右半区继续检索； 此时 low=mid+1=8+1=9， mid= (9+15)/2=12， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=9 mid=12 high=15 由于 k=4642=R14.key， 所以应在当前区间的右 半区继续检索； 二分法检索举例 检索 k=46(续 ) 此时 low=12+1 =13， mid=(13+15)/2=14， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13mid=14high=15 由于 k=4649=R14.key， 所以应在当前区间的左半 区 继 续 检 索 ； 此 时 high=mid-1= 14-1=13 ， mid=(13+13)/2=13， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13 mid=13 high=13 由于 k=46=R13.key， 此时检索 46成功 。 二分法检索举例 检索 k=11 检索 k=11的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 high=15 由于 k=1129=R8.key， 应在左半区继续检索；此 时 high= mid-1=8-1=7， mid= (1+7)/2=4， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=4 high=7 由于 k=1110=R2.key， 应在当前区间的右半区继 续检索；此时 low=2+1=3， mid= (3+3)/2=3， 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=3 mid=3 high=3 由于 k=1114=R3.key， 应在当前区间的左半区继 续检索；此时 high=mid-1= 3-1=23=low， 左半区已 没有元素 （ 不存在区间了 ） ， 检索 k 11失败 。 二分法检索过程可用 C语言描述 二分法检索过程可用 C语言描述为如下算法： int binarysearch (sglist R,keytype k) int low,mid,high; low=1; high=n; while(low=high) mid=(low+high)/2; if(k=Rmid.key) return mid; else if(k100， 则可有如下近似结果： 二分法检索过程分析（续） 由此可见 ， 二分法检索的效率比顺序检索高得多 ， 如 n=127时 ， 顺序检索 ASL 64而二分法则为 ASL 6。 二分法检索只适用于检索表为顺序存储结构之下 的有序表 ， 即这种较高的检索效率是以对检索表预 先按关键字值大小排序为代价的 ， 所以二分法检索 适合于一旦建立很少变动而又需要经常检索的检索 表 。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 黄金分割点检索 黄金分割点检索 （ gold-partition search） ， 简称黄 金点检索 。 它是利用我国著名数学家华罗庚院士当 年推广优选法时介绍的黄金分割点的概念 ， 即利用 黄金分割数 0.618把检索区间分为两个不等的区间 。 每次用给定值与黄金点上的记录的关键字比较 ， 若相等检索成功 ， 若给定值小于黄金点关键字值 ， 继续在黄金点之前的区间检索；若给定值大于黄金 点关键字值 ， 继续在黄金点之后的区间检索 。 通过黄金点逐次缩小检索区间 ， 直到检索成功 ， 或区间已无记录检索失败时止 。 黄金分割点检索举例 例如 ， 仍以前面的 15个记录为例 ， 检索 k 46的黄金分割点 检索过程为： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=9 high=15 开始时 low=1 ， high=15 ， mid=low+0.618*(high-low+1)- 1=1+0.618*(15-1+1)-1=9.329。 给定值 k=4631=R9.key， 在 黄 金 点 之 后 的 区 间 继 续 检 索 。 此时 low=9+1=10 ， mid=10+0.618*(15-10+1)-1=12.70813。 即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=10 mid=13 high=15 由于 k=46=R13.key 检索成功 。 一个用二分法检索需 4次比 较的工作 ， 黄金分割点检索只需两次比较就完成了 。 黄金分割点检索算法描述 int goldpartsearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; while(low=high) /*逐次缩小区间检索 */ mid=low+0.618*(high-low+1)-1+0.5; if(k=Rmid.key) return mid; else if(kRmid.key) high=mid-1; /*修改区间上界 */ else low=mid+1; /*修改区间下界 */ return 0; 黄金分割点检索（续） 该算法的时间性能与二分法相比 ， 在平均性能上优于二分法 ， 但仍然是；在最坏情况下 ， 每次比较之后都在较大的区间内 继续检索 ， 比二分法差；在最好情况下 ， 每次比较之后都在 小区间内继续检索 ， 比二分法好 。 所谓 黄金分割点 ， 就是利用 Fibonacci数列对检索表分割 得到的一系列位置 。 Fibonacci数列的定义为： 黄金分割点检索（续） 注意观察 “ Fibonacci数列及其相邻项的比值 ” 表中给出的 F(n)/F(n+1)的值 ， 从 n=6之后基本上稳定在 0.618处 。 因此 ， 我们可以对长度为 F(n)的检索表 ， 第一次用 F(n-1) 处记录的关键字同给定值比较；由 F(n-1)分割的两个区间的 长度分别为 F(n-2)-1和 F(n-3)， 又都可以利用 Fibonacci 数列找出新的分割点；如此一直进行下去 ， 就可获得检索成 功或失败的结果 。 然而 ， 检索表的长度很难是某个 Fibonacci数列或接近 Fibonacci数的值；其次即就是 Fibonacci数 ， 也还得为 Fibonacci检索准备一张 Fibonacci数表或通过循环递推求 出每次要用的 Fibonacci数 ， 所以说利用 Fibonacci数列设 计检索算法不如直接使用黄金分割数 0.618设计检索算法方 便 。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 精算点检索 对于有序的检索表 ， 如果记录的关键字值不仅有 序 ， 而且分布均匀或比较均匀 ， 我们能不能很快 地完成关键字值等于给定值记录的检索任务呢 ？ 回答是肯定的 ， 下面将要介绍的精算点检索就可 以解决这个问题 。 所谓 精算点检索 （ precise computing search） ， 也称作插值检索 。 它是利用检索区间有序关键字 值范围和给定值的大小比例关系估算检索位置的 一种检索方法 。 精算点检索（续） 当关键字值分布均匀时应满足下式： 其中 k为给定值 ， mid为估算位置 ， low和 high分别 为检索区间下界和上界位置 ， 经整理可得估算公式 为： 当给定值 k等于 Rmid.key则检索成功；否则若 kRmid.key则 在 mid之后检索 。 精算点检索（续） 在关键字值均匀分布时 ， 如呈等差数列时一次比 较便可检索成功；在关键字值分布比较均匀时 ， 若一次比较不能找到也会在 mid位置附近 ， 这两种 情况的检索长度与检索表的大小 n无关 ， 所以称之 为 精算点检索 。 如果关键字值 分布不均匀 ， 可缩小检索区间继续 用前面的估算公式确定检索点检索 ， 其检索性能 也优于黄金分割点检索和二分法检索 。 精算点检索举例 例如 ， 对于前述的 15个记录的检索表 ， 检索 k=14 的记录 ， low=1， high=15， ， R3.key=14等于给定值 ， 一次比较检索成功；又如 检索 k=29 时 ， ， 一次比较 Rn.key=29等于给定值检索成功；再如检索 k=46 时 ， ， 一次比较 R13.key=46 等于给定值检索成功；等等 。 精算点检索举例（续） 既然在关键字值分布较均匀时 ， 即使一次比较不能 检索成功也会在 mid位置附近 ， 在算法设计时就只需 一次计算 mid的值 。 若 k=Rmid.key， 则一次比较检索成功； 若 kRmid.key， 则可由 mid后一个记录开始向后 顺序检索 ， 直到检索成功或某个记录的关键字值大 于给定值 k时检索失败 。 精算点检索算法描述 这种与顺序检索相结合的精算点检索算法可描述如下： int precisesearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; mid=low+(k-Rlow.key)*(high-low)/ (Rhigh.key-Rlow.key)+0.5; if(k=Rmid.key) return mid; else if(kk) mid-; 精算点检索算法描述（续） if(Rmid.key=k) return mid; /*检索成功返回位置 */ else return 0; /*检索失败返回 0*/ else mid+; /*若给定值大于 mid时在 mid后检索 */ while(Rmid.keyk) /*向后顺序检索 */ mid+; if(Rmid.key=k) return mid; /*检索成功返回位置 */ else return 0; /*检索失败返回 0*/ 精算点检索算法分析 该算法中的两个当型循环 ， 在关键字值分布较均 匀的情况下 ， 检索长度与检索表的长度 n无关 ， 平 均检索长度趋近于某个常数； 在关键字值分布不均匀的情况下 ， 检索长度在最 坏的情况下也不会超过二分法检索和黄金分割点 检索； 精算点检索是平均性能最好的检索方法 ， 对于检 索表较大和分布较均匀时 ， 使用精算点检索特别 合适 。 7.2 线性表的检索 7.2.1 顺序检索 7.2.2 二分法检索 7.2.3 黄金分割点检索 7.2.4 精算点检索 7.2.5 分块检索 精算点检索算法分析 分块检索 （ blocking search） ， 又称作索引检索 ， 它是顺序检索的一种改进方法 ， 其效率介于顺序检 索和二分法检索之间 。 分块检索不要求检索表中所有记录关键值有序排 列 ， 但要求把检索表分成若干块之后各块之间按关 键字值大小有序 。 即分块检索要求检索表的 特点 是：块间有序 ， 块内无序 。 所谓块间有序是指块间升序或块间降序 。 在块间升序时 ， 每一块中所有记录的关键字值均大于和 该块相邻的前一块中最大的关键字值； 在块间降序时 ， 每一块中所有记录的关键字值均小于和 该块相邻的前一块中最小的关键字值 。 精算点检索算法分析（续） 在分块检索中 ， 除检索表本身之外 ， 还需要建立一张索引 表 。 如下图给出了一张块间升序的检索表的索引表 ， 每个块 在索引表中有一个索引项 ， 每个索引项中包含有该块中最大 的关键字值和该块第一个记录在检索表中的位置 。 本例中检索表分为三块 ， 各块中最大关键字值依次为 22、 48和 86， 各块中第一个记录在检索表中的位置依次为 1、 7和 13；第二块中的最小关键字值 24大于第一块中的最大关键字 值 22， 第三块中的最小关键字值 49大于第二块中的最大关键 字值 48。 精算点检索算法分析（续） 下图中给出了一张块间降序的检索表的索引表 ， 每个块在 索引表中也是一个索引项 ， 但索引项中包含的是块中最小的 关键字值和该块第一个记录在检索表中的位置 。 该例中检索表分为四块 ， 各块中最小关键字值依次为 47、 32、 22和 9， 各块中第一个记录在检索表中的位置依次是 1、 6、 11和 16；第二块中的最大关键字值 45小于第一块中最小 的关键字值 47， 第三块中的最大关键字值 31小于第二块中的 最小关键字值 32， 第四块中的最大关键字值 20小于第三块中 最小的关键字值 22。 精算点检索的基本思想 分块检索的基本思想是： 首先依据给定值在索引表中检索 ， 以确定待查找 记录所属的块； 由于索引表是有序表 ， 所以可以用二分法检索 ， 也可以用顺序检索或其它检索方法进行 。 然后在确定的块内检索关键字值等于给定值的记 录 ， 由于块内记录无序排列 ， 所以只能用顺序检 索方法进行 。 精算点检索举例 例如 ， 要在前例 “ 块间升序的检索表及其索引表示 例 ” 中检索 k=38的记录： 先将 k依次和索引表中各个最大关键字进行比较 ， 由于 22k48， 所以 k=38的记录若存在必在第二个块中； 然后从第二个块的起始地址开始顺序检索 ， 直到 R10.key=k时检索成功 。 再如检索 k=76的记录： 将 k和索引表中各个最大关键字值比较 ， 由于 48k50则在右 子树中继续检索；再用 80和右子树的根 70比 较 ， 8070则继续在当前根结点 70的右子树 中检索；当再次和新的当前根结点比较时二 者相等检索成功 ， 返回指向当前根结点的指 针 。 又如检索 k=15的记录时 ， 由于 15小于根结 点 50， 在其左子树继续检索； 15又小于左子 树的根结点 40， 继续在当前根结点 40的左子 树中检索； 15也小于当前根结点 40的左子树 的根结点 20， 当在 20的左子树中继续检索时 发现 20的左子树为空 ， 检索失败返回 NULL。 二叉检索树的二叉链表类型 设二叉检索树以如下描述的二叉链表作为存储结 构： typedef struct node keytype key; /*关键字域 */ elemtype other; /*其它数据域 */ struct node *lchild, *rchild; /*左右孩子指针域 */ bstnode; /*定义结点类型 bstnode*/ typedef bstnode *bstlist; /*定义二叉检索树表类型 bstlist*/ 二叉检索树的检索算法描述 二叉检索树的检索算法可描述如下： bstlist bstsearch(bstlist t,keytype k) bstlist p ; p=t; if(p=NULL)|(p-key=k) return p; else if(p-keyrchild,k); else return bstsearch(p-lchild,k); /*bstsearch end*/ 2.二叉检索树的构造过程和插入操作 对于一组关键字无序的记录 ， 构造其相应的二叉检索 树的方法是：从一棵空的二叉检索树开始 ， 每当读入 一个记录就生成一个结点 ， 然后按关键字值的大小插 入到当前的二叉检索树之中；当所有记录的结点都已 插入二叉检索树中时便构造完毕 。 虽然 ， 插入操作是构造二叉检索树的关键操作 。 要保 证在一棵二叉检索树中插入一个结点之后 ， 仍然满足 二叉检索树的定义 。 其插入过程为： 若二叉检索树为空 ， 则插入结点作为新的根结点； 若二叉检索树非空 ， 则在非空的二叉检索树中检索插入结 点；如果检索成功就不必插入 ， 否则插入结点作为新的叶结 点 ， 并成为检索路径上最后一个结点的左孩子或右孩子 。 二叉检索树的构造过程和插入操作 (续 ) 为了实现这一插入过程 ， 在二叉检索树非空时需要知 道检索路径上的最后一个结点位置 ， 才能够准确地把 插入结点作为左孩子或右孩子插入二叉检索树中；为 此；需要在检索过程中设一指针变量记下当前结点的 前趋 （ 即双亲 ） 结点位置 。 插入算法的形式化描述如下： bstlist insertbst(bstlist t,keytype k) bstlist s,p,q; if(t=NULLl) p=(bstlist)malloc(sigeof(bstnode); p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; return p; 二叉检索树的构造过程和插入操作 (续 ) p=t; while(p!=NULL) q=p; if(p-key=k) /*检索成功不必插入 */ return t; /*返回原二叉检索树 */ else if(p-keyrchild; else p=p-lchild; p=(bstlist)malloc(sizeof(bstnode); 二叉检索树的构造过程和插入操作 (续 ) p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; if(kq-key) q-rchild=p; else q-lchild=p; return t; 二叉检索 (排序 )树构造过程举例 从空树出发经过一系列的检索插入操作之后 ， 就可生成一 棵 二叉检索树 。 一个无序序列可以通过构造一棵二叉检索树 而变成一个有序序列 （ 即中序遍历次序序列 ） ， 构造的过程 就是对无序序列进行排序的过程 ， 所以又称作 二叉排序树 。 设关键字序列为 （ 45， 22， 57， 18， 29， 92） ， 生成二叉 检索树 （ 即二叉排序树 ） 的过程如下图所示 。 3.二叉树检索树的删除操作 在二叉检索树中删除一个结点 ， 相当于在检索表中 删除一个记录 ， 不能把以待删除结点为根结点的子树 全部删去 ， 并且要保证删除某个结点后的二叉树仍然 是一棵二叉检索树 。 下面 ， 我们分三种情况讨论如何 在二叉检索树中删除一个结点 。 待删除结点是度为 0的叶子结点 删除一个叶子结点 *p， 不破坏整棵树的结构 ， 只 需将其双亲结点 *f与 *p之间相链接的指针域置为空即 可： f-lchild=NULL; 或 f-rchild=NULL; 二叉树检索树的删除操作（续） 待删除结点是度为 1的单枝结点 即待删除结点只有左子树或只有右子树的情况 ， 如下图所 示 。 此时只需将待删除结点 *p的惟一后继结点 （ 左孩子或右 孩子 ） 直接链接到其双亲结点 *f的相应位置 （ 即左链域或右 链域 ） 上即可： (a) f-lchild=p-lchild; 或 (b) f-lchild=p-rchild; 或 (c) f-rchild=p-lchild; 或 (d) f-rchild=p-rchild; 二叉树检索树的删除操作（续） 待删除结点是度为 2的双枝结点 即待删除结点既有左子树又有右子树的情况 ， 如下图所 示 ， 为了保持二叉检索树的特性 ， 通常有如下四种做法 。 二叉树检索树的删除操作 方法一 方法一：找出待删除结点 *p的中序前趋结点 *q， 把 *q的关键 字域和数据域的值赋给 *p的相应域 ， 即： p-key=q-key; p-other=q-other; 然后删除其中序前趋结点 *q， 由于 *p的中序前趋 *q是 *p左子 树上的最右下结点 ， 所以 *q必是叶子结点或单左枝结点 ， 如 下图所示；其删除方法见 和 。 二叉树检索树的删除操作 方法二 方法二：找出待删除结点 *p的中序后继结点 *q， 把 *q的关键 字域和数据域的值赋给 *p的相应域 ， 即： p-key=q-key; p-other=q-other; 然后删除其中序后继结点 *q。 由于 *p的中序后继 *q是 *p右子 树上的最左下结点 ， 所以 *q必是叶子结点或单右枝结点 ， 如 下图所示；其删除方法见 和 。 二叉树检索树的删除操作 方法三 方法三：将待删除结点 *p的右子树链接到它的中 序前趋结点 （ 即左子树上的最右下结点 ） *q的右孩 子域上 ， 然后把它的左子树直接链接到其双亲结点 *f的左 （ 或右 ） 孩子域上 。 即： q-rchild=p-rchild; f-lchild（ 或 f-rchild） =p-lchild; 二叉树检索树的删除操作 方法四 方法四：将删除结点 *p的左子树链接到它的中序 后继 （ 即右子树上的最左下结点 ） *q的左孩子域上 ， 然后把它的右子树直接链接到其双亲结点 *f的左 （ 或右 ） 孩子域上 。 即： q-lchild=p-lchild; f-lchild（ 或 f-rchild） =p-rchild; 二叉树检索树的删除操作（续） 前两种方法是以删除待删除结点 *p的中序前趋或 中序后继 *q来实现删除结点 *p之目的 ， 不需要知道 待删除结点的双亲结点位置； 后两种方法是直接删除待删除结点 *p， 不仅需要 知道其中序前趋或中序后继 *q的位置 ， 还需要在检 索待删除结点 *p的同时记住其双亲结点的位置 。 二叉树检索树的删除操作（续） 方法一和方法三中 *p的中序前趋 *q（ 即左子树中的 最右下结点 ） 可以如下确定： q=p-lchild; while(q-rchild!=NULL) q=q-rchild; 而方法二和方法四中 *p的中序后继 *q（ 即右子树中 的最左下结点 ） 的确定方法为： q=p-rchild; while(q-lchild!=NULL) q=q-lchild; 二叉检索树的删除算法描述 下面我们给出采用方法四删除双枝结点时的二叉检 索树的删除算法描述如下： bstlist deletebst(bstlist t,keytype k) bstlist p,q,r,f; p=t; f=NULL; while(p!=NULL) if(kkey) p=p-lchild; else p=p-rchild; 二叉检索树的删除算法描述（续） if(p=NULL) break; /*检索失败时不用删除中断执行 */ if(p-lchild=NULL)|(p-rchild=NULL) q=p; /*待删除的 *p为叶子结点或单枝结点时 */ else q=p-rchild; while(q-lchild!=NULL) q=q-lchild; if(q-lchild!=NULL) r=q-lchild; else r=q-rchild; 二叉检索树的删除算法描述（续） if(p!=q) q-lchild= p-lchild; if(f-lchild=p) f-lchild=r; else f-rchild=r; return t; /*返回删除操作后的二叉检索树 */ /*deletebst end*/ 4.二叉检索树的检索性能分析 在二叉检索树上检索关键字值等于给定值 k的记录 ， 正好是走了一条从根结点到关键字值为 k的结点的路 径 ， 和给定值 k的比较次数为路径长度加 1（ 或结点所 在层次数 ） ， 和二分法检索类似 ， 其比较次数不超过 树的深度 。 然而 ， 用 二分法检索 一个长度为 n的检索表其检索过 程的二叉树表示是 惟一 的 ， 而含有 n个结点的 二叉检 索树 却 不惟一 。 二叉检索树的检索性能分析举例 例如 ， 如下图给出了结点值都相同的两棵二叉检索 树 ， 由于构造时的关键字序列不同 ， 前者深度为 3， 而后者深度为 7；在等概率的情况下 ， 前者的平均检 索长度为 ASL=(1+2+2+3+3+3+3)/7=17/7， 后者的平均 检索长度为 ASL=(1+2+3+4+5+6+7)/7= 28/7=4。 二叉检索树的检索性能分析（续） 因此 ， 含有 n个结点的二叉检索树的平均检索长度 和二叉检索树的形态有关 ， 当先后插入的关键字按值 有序时 ， 构造的二叉检索树蜕变为单枝树； 升序时为 单右枝二叉树 ， 降序时为 单左枝二叉树 ； 树的深度为 n， 平均检索长度为 (n+1)/2（ 和顺序检 索相同 ） ， 这是最差的情况 。 最好的情况是二叉检索 树的形态和二分法检索过程得到的树相同 ， 树的高度 和完全二叉树的高度相同 ， 其平均检索长度为 。 二叉检索树的检索性能分析（续） 现在我们考虑在一般情况下二叉检索树的平均检索 长度 ， 假设在含有 n个结点的二叉树中 ， 有 i个结点关 键字值小于根结点的关键字值 ， n-i-1个结点关键字值 大于根结点的关键字值 。 在等概率检索的情况下平均检索长度为： 其中 ， p(i)为含有 i个结点的二叉检索树的平均检索长度； p(i)+1为检索左子树中每个结点所用比较次数的平均值 ， p(n-i-1)+1为检索右子树中每个结点所用比较次数的平均值 。 二叉检索树的检索性能分析（续） 由于根结点的左子树中有 0个 ， 1个 ， ， n-1个结点 的情况是等概率的 ， 对上式取平均值得： 用数学归纳法可以证明 ， ， 即二叉检 索树的平均长度为 。 7.3 树表的检索 7.3.1 二叉检索树 7.3.2 二叉检索树的平衡性调整 7.3.3 B树和 B+树 平衡因子 平衡因子 （ balance factor） 二叉树上任一结点的平衡因子 ， 定义为该结点的左子树深 度减去右子树深度的差 。 如下图中给出了一些二叉树 ， 其结点上所示数值为 该结点的平衡因子值 。 平衡二叉树 平衡二叉树 （ balance binary tree） 如果一棵二叉树中所有结点的平衡因子的绝对值不超过 1， 则称该二叉树为 平衡二叉树 ；平衡二叉树也称作 AVL树 。 显然 ， AVL树要么是一棵空树 ， 要么其左右子树深 度不超过 1且都是 AVL树；只要二叉树上有一个结点 的平衡因子的绝对值大于 1， 该二叉树就是不平衡的 。 如前例图中 ， (a)和 (b)都是平衡二叉树 （ 即 AVL树 ） ， 而 (c)和 (d)都不是平衡二叉树 （ 即非 AVL树 ） 。 平衡二叉树（续） 由于 AVL树具有良好的形态 ， 其左右子树的深度差不 超过 1；对于给定的结点数目 n， AVL树的平均深度接 近于完全二叉树的深度 ； 所以我们希望由任何初始序列构成的二叉检索树都 是 AVL树 ， 使得其平均检索长度接近于 。 如何使构造的二叉树成为 AVL树呢 ？ Adelson- Velskii和 Landis提供了一个动态地保持二叉检索树 平衡性的方法； 其基本思想是在构造二叉检索树的过程中 ， 每当插入一个 结点后都去检查是否由于该结点的插入而破坏了二叉检索 树的平衡性；若出现绝对值超过 1的平衡因子 ， 则需要在保 持二叉检索树特性的前提下通过调整使之达到新的平衡 。 平衡二叉树（续） 在一般情况下 ， 设在插入结点的过程中使二叉检索 树失去平衡的最小子树的根结点为 a， 即 a为离插入 结点最近且平衡因子绝对值超过 1的祖先结点； 因插入结点的位置不同而失去平衡需要调整的规律 可归纳为如下四种情况： LL型平衡旋转 （ 右单旋型 ） RR型平衡旋转 （ 左单旋型 ） LR型平衡旋转 （ 先左后右双旋型 ） RL型平衡旋转 （ 先右后左双旋型 ） 1.LL型平衡旋转（右单旋型） 这种失衡是由于在结点 a的左孩子 b的左子树上插入结点 ， 使结点 a的平衡因子由 1增至 2而造成的 。 其 调整策略 是以 a的左孩子 b为轴心顺时针旋转 （ 即向右旋 转 ） 一次；使结点 a成为其左孩子 b的右孩子 ， 而 b的右子树 成为 a的左子树 ， 如下图所示 。 这种调整策略既使结点的平 衡因子满足 AVL树的要求 ， 又保持了二叉检索树的特性 （ 即 中序遍历次序为上升序列 ） 。 2.RR型平衡旋转（左单旋型） 这种失衡是由于在结点 a的右孩子 b的左子树上插入结点 ， 使 a的平衡因子由 -1变成 -2而造成的； 其 调整策略 是以 a的右孩子 b 为轴心逆时针旋转 （ 即向左旋 转 ） 一次；使 a成为 b的左孩子 ， 而 b的左子树成为 a的右子树 ， 如下图所示 。 3. LR型平衡旋转（先左后右双旋型） 这种失衡是由于在结点 a的左孩子 b的右子树上插入结点 ， 使 a的平衡因子由 1增至 2造成的 。 设 c是 b的右孩子 ， 插入结点的位置有三种可能性： c就是插入结点 ， 这是由于插入前 b为叶子结点且 a无右孩子而产生的 一种可能； 插入结点在 c的左子树上； 插入结点在 c的右子树上 。 LR型平衡旋转（续） 对这三种导致 LR型失衡的情况 ， 其 调整策略 是一致的： 即以 a的左孩子 b的右孩子 c为轴心 ， 先逆时针 （ 即向左 ） 旋转一次 ， 再顺时针 （ 即向右 ） 旋转一次；使 c的左子树 成为 b的右子树 ， c的右子树成 a的左子树 ， b成为 c的左孩子 而 a成为 c的右孩子 ， 以 “ 插入在 c的左子树上 ” 为例 ， 两次 旋转的调整过程如下图所示 。 4. RL型平衡旋转（先右后左双旋型） 这种失衡是由于在结点 a的右孩子 b的左子树上插入 结点 ， 使 a的平衡因子由 -1变成 -2造成的 ， 设 c是 b的 左孩子 ， 插入结点位置的三种可能性如下图所示 ： RL型平衡旋转（续） 对这三种导致 RL型失衡的情况 ， 其 调整策略 为： 以 a的右孩子 b的左孩子 c为轴心 ， 先顺时针 （ 即向右 ） 旋 转一次 ， 再逆时针 （ 即向左 ） 旋转一次；使 c的左子树成 为 a的右子树 ， c的右子树成为 b的左子树 ， a成为 c的左孩 子而 b成为 c的右孩子 。 以 “ 插入在 c的左子树上 ” 为例 ， 两次旋转的调整过程如下图所示： 构造平衡二叉检索树举例 例如 ， 对于一组记录其关键字序列为 （ 18， 5， 10， 15， 12， 11， 20） ， 要建立一棵平衡的二叉检索树 ， 其构造过程如下 图所示： 构造型平二叉检索树的算法 在设计构造平衡的二叉检索树的算法时 ， 需要先为 每个结点增加一个平衡因子域 ， 然后在二叉检索树构 造算法的基础上做几点修改： 插入一个结点后 ， 要修改树中各结点平衡因子的值； 判别是否因插入结点产生失衡 ， 在失衡时找到失衡的最 小子树； 判别失衡类型并做相应的调整处理 。 在平衡的二叉检索树上进行检索的过程 ， 和在二叉 检索树上的检索过程一致 ， 在检索过程中和给定值比 较的次数不会超过树的深度 ， 而含有 n个结点的平衡 二叉检索树的最大深度为 ， 其中 。 7.3 树表的检索 7.3.1 二叉检索树 7.3.2 二叉检索树的平衡性调整 7.3.3 B树和 B+树 B树 B树 是一种平衡的多路检索树 ， 是文件系统 （ 包 括大型数据库文件系统 ） 中的一种重要的数据组织 结构 。 一棵 m阶 B树 ， 或者为空树 ， 或者为满足下列特性 的 m叉树： 树中每个结点至多有 m棵子树 （ 即至多有 m-1 个关键字 ） ； 除非根结点为叶子结点 ， 否则至少有两棵子 树 （ 即至少有一个关键字 ） ； 除根结点之外的所有非终端结点至少有棵子 树； B树（续） 所有的非终端结点中包含以下信息： （ n， A0， k1， A1， k2， ， kn， An ） 其中： n（ nm-1） 为关键字的个数 ， 即子树个数为 n+1； ki（ 1in） 为关键字 ， 且 kiki+1（ 1in） ； Ai（ 0in） 为指向其子树的根结点的指针 ， 且 Ai （ 0in） 所指子树中所有结点的关键字值都小于 ki+1， An 所指子树中所有结点的关键字值都大于 kn； 所有叶子结点在同一个层次上 ， 且不含有任何 信息 （ 可以看作是外部结点或检索失败的结点；实 际上这些结点不存在 ， 指向这些结点的指针为 NULL） 。 B树示全例 下图给出了一棵 4阶 B树的示例： B树的插入操作 在 B树上插入一个关键字 ， 不是象在二叉检索树中 那样添加一个叶子结点 ， 而是在 B树的最底层的某个 非终端结点中添加一个关键字 。 若该结点中关键字的个数小于 m-1个则插入完成； 否则添加后关键字个数由 m-1个变为 m个与 B树定义不 符 ， 需要进行结点的 “ 分裂 ” 以满足 B树定义 。 结点的分裂方法为 ， 把中间一个关键字拿出来插入到该 结点的双亲结点上 ， 前后两部分各自形成一个结点；双 亲结点中也可能有 m个关键字 ， 就需要继续分裂结点 ， 直 到插入到某个关键字个数小于 m-1的祖先结点 。 由这种分裂过程可见 ， B树是由底向上生长的 。 B树的插入操作举例 B树的插入过程如下图所示 ， 图中只画出了非终端 结点 ， 省去了最底层的叶子结点 。 B树的删除操作 在 B树上删除一个关键字和插入关键字类似也是由 底向上的调整过程 ， 先找到该关键字所在的结点并删除这个关键字 。 若找到的结点是最底层的非终端结点 ， 当关键字个数大 于则删除完成 ， 否则删除后关键字个数由个变为个与 B树 定义不符 ， 需要进行结点的 “ 合并 ” 以满足 B树定义 。 合并的方法是把删除了关键字的结点同其左兄弟结点 （ 或右兄弟结点 ） 合并 ， 连同它们的双亲结点中的相关 关键字项一块合并重新分配 ， 在其双亲结点不满足 B树定 义时继续向上调整直到根结点 。 若找到的待删除关键字所在结点不是底层非终端结点 ， 则是将该关键字用其 B树中的后继替代 ， 而删除其后继的 信息 。 B树的删除操作举例 B树的删除过程如下图所示： B树的检索操作 在 B树中进行检索的过程是： 首先在根结点中所包含的关键字中检索给定的关键字 ， 若找到则检索成功 ， 否则确定待检索关键字所在的子树 ， 并在该子树中继续检索 ， 直到检索成功或指针为空时检 索失败 。 例如 ， 在前例中的一棵 4阶 B树中检索关键字值为 61的记录 ， 因根结点中不存在此关键字 ， 则到大于 39的子树中检索；又 因为子树的根结点中没有此关键字 ， 而 506180， 故再到 s 所指子树中检索 ， 在这个结点中含有 61的关键字值则检索成 功 。 又如在此 4阶 B树中检索关键字值为 75的记录 ， 也是沿前面 的这一条路线检索 ， 由于 s所指结点中没有值为 75的关键字而 检索失败 。 B树的检索操作（续） B树的检索是在 B 树上找结点和在结点中找关键字 两个基本操作的交叉进行过程 ， 待查关键字所在结 点在 B树中的层次是决定 B树检索效率的首要因素 ， 最坏的情况下是含 n个关键字的 m阶 B树的最大深度 。 由 B树定义 ， 第一层至少有 1个结点 ， 第二层至少有 2个结点；由于除根结点外的每个非终端结点至少有 棵子树 ， 则第三层至少有 2（ ） 个结 点； ；依此类推 ， 第 h+1层至少有 个结 点；而 h+1层为叶子结点 。 若 m阶 B树有 n个关键字 ， 则叶子结点即查找不成功的结点数为 n+1， 由此有 B+树 B+树是应用于文件系统中的 B树的一种变形树 ， 它 与 B树的差异主要在于： 有 n棵子树的结点中含有 n个关键字； 所有叶子结点中包含了全部关键字的信息 及指向相应记录的指针 ， 且叶子结点以关键字递增 顺序链接； 所有的非终端结点可以看成是索引部分 ， 结点中仅含有其子树中的最大 （ 或最小 ） 关键字 。 B+树举例 如下图给出了一棵 3阶 B+树 。 通常 B+树上有两个指针 ， 一个指向根结点 ， 一个指 向关键字值最小的叶子结点 。 因此 ， 对于 B+树既可从根结点开始多级索引顺序检 索 ， 又可以从最小关键字开始顺序检索 。 B+树的操作 在 B+树上进行插入 、 删除和检索的过程与 B树基本相 似 。 在检索过程中在非终端结点上找到给定值后并不终止 ， 而是继续向下直到叶子结点；因而无论是检索成功还是检 索失败 ， 每次检索都是走了一条从根结点到叶子结点的路 径 。 B+树的插入仅在叶子结点上进行 ， 当叶子结点中关键字 个数大于 m时也要分裂成两个结点 ， 并且其双亲结点中同 时也包含这两个结点的关键字最大值 。 B+树的删除也在叶子结点中进行 ， 其在非终端结点中的 值可以作为分界关键字存在；当然在删除后若使结点中关 键个数小于 时也要进行结点的合并操作 。 第 7章 检索及基本算法 7.1 检索的概念 7.2 线性表的检索 7.3 树表的检索 7.4 哈希检索 哈希检索 在前两节介绍的线性表检索和树表检索方法后 ， 由 于记录在检索表中的位置是随机的或按关键字值大 小次序排列的 ， 记录的存储位置和其关键字值之间 不存在某种确定的关系 ， 存储位置依赖于关键字的 初始随机序列或在检索表中其它关键字值的大小 。 所以在检索时需要进行一系列的关键字值与给定值 之间的比较 ， 其检索效率和检索过程中进行的比较 次数有关 。 本节介绍一种直接利用关键字值计算记录在检索表 中的存储位置来进行检索的方法 哈希 （ Hash） 检索技术 。 7.4 哈希检索 7.4.1 哈希检索与哈希表 7.4.2 哈希函数的构造方法 7.4.3 地址冲突的消解策略 7.4.4 哈希表的检索算法及性能分析 哈希检索与哈希表 哈希检索技术的初衷是组织理想状态的检索表 。 检索表的理想状态是：把记录的关键字值与记录在 检索表中的存储位置建立起某种一对一的关系 ， 这 种一对一的关系可以用关于关键字的一个 函数 h(key