第7章 检索及基本算法_第1页
第7章 检索及基本算法_第2页
第7章 检索及基本算法_第3页
第7章 检索及基本算法_第4页
第7章 检索及基本算法_第5页
已阅读5页,还剩155页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

,靠法与剧据秸构

第7章检索及基本算法

[第7章检索及基本算法

7.1检索的概念

7.2线性表的检索

7.3树表的检索

7.4哈希检索

1检索的概念

■检索(searching)也称作查找,是一种常用的基本

运算。

■人们几乎每天都要做检索的工作,如在电话号码薄

中查找某单位或某个人的电话号码,在字典中查找

某个词的含义或读法,在图书馆查找某本书刊的编

号,上网在各种数据库中查找某些需要的文献资料

等等。

玉总言翻译的编译程序中要对符号表查找,在数据

库系统中要用SQL语言为各种应用设计查找程序,

如此等等。

,检索的概念(续)

■简言之,检索就是在“大量信息”中查找一个

“特定的”信息。

■这里的大量椁骨、是检索所依赖的数据结构,称之

为检索表(searchtable);

■检索表是由同一类型的数据元素(或记录)组成

的集合。

■由栽合是一种松散型数据结构,数据元素除了

同属于一个集合外再无别的关系,所以检索表是

一种非常灵活的数据结构。

1检索的概念(续)

■对检索表常做的运算和操作有:

-查找某个特定的数据元素是否在检索表中;

-检索某个特定的数据元素的各种属性;

-在检索表中插入一个数据元素;

■从检索表中删去某个数据元素。

■若对查找表只作前两种统称为“检索”的操作,称

此类检索表为静态检索表(staticsearchtable);

■若在检索的过程中同时插入表中不存在的数据元素,

或者从检索表中删除已存在的某个数据元素,称此

类检索表为动态检索表(dynamicsearchtable)。

中检索的概念(续)

■所谓特定的信息,是指关键字值等于给定值的信

息,信息的单位是数据元素或记录。

■关键字(key)是数据元素(或记录)中某个数据

项的值,用它可以标识一个数据元素(或记录)。

显然,在一个记录中的每个数据项都可以作为标识

该记录的关键字。如人事档案记录结构为:

身份证号码|姓名|性别|年龄|工资级别|

它含有五个关键字,其中性别这个关键字标识了

一个职工的性别情况。

,检索的概念(续)

■主关键字(primarykey)是指能惟一标识一个

数据元素(或记录)的关键字。如上述记录中身

份证号码是主关键字,可以惟一标识一条记录;

而姓名、性别、年龄、工资级别不能惟一标识一

条记录,它们都不是主关键字。

■辅关键字(secondarykey)是用以标识若干数

据元素(或记录)的关键字,也称作次关键字或

从关键字。如上述记录中的姓名、性别、年龄、

工资级别都是辅关键字。

1检索的概念(续)

■检索,就是根据给定的某个值,在检索表中查找

一个关键字等于给定值的记录的运算或操作。

■若在检索表中存在这样的记录,则称检索成功,

检索的结果是找到记录的全部信息(或找到记录

在检索表中的位置);

■若检索表中不存在关键字值等于给定值的记录,

则称检索失败,给出在检索表中无要查找的记录

的信息提示,并在动态检索时插入关键字等于给

定值的记录于检索表中。

检索的概念(续)

■在检索表中查找某个数据元表(或记录)的过程,

依赖于这个数据元表(或记录)在查找表中所处

的位置;对检索表的检索方法取决于检索表中数

据元表(或记录)的组织策略。

■如在字典中查找一个英文单词,由于字典是按字母顺

序编排的,所以不需从第一个单词顺序查找,而只是

按待查单词中每个字母在字母表中的位置快速找到该

单词;

■而在数据元素(或记录)之间无任何关系组织起

来的集合中查找,则需要从第一个元素(或记录)

开始依次顺序查找。

中检索的概念(续)

■在计算机中进行检索是对已存入计算机中的数据

进行检索,取决于采用何种数据结构来组织检索

表;往往需要在数据元素(或记录)之间人为地

加上一些关系,即用非集合结构如数组、文件、

二叉树、散列表等结构来组织检索表,以便按某

种规律来进行检索。

■依数据组织方式不同,检索分为线性表检索、树

表检索和散列表检索等。

■衡量一个检索算法的优劣,主要依据在检索过程

中给定值和关键字的比较操作次数。为此,我们

引入平均检索长度的概念。

1平均检索长度

■检索算法的平均检索长度(averagesearch

length),即在检索过程中用给定值和关键字进

行比较的平均比较次数,

■或者说是为找到具有给定值关键字的记录所需

要的比较次数的平均值。

■它是为确定记录在检索表中的位置,需要和给

定值进行比较的关键字个数的期望值。

中平均检索长度(续)

■对于含有n个记录的检索表,检索成功时的平均

检索长度为

ASL=£PG

2-1

■其中,Pj为检索第i个记录的概率,且,名"I;

一般在不特殊说明的情况下均认为是等银率,即

检索每个记录的概率相等,片=舄=…=月=1O

n

■3为找到第i个记录需要和给定值比较的关键字的

个数,它随检索方法的不同而不同。

[第7章检索及基本算法

7.1检索的概念

7.2线性表的检索

7.3树表的检索

7.4哈希检索

中线性表的检索

■在检索表的数据组织方式中,线性表是最基本的,

也是最常用的一种组织方式。本节主要讨论在顺序

存储结构实现的线性表上的检索算法,其类型定义

描述为

typedefstruct

{keytypekey;/*关键字类型*/

elemtypeother;/*其它域*/

}sqlist;

sqlistR[n+1];/*顺序表*/

■本节介绍的线性表检索方法有顺序检索、二分法检

索、黄金点检索、精算点检索和分块检索等。

7.2线性表的检索

7.2.1顺序检索

7.2.2二分法检索

7.2.3黄金分割点检索

7.2.4精算点检索

7.2.5分块检索

,顺序检索

■顺序检索(sequentialsearch)是一种最简单的基

本检索方法。

■其基本思路为:

■从表的一端开始,用给定值逐个与表中各记录的关键字

值比较。

■若找至i某个关键字值等于给定值的记录,则检索成功,

并给出该记录在表中的位置;

■若检索完整个表仍未找到关键字值等于给定值的记录,

则检索失败,并给出失败信息。

■顺序检索方法既适用于线性表的顺序存储结构,

也适用于线性表的链式存储结构。

中顺序检索举例

■以顺序存储结构为例,设数据元素存放在数组中

下标从1到n的记录中,。号记录位置留作监视哨,

从下标为n的一端开始向另一端检索,顺序检索算

法可描述如下:

intseqsearch(sqlistR[],keytypek)

(inti=n;

R[0].key=k;/*设置R[0]为监视哨*/

while(R[i].key!=k)

i一;

returni;/*返回检索结果i*/

,顺序检索举例(续)

■算法中设置监视哨R[0],可以使得在检索成功和

检索失败时的处理一致,在检索失败时也能在监视

哨位置找到关键字值为k的记录,可省去在while循

环中的位置越界检查(i>=l)。

■若从R[0]处向后顺序检索,监视哨可设置在R[n]处。

■算法执行之后,非0的函数值表示待查找记录在数

组中的位置(下标);若函数值为0说明检索表中

没有要查找的记录。

■顺序检索(续)

■对于具有n个记录的检索表,若待查找记录在R[n]

处,需要和给定值k比较一次,即C:l;

■若待查找记录在R[n-1]处,需要和给定值k比较两

次,即CnJ=2;

■一般地,若待查找记录在R[i]处,需和给定值k比

较n-i+1次,即Ci=n-i+1。

■因此,在等概率的情况下顺序检索的平均检索长

度为

人已、融+1

ASL=工名G=工一5T+1)=__

M餐"2

,顺序检索(续)

■在检索成功时顺序检索的平均比较次数约为表长

的一半。

■在检索失败时,顺序检索需要进行n+1次的比较。

■当n很大时,平均检索长度也很大,检索效率较低,

这是顺序检索的主要缺点。

■但由于顺序检索对表的存储结构和元素存放次序

没有要求,且算法简单,在许多实际应用中常被

采用。

7.2线性表的检索

7.2.1顺序检索

7.2.2二分法检索

7.2.3黄金分割点检索

7.2.4精算点检索

7.2.5分块检索

二分法检索

■上分法检索(binarysearch),也称作折半检索,

它是一种效率较高的检索方法。它要求检索表是用

顺序存储结构表示,且数据元素的存放要按关键字

值有序排列。

■二分法检索的基本思想是:

■在有序表中先取中间位置作为比较对象,若给定值与中

间记录的关键字值相等,则检索成功;

■若给定值小于中间记录的关键值则在表的左半区查找,

■若给定值大于中间记录的关键字值则在表的右半区查找。

■就这样经过一次的比较缩小一半的检索区间,在每一个

检索区间都是选取中间位置作为比较对象,不断地重复这

样的检索过程直到检索成功,或者检索区间已无记录时检

索失败Q一―一一——

1二分法检索举例

■例如:已知一个含15个记录的有序表,其关键字序

列如下:

(071014182123252931353842464952)

■现在要检索给定值k为19、46和H的记录,其检索

过程如下:

■用low和high分别表示检索区间的下界和上界;

■用mid指示中间位置,即mid=(low+high)/2;

■检索开始时low=1,high=n;即检索区间为[1,

n]o

中二分法检索举例——检索k=18

■检索k=18的过程:

071014182123252931353842464952

TTT

low=1mid=8high=15

■检索开始时,low=l,high=15,mid=(l+15)/2=8O

由于k=18<29=R[8].key,所以应在左半区继续检索。

此时,high=mid-l=8-l=7,mid=(1+7)/2=4,即:

071014182123252931353842464952

TTT

low=lmid=4high=7

■由于k=18=R[4].key,此时检索18成功。

中二分法检索举例——检索k=46

■检索46的过程:

0T7101418212325T29313538424649T52

low=1mid=8high=15

■由于k=46〉29二R[8].key,所以应在右半区继续检索;

此时low=mid+l=8+l=9,mid=(9+15)/2=12,即:

071014182123252931353842464952

TTT

low=9mid=12high=15

■由于k=46>42=R[14].key,所以应在当前区间的右

半区继续检索;

,二分法检索举例一检索k=46(续)

■ikHtlow=12+l=13,mid=(13+15)/2=14,即:

071014182123252931353842464952

TTT

low=13mid=14high=15

■由于k=46〈49=R[14].key,所以应在当前区间的左半

区继续检索;此时high=mid-1=14-1=13,

mid=(13+13)/2=13,即:

071014182123252931353842464952

T

low=13

mid=13

high=13

■由于k=46=R[13].key,此时检索46成功。

中二分法检索举例——检索k=l1

071014182123252931353842464952

TTT

low=lmid=8high=15

■由于k=H<29=R[8].key,应在左半区继续检索;此

时high=mid-l=8-l=7,mid=(1+7)/2=4,即:

071014182123252931353842464952

TTT

low=lmid=4high=7

■由于k二H〈18=R[4].key,应在当前区间的左半区继

续检索;

1二分法检索举例一检索1<=11(续)

■It匕时high二4T二3,mid=(i+3)/2=2,即:

071014182123252931353842464952

TTT

low=1mid=2high=3

■由于k=ll>10=R[2].key,应在当前区间的右半区继

续检索;此时low=2+1=3,mid=(3+3)/2=3,即:

071014182123252931353842464952

T

low=3

mid=3

high=3

■由于k二H〈14=R[3].key,应在当前区间的左半区继

续检索;此时high二midT=3-l=2<3=low,左半区已

”士工老/木—¥间工〕松为二HjH

中二分法检索过程可用C语言描述

・L分法检索过程可用c语言描述为如下算法:

intbinarys㊀arch(sglistR[],k㊀ytyp㊀k)

{intlow,mid,high;

low=l;high=n;

whil㊀(low〈=high)

{mid=(low+high)/2;

if(k==R[mid].k㊀y)

returnmid;

㊀Is㊀

if(k<R[mid].k㊀y)

high=mid-l;

㊀Is㊀

low=mid+l;

)

return0;}

『二分法检索过程分析

」为了分析二分法检索算法的性能,我们先注意前述15个

元素的检索表的检索过程:为了找到第8个记录仅需一次比

较;为了找到第4,12个记录需二次比较;为了找到第2,6,

10,14个记录需要三次比较;为了找到第1,3,5,7,9,

11,13,15个记录需四次比较。这个检索过程可用下图所

示的二叉树来描述:

检索成功时检索过程示意及检索k=35的过程

1二分法检索过程分析(续)

■树中每个结点表示一个记录,结点中的数值为该

记录在检索表中的位置,找到检索表中的任一记录

的过程,是走了一条从二叉树的根结点到该记录相

应结点的一条路径;

■和给定值比较的关键字个数,恰为该结点在树上

的层次数,图中的虚线示意了检索k=35的过程,

走的是从根到结点⑩的路径,比较次数为结点⑩所

在层次数3。

1二分法检索算法分析

■因此,二分法检索在检索成功时给定值与关键字

的比较次数不超过二叉树的深度。

■虽然描述二分法检索过程的二叉树不一定是完全

二叉树,但它的叶子结点所在层次差别最多为1,

所以在具有n个结点时二叉树的深度和n个结点的

完全二叉树的深度相同。

■具有n个结点的完至二叉树深度为降/」+1,所以

二分法检索在检索成功时的比较次数至多为

]1啊连1+1次。

,二分法检索过程分析(续)

■如果在如前例图的二叉树中所有结点的空指针域

上加一个指向方形结点的指针,如下图所示,这些

方形结点是检索失败时的情况描述。

1二分法检索过程分析(续)

■二分法检索在检索失败时走了一条从二叉树根结点

到方形结点的路径和给定值的比较次数等于路径上

结占(不含方形结占)的个数。

■卤*虚线给出亍母藁k=11检索失败时从根到方形

结点的一路径。因此检索失败时和给定值的比较次

数也是最多不超过[log/」+l次。

1二分法检索过程分析(续)

■为了方便讨论平均检索长度,假定检索过程是深度

为h的满二叉树,即第k层上有2-个结点,检索第k

层上结点需k次比较,在等概率的情况下,二分法检

索在检索成功时的平均检索长度

右He;

=1工上12(«+1)-1

■当n较大时,例如n>100,则可有如下近似结果:

ASL、log?伽+1)—1

,二分法检索过程分析(续)_

■由此可见,二分法检索的效率比顺序检索高得多,

如n=127时,顺序检索ASL=64而二分法则为ASL

=6o

■二分法检索只适用于检索表为顺序存储结构之下

的有序表,即这种较高的检索效率是以对检索表预

先按关键字值大小排序为代价的,所以二分法检索

适合于一旦建立很少变动而又需要经常检索的检索

7.2线性表的检索

7.2.1顺序检索

7.2.2二分法检索

7.2.3黄金分割点检索

7.2.4精算点检索

7.2.5分块检索

1黄金分割点检索

■黄金分割点检索(gold-partitionsearch),简称黄

金点检索。它是利用我国著名数学家华罗庚院士当

年推广优选法时介绍的黄金分割点的概念,即利用

黄金分割数0.618把检索区间分为两个不等的区间。

■每次用给定值与黄金点上的记录的关键字比较,

若相等检索成功,若给定值小于黄金点关键字值,

继续在黄金点之前的区间检索;若给定值大于黄金

点关键字值,继续在黄金点之后的区间检索。

■通过黄金点逐次缩小检索区间,直到检索成功,

或区间已无记录检索失败时止。

1黄金分割点检索举例

■I列如,仍以前面的15个记录为例,检索k=46的黄金分割点

检索过程为:

071014182123252931353842464952

ttt

low=lmid=9high=15

■开始时low=l,high=15,mid=low+0.618*(high-low+1)-

1=1+0.618*(15-1+1)-1=9.32^9o给定值k=46>31=R[9].key,在

黄金点之后的区间继续检索。此时low=9+l=10,

mid=10+0.618*(15-10+l)-l=12.708~13o即:

071014182123252931353842464952

fft

low二10mid=13high=15

■由于k=46=R[13].key检索成功。一个用二分法检索需4次比

较的工作,黄金分割点检索只需两次比较就完成了。

,黄金分割点检索算法描述

mtgoldpartsearch(sqlistR[],keytypek)

{intlow,mid,high;

low=1;high=n;

while(low〈二high)/*逐次缩小区间检索*/

{mid=low+0.618*(highTow+1)T+0.5;

if(k==R[mid].key)

returnmid;

else

if(k<R[mid].key)

high=mid-l;/*修改区间上界*/

else

low=mid+l;/*修改区间下界*/

return0;}

黄金分割点检索(续)

■【亥算法的时间性能与二分法相比,在平均性能上优于二分法,

但仍然是;在最坏情况下,每次比较之后都在较大的区间内

继续检索,比二分法差;在最好情况下,每次比较之后都在

小区间内继续检索,比二分法好。

-所谓黄金分割点,就是刘川Fibonacci数列对检索表分割

得到的一系列位置。Fibonacci数歹U的定义为:

F(o)=i

<F(l)=1

尸5)=尸5一1)+95-2)总22

n0123456789101112131415

F(n)1123581321345589144233377610987

F(n)JF(n+l)10.50.6670.60.6250.6150.6190.6170.6180.6180.6180.6180.6180.6180.6180.618

Fibonacci数列及其相邻项的比值

1黄金分割点检索(续)

■注意观察“Fibonacci数列及其相邻项的比值”表中给出的

F(n)/F(n+1)的值,从n=6之后基本上稳定在0.618处。

■因此,我们可以对长度为F(n)的检索表,第一次用F(n-1)

处记录的关键字同给定值比较;由F(n-l)分割的两个区间的

长度分别为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分块检索

1精算点检索

■对于有序的检索表,如果记录的关键字值不仅有

序,而且分布均匀或比较均匀,我们能不能很快

地完成关键字值等于给定值记录的检索任务呢?

回答是肯定的,下面将要介绍的精算点检索就可

以解决这个问题。

■所谓精算点检索(precisecomputingsearch),

也称作插值检索。它是利用检索区间有序关键字

值范围和给定值的大小比例关系估算检索位置的

一种检索方法。

,精算点检索(续)

售关键字值分布均匀时应满足下式:

mid-low_k-key

high-lowK[high]k&y-E[low].key

■其中k为给定值,mid为估算位置,low和high分别

为检索区间下界和上界位置,经整理可得估算公式

为:

.,,k-B[loy^].key...,、

mia=low+--------------------------------(mgk-low)

B[high\,key-P[lo^].key

■当给定值k等于R[mid].key则检索成功;否则若

k<R[mid].key则在mid之前检索,若k>R[mid].key则

在mid之后检索。

1精算点检索(续)

■在关键字值均匀分布时,如呈等差数列时一次比

较便可检索成功;在关键字值分布比较均匀时,

若一次比较不能找到也会在mid位置附近,这两种

情况的检索长度与检索表的大小n无关,所以称之

为精算点检索。

■如果^^^直分布不均匀,可缩小检索区间继续

用前面的估算公式确定检索点检索,其检索性能

也优于黄金分割点检索和二分法检索。

,精算点检索举例

■例如,对于前述的15个记录的检索表,检索k=14

的记录,1OW=1,high=15,^=14-li2Z(15-l)=3.177^3,

52—7

R[3].key=14等于给定值,一次比较检索成功;又如

检索k=29时,加d=1+巴二(15-1)=7844a8,—*次比较

52-7

R[n].key=29等于给定值检索成功;再如检索k=46

时,流出=i+竺二2(15-i)=i3.133^13,―*次比较R[13].key=46

52-7■

等于给定值检索成功;等等。

1精算点检索举例(续)

■既然在关键字值分布较均匀时,即使一次比较不能

检索成功也会在mid位置附近,在算法设计时就只需

一次计算mid的值。

■若k=R[mid].key,则一次比较检索成功;

■若k〈R[mid].key,则可由mid前一个记录开始向前

顺序检索,直到检索成功或某个记录的关键字值小

于给定值k时检索失败;

■若k>R[mid].key,则可由mid后一个记录开始向后

顺序检索,直到检索成功或某个记录的关键字值大

于给定值k时检索失败。

1精算点检索算法描述

■k种与顺序检索相结合的精算点检索算法「描述如下:

intprecisesearch(sqlistR[],keytypek)

{intlow,mid,high;

low=l;high=n;

mid=low+(k-R[low].key)*(high-low)/

(R[high].key-R[low].key)+0.5;

if(k二二R[mid].key)

returnmid;

else

if(k<R[mid].key)

{mid--;

while(R[mid].key>k)

mid——;

中精算点检索算法描述(续)

if(R[mid].key=二k)

returnmid;/*检索成功返回位置*/

else

return0;/*检索失败返回0*/

)

else

{mid++;/*若给定值大于mid时在mid后检索*/

while(R[mid].key<k)/*向后顺序检索*/

mid++;

if(R[mid].key=二k)

returnmid;/*检索成功返回位置*/

else

return0;/*检索失败返回0*/

中精算点检索算法分析

■该算法中的两个当型循环,在关键字值分布较均

匀的情况下,检索长度与检索表的长度n无关,平

均检索长度趋近于某个常数;

■在关键字值分布不均匀的情况下,检索长度在最

坏的情况下也不会超过二分法检索和黄金分割点

检索,

■第支点检索是平均性能最好的检索方法,对于检

索表较大和分布较均匀时,使用精算点检索特别

合适。

7.2线性表的检索

7.2.1顺序检索

7.2.2二分法检索

7.2.3黄金分割点检索

7.2.4精算点检索

7.2.5分块检索

1精算点检索算法分析

■分块检索(blockingsearch),又称作索引检索,

它是顺序检索的一种改进方法,其效率介于顺序检

索和二分法检索之间。

■分块检索不要求检索表中所有记录关键值有序排

歹U,但要求把检索表分成若干块之后各块之间按关

键字值大小有序。

■即分块检索要求检索表的特点是:块间有序,块内无序。

■所谓块间有序是指块间升序或块间降序。

■在块间升序时,每一块中所有记录的关键字值均大于和

该块相邻的前一块中最大的关键字值;

■在块间降序时,每一块中所有记录的关键字值均小于和

该块相邻的前一块中最小的关键字值。

r精算点检索算法分析(续)

「在分块检索中,除检索表本身之外,还需要建立一张索引

表。如下图给出了一张块间升序的检索表的索引表,每个块

在索引表中有一个索引项,每个索引项中包含有该块中最大

的关键字值和该块第一个记录在检索表中的位置。

■本例中检索表分为三块,各块中最大关键字值依次为22、

48和86,各块中第一个记录在检索表中的位置依次为1、7和

13;第二块中的最小关键字值24大于第一块中的最大关键字

值22,第三块中的最小关键字值49大于第二块中的最大关键

123456789101112131415161718

精算点检索算法分析(续)

T■年图中给出了一张块间降序的检索表的索引表,每个块在

索引表中也是一个索引项,但索引项中包含的是块中最小的

关键字值和该块第一个记录在检索表中的位置。

■该例中检索表分为四块,各块中最小关键字值依次为47、

32、22和9,各块中第一个记录在检索表中的位置依次是1、

6、11和16;第二块中的最大关键字值45小于第一块中最小

的关键字值47,第三块中的最大关键字值31小于第二块中的

最小关键字值32,第四块中的最大关键字值20小于第三块中

1234567891011121314151617181920

中精算点检索的基本思想

;分块检索的基本思想是:

■首先依据给定值在索引表中检索,以确定待查找

记录所属的块;

■由于索引表是有序表,所以可以用二分法检索,

也可以用顺序检索或其它检索方法进行。

■然后在确定的块内检索关键字值等于给定值的记

录,由于块内记录无序排列,所以只能用顺序检

索方法进行。

1精算点检索举例

■例如,要在前例“块间升序的检索表及其索引表示

例"中检索k=38的记录:

■先将k依次和索引表中各个最大关键字进行比较,由于

22<k<48,所以k=38的记录若存在必在第二个块中;

■然后从第二个块的起始地址开始顺序检索,直到

R[10].key=k时检索成功。

■再如检索k=76的记录:

■将k和索引表中各个最大关键字值比较,由于48<k<86,

故k=76的记录若存在必在第三个块中;

■从第三个块的起始地址开始顺序检索,直到和块中最后

一个记录的关键字R[18].key比较都不等于k时检索失败。

1精算点检索算法分析

■由分块检索的思想可知,分块检索算法是对索引表

的二分法检索或顺序检索和对块中检索的顺序检索

这两部分检索算法的简单合成。

■由于分块检索是由索引表检索和块内检索两部分合

成,所以分块检索的平均检索长度为:

ASL=Lb^Lw

■其中:L是为确定所在块对索引表的平均检索长度,

人是在块内检索记录的平均检索长度。

1精算点检索算法分析(续)

■二般情况下,为了分块检索,把长度为n的检索表

均匀分成b块,每块含s个记录,即力=,//。再假定

对检索表中各记录的检索是等概率的,即块检索概

率为1/b,块中记录的检索概率为1/s。

■若顺序检索确定所在的块,则分块检索的平均检索

长度为:

1b15

ASL-Lb+Lw=-^7+一£?

U,=1Si=l

=^1+£11=1

222

=—(—+5)+1

2s

1精算点检索算法分析(续)

■由上式可知,ASL不仅与检索表的长度n有关,而且和每一

块中的记录个数s有关。在给定n的前提下s是可以选择的;

当选取.赤时,ASL具有最小值6+1o即/以=6+1。这个

值比顺序检索有了很大的改进,但远不及二分法检索。例如

当n=1024时,赤=32,分块检索、顺序检索和二分法检索的

平均检索长度分别如下:

分块检索:4SZ=-(-+5)+1=1(^1+32)+1=33

2s232

顺序检索:XSZ=-(z?+l)=-(1024+1)=512.5

二分法检索rASL=log2(H+1)-1=log2(1024+1)—1=9

1精算点检索算法分析(续)

■若用二分法检索确定所在的块,则分块检索的平均检索长

度为:

C+1

ASL=Lb+LW=log2(Z)+l)-l+—

=log2(-+l)+^

s2

■其平均检索长度ASL仍是介于二分法检索和顺序检索之间。

■如当n=1024时,

s11024小32-1

ASL=log2+1)+-y-=5+15.5=20.5

■最后对分块检索需要说明的是,为了提高检索效率,要尽

可能把块划分均匀;在实际应用中,要依据检索表的具体

情况来划分块的大小,不一定要做到块的大小相同,只要

满足块间直序即也。、..—一

[第7章检索及基本算法

7.1检索的概念

7.2线性表的检索

7.3树表的检索

7.4哈希检索

,树表的检索

■在上一节介绍的线性表的检索,主要讨论了检索

表为顺序表和有序表的几种检索方法;由于顺序存

储结构的特点,不适用于对检索表中的记录多做插

入和删除操作,所以统称作静态检索。

■本节讨论的树表检索属于动态检索,其特点是检

索表本身是在检索过程中动态生成的;即若检索表

中存在关键字值等于给定值k的记录,则检索成功

返回,否则在检索表中插入关键字值等于k的记录。

7.3树表的检索

7.3.1二叉检索树

7.3.2二叉检索树的平衡性调整

7.3.3B树和B+树

■■1.二叉检索树的概念及检索过程

■二叉检索树(binarysearchtree),又称作二

又排序树(binarysorttree);它或者是一棵空

树,或者是具有下列性质的二叉树:

■若左子树不空,则左子树上所有结点的值均小

于根结点的值;

■若右子树不空,右子树上所有结点的值均大于

根结点的值;

■其左、右子树也都是二叉检索树。

1二叉检索树举例

■如下图给出的就是一棵二叉检索树,它满足二叉

检索树的定义;对该二叉检索树中序遍历得到结

点序列20、30、40、45、50、55、70、75、80,

是一个结点的有序序列。

二叉检索树示例

,二叉检索树的检索过程

■如果把检索表中各记录按关键字值大小组织为上

述的二叉检索树,则检索关键字值等于给定值k的

记录的过程为:

⑴若二叉检索树为空,检索失败,返回特定值NULL;

⑵若二叉检索树非空,用给定值k与根结点的关键字值

比较:

①相等时,检索成功,返回指向当前根结点的指针;

②k小时,继续在根的左子树中检索,即转⑴;

③k大时,继续在根的右子树中检索,即转⑴。

1二叉检索树的检索过程举例

■例如,在右图所示二叉检索树中检索k=80

的记录,先用80和根先比较,80的0则在右

子树中继续检索;再用80和右子树的根70比

较,80>70则继续在当前根结点70的右子树

中检索;当再次和新的当前根结点比较时二

者相等检索成功,返回指向当前根结点的指

针。

■又如检索k二15的记录时,由于15小于根结

点50,在其左子树继续检索;15又小于左子二叉检索树示例

树的根结点40,继续在当前根结点40的左子

树中检索;15也小于当前根结点40的左子树

的根结点20,当在20的左子树中继续检索时

发现20的左子树为空,检索失败返回NULL。

,二叉检索树的二叉链表类型_

-设二叉检索树以如下描述的二叉链表作为存储结

构:

typedefstructnode

{keytypekey;/*关键字域*/

elemtypeother;/*其它数据域*/

structnode*lchild,*rchild;

/*左右孩子指针域*/

}bstnode;/*定义结点类型bstnode*/

typedefbstnode^bstlist;

/*定义二叉检索树表类型bstlist*/

1二叉检索树的检索算法描述

;二叉检索树的检索算法可描述如下:

bstlistbstsearch(bstlistt,keytypek)

{bstlistp;

P二t;

if((p二二NULL)||(p->key==k))

returnp;

else

if(p->key<k)

returnbstsearch(p->rchild,k);

else

returnbstsearch(p->lchild,k);

}/*bstsearchend*/

2.二叉检索树的构造过程和插入操作

于一组关键字无序的记录,构造其相应的二叉检索

树的方法是:从一棵空的二叉检索树开始,每当读入

一个记录就生成一个结点,然后按关键字值的大小插

入到当前的二叉检索树之中;当所有记录的结点都已

插入二叉检索树中时便构造完毕。

■虽然,插入操作是构造二叉检索树的关键操作。要保

证在一棵二叉检索树中插入一个结点之后,仍然满足

二叉检索树的定义。其插入过程为:

■若二叉检索树为空,则插入结点作为新的根结点;

■若二叉检索树非空,则在非空的二叉检索树中检索插入结

点;如果检索成功就不必插入,否则插入结点作为新的叶结

点,并成为检索路径上最后一个结点的左孩子或右孩子。

T二叉检索树的构造过程和插入操作(续)

■力了实现这一插入过程,在二叉检索树非空时需要知

道检索路径上的最后一个结点位置,才能够准确地把

插入结点作为左孩子或右孩子插入二叉检索树中;为

此;需要在检索过程中设一指针变量记下当前结点的

前趋(即双亲)结点位置。

■插入算法的形式化描述如下:

bstlistinsertbst(bstlistt,keytypek)

(bstlists,p,q;

if(t==NULLl)

{p二(bstlist)malloc(sigeof(bstnode));

p->key=k;p->IchiId二NULL;p->rchiId二NULL;

p->other=data;

returno:}

二叉检索树的构造过程和插入操作(续)

while(p!=NULL)

{q=p;

if(p->key==k)/*检索成功不必插入*/

returnt;/*返回原二叉检索树*/

else

if(p->key<k)

p:=p->rchild;

else

p=p->lchild;

p二(bstlist)malloc(sizeof(bstnode));

,二叉检索树的构造过程和插入操作(续)

p->key=k;

p->IchiId二NULL;

p->rchild=NULL;

p->other=data;

if(k>q->key)

q->rchild=p;

else

q->lchild=p;

returnt;

1二叉检索(排序)树构造过程举例二

■从空树出发经过一系列的检索插入操作之后,就可生成一

棵二叉检索树。一个无序序列可以通过构造一棵二叉检索树

而变成一个有序序列(即中序遍历次序序列),构造的过程

就是对无序序列进行排序的过程,所以又称作二叉排序树。

■设关键字序列为(45,22,57,18,29,92),生成二叉

检索树(即二叉排序树)的过程如下图所示。

0®

(a)空树(b)插入45©插入22

QI3.二叉树检索树的删除操作

■在二叉检索树中删除一个结点,相当于在检索表中

删除一个记录,不能把以待删除结点为根结点的子树

全部删去,并且要保证删除某个结点后的二叉树仍然

是一棵二叉检索树。下面,我们分三种情况讨论如何

在二叉检索树中删除一个结点。

(1)待删除结点是度为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;

1二叉树检索树的删除操作(续)

⑶待删除结点是度为2的双枝结点

即待删除结点既有左子树又有右子树的情况,如下图所

示,为了保持二叉检索树的特性,通常有如下四种做法。

待删除结点为双枝结点示例

1二叉树检索树的删除操作—方法一

■方法一:找出待删除结点*P的中序前趋结点*q,把*q的关键

字域和数据域的值赋给*P的相应域,即:

p-〉k;y=q-〉k,y;p->oth㊀r=q->oth㊀r;

■然后删除其中序前趋结点*q,由于*P的中序前趋*q是*P左子

树上的最右下结点,所以*q必是叶子结点或单左枝结点,如

下图所示;其删除方法见⑴和⑵。

q

(a)*q是叶子结点(b)*q是单左枝结点

,二叉树检索树的删除操作—方法二

■方法二:找出待删除结点*p的中序后继结点*q,把*q的关键

字域和数据域的值赋给*P的相应域,即:

p->k^y=q->k^y;p->oth㊀r=q->oth㊀r;

■然后删除其中序后继结点*q。由于*P的中序后继*q是*P右子

树上的最左下结点,所以*q必是叶子结点或单右枝结点,如

下图所示;其删除方法见⑴和⑵。

(b)*q是单右枝结点

1二叉树检索树的删除操作—方法三

■方法三:将待删除结点*p的右子树链接到它的中

序前趋结点(即左子树上的最右下结点)*q的右孩

子域上,然后把它的左子树直接链接到其双亲结点

的左(或右)孩子域上。即:

q->rchild=p->rchild;

f->lchild(或f-〉rchild)=p->lchild;

1二叉树检索树的删除操作—方法四

■方法四:将删除结点*P的左子树链接到它的中序

后继(即右子树上的最左下结点)*口的左孩子域上,

然后把它的右子树直接链接到其双亲结点*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;

,二叉检索树的删除算法描述

■、面我们给出采用方法四删除双枝结点时的二叉检

索树的删除算法描述如下:

bstlistdeletebst(bstlistt,keytypek)

(bstlistp,q,r,f;

P二t;

f=NULL;

while((p!=NULL)&&(k!=p->key))

{f=P;

if(k<p->key)

p=p->lchild;

else

p=p->rchild;

二叉检索树的删除算法描述(续)

if(p二二NULL)

break;/*检索失败时不用删除中断执行*/

if((p->IchiId二二NULL)||(p->rchild==NULL))

q=P;/*待删除的*P为叶子结点或单枝结点时*/

else

{q=p->rchild;

while(q->lchiId!=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;

returnt;/*返回删除操作后的二叉检索树*/

}/*deletebstend*/

中4.二叉检索树的检索性能分析

■在二叉检索树上检索关键字值等于给定值k的记录,

正好是走了一条从根结点到关键字值为k的结点的路

径,和给定值k的比较次数为路径长度加1(或结点所

在层次数),和二分法检索类似,其比较次数不超过

树的深度o

■然而,年二分法检索一个长度为n的检索表其检索过

程的二叉树表示是惟一的,而含有n个结点的二叉检

索树却不惟一。

1二叉检索树的检索性能分析举例_

■例如,如下图给出了结点值都相同的两棵二叉检索

树,由于构造时的关键字序列不同,前者深度为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。

⑥深度为3的二叉检索树

(b)深度为7的二叉检索树

,二叉检索树的检索性能分析(续)

■因此,含有n个结点的二叉检索树的平均检索长度

和二叉检索树的形态有关,当先后插入的关键字按值

有序时,构造的二叉检索树蜕变为单枝树;

■升序时为单右枝二叉树,降序时为单左枝二叉树;

■树的深度为n,平均检索长度为(n+l)/2(和顺序检

索相同),这是最差的情况。最好的情况是二叉检索

树的形态和二分法检索过程得到的树相同,树的高度

和完全二叉树的高度相同,其平均检索长度为昵㈤。

,二叉检索树的检索性能分析(续)

■现在我们考虑在一般情况下二叉检索树的平均检索

长度,假设在含有n个结点的二叉树中,有i个结点关

键字值小于根结点的关键字值,n-i-1个结点关键字值

大于根结点的关键字值。

■在等概率检索的情况下平均检索长度为:

目(招好=-[1+/*(p(>+1)+f—1)+1)]

n

=1+—+-1)*p(n-i-1)]

n'

■其中,p⑴为含有i个结点日勺二义检索何的平均检索长度;

p⑴+1为检索左子树中每个结点所用比较次数的平均值,

p(n-i-l)+l为检索右子树中每个结点所用比较次数的平均值。

〒二叉检索树的检索性能分析(续)_

■由于根结点的左子树中有0个,1个,…,n-1个结点

的情况是等概率的,对上式取平均值得:

]»-1

二一£。

%7=0

]M-l

=1+-T£["(i)+("jT)*P("jT)]

〃z=0

21

=1+

1

nz=0

■用数学归纳法可以证明,以用<l+41og2"即二叉检

索树的平均长度为l+410g/o

7.3树表的检索

7.3.1二叉检索树

7.3.2二叉检索树的平衡性调整

7.3.3B树和B+树

,平衡因子

■平衡因子(balancefactor)

■二叉树上任一结点的平衡因子,定义为该结点的左子树深

度减去右子树深度的差。

■如下图中给出了一些二叉树,其结点上所示数值为

该结点的平衡因子值。

1平衡二叉树

■平衡二叉树(balancebinarytree)

■如果一棵二叉树中所有结点的平衡因子的绝对值不超过L

则称该二叉树为平衡二叉树;平衡二叉树也称作AVL树。

■显然,AVL树要么是一棵空树,要么其左右子树深

度不超过1且都是AVL树;只要二叉树上有一个结点

的平衡因子的绝对值大于1,该二叉树就是不平衡的。

如前例图中,(a)和(b)都是平衡二叉树(即AVL树),

而(c)和(d)都不是平衡二叉树(即非AVL树)。

T平衡二叉树(续)

■[于AVL树具有良好的形态,其左右子树的深度差不

超过1;对于给定的结点数目n,AVL树的平均深度接

近于完全二叉树的深度做㈤+1;

■所以我们希望由任何初始序列构成的二叉检索树都

是AVL树,使得其平均检索长度接近于现同+1。

■如何使构造的二叉树成为AVL树呢?Adelson-

Velskii和Landis提供了一个动态地保持二叉检索树

平衡性的方法;

■其基本思想是在构造二叉检索树的过程中,每当插入一个

结点后都去检查是否由于该结点的插入而破坏了二叉检索

树的平衡性;若出现绝对值超过1的平衡因子,则需要在保

持二叉检索树特性的前提下通过调整使之达到新的平衡。

平衡二叉树(续)

■在一般情况下,设在插入结点的过程中使二叉检索

树失去平衡的最小子树的根结点为a,即a为离插入

结点最近且平衡因子绝对值超过1的祖先结点;

■因插入结点的位置不同而失去平衡需要调整的规律

可归纳为如下四种情况:

■LL型平衡旋转(右单旋型)

■RR型平衡旋转(左单旋型)

■LR型平衡旋转(先左后右双旋型)

■RL型平衡旋转(先右后左双旋型)

5LLL型平衡旋转(右单旋型)

■这种失衡是由于在结点a的左孩子b的左子树上插入结点,

使结点a的平衡因子由1增至2而造成的。

■其调整策略是以a的左孩子b为轴心顺时针旋转(即向右旋

转)

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论