数据结构教程（第3版）四ppt课件

1、数据构造教程第数据构造教程第3版四版四第第1010章章 查找查找10.1 10.1 查找的根本概念查找的根本概念本章小结本章小结10.2 10.2 线性表的查找线性表的查找10.3 10.3 树表的查找树表的查找10.4 10.4 哈希表查找哈希表查找10.1 10.1 查找的根本概念查找的根本概念 被查找的对象是由一组记录组成的表或文被查找的对象是由一组记录组成的表或文件件, ,而每个记录那么由假设干个数据项组成而每个记录那么由假设干个数据项组成, ,并并假设每个记录都有一个能独一标识该记录的关假设每个记录都有一个能独一标识该记录的关键字。键字。 在这种条件下在这种条件下, ,查找的定义是：

2、给定一个值查找的定义是：给定一个值k,k,在含有在含有n n个记录的表中找出关键字等于个记录的表中找出关键字等于k k的记的记录。假设找到录。假设找到, ,那么查找胜利那么查找胜利, ,前往该记录的信前往该记录的信息或该记录在表中的位置；否那么查找失败息或该记录在表中的位置；否那么查找失败, ,前往相关的指示信息。前往相关的指示信息。 采用何种查找方法采用何种查找方法? (1) 运用哪种数据构造来表示运用哪种数据构造来表示“表表,即表中记录即表中记录是按何种方式组织的。是按何种方式组织的。 (2) 表中关键字的次序。是对无序集合查找还表中关键字的次序。是对无序集合查找还是对有序集合查找是对有序

3、集合查找? 假设在查找的同时对表做修正运算假设在查找的同时对表做修正运算(如插入如插入和删除和删除),那么相应的表称之为动态查找表那么相应的表称之为动态查找表,否那么否那么称之为静态查找表。称之为静态查找表。 由于查找运算的主要运算是关键字的比较由于查找运算的主要运算是关键字的比较,所以通所以通常把查找过程中对关键字需求执行的平均比较次数常把查找过程中对关键字需求执行的平均比较次数(也也称为平均查找长度称为平均查找长度)作为衡量一个查找算法效率优劣的作为衡量一个查找算法效率优劣的规范。平均查找长度规范。平均查找长度ASL(Average Search Length)定义定义为：为： n1iii

4、cpASL 其中其中,n是查找表中记录的个数。是查找表中记录的个数。pi是查找第是查找第i个记个记录的概率录的概率,普通地普通地,均以为每个记录的查找概率相等均以为每个记录的查找概率相等,即即pi=1/n(1in),ci是找到第是找到第i个记录所需进展的比较次个记录所需进展的比较次数。数。 10.2 10.2 线性表的查找线性表的查找 在表的组织方式中在表的组织方式中, ,线性表是最简单的一线性表是最简单的一种。三种在线性表上进展查找的方法：种。三种在线性表上进展查找的方法： (1) (1) 顺序查找顺序查找 (2) (2) 二分查找二分查找 (3) (3) 分块查找。分块查找。 由于不思索在

5、查找的同时对表做修正由于不思索在查找的同时对表做修正, ,故故上述三种查找操作都是在静态查找表上实现的。上述三种查找操作都是在静态查找表上实现的。 查找与数据的存储构造有关查找与数据的存储构造有关,线性表有顺序和链式线性表有顺序和链式两种存储构造。本节只引见以顺序表作为存储构造时两种存储构造。本节只引见以顺序表作为存储构造时实现的顺序查找算法。定义被查找的顺序表类型定义实现的顺序查找算法。定义被查找的顺序表类型定义如下：如下： #define MAXL typedef struct KeyType key; /*KeyType为关键字的数据类为关键字的数据类型型*/ InfoType data

6、; /*其他数据其他数据*/ NodeType; typedef NodeType SeqListMAXL; /*顺序表类型顺序表类型*/ 10.2.1 10.2.1 顺序查找顺序查找 顺序查找是一种最简单的查找方法。顺序查找是一种最简单的查找方法。 它的根本思绪是：从表的一端开场它的根本思绪是：从表的一端开场, ,顺序扫描线性顺序扫描线性表表, ,依次将扫描到的关键字和给定值依次将扫描到的关键字和给定值k k相比较相比较, ,假设当前假设当前扫描到的关键字与扫描到的关键字与k k相等相等, ,那么查找胜利；假设扫描终那么查找胜利；假设扫描终了后了后, ,仍未找到关键字等于仍未找到关键字等于k

7、 k的记录的记录, ,那么查找失败。那么查找失败。 例 如例 如 , , 在 关 键 字 序 列 为在 关 键 字 序 列 为3,9,1,5,8,10,6,7,2,43,9,1,5,8,10,6,7,2,4的线性表查找的线性表查找关键字为关键字为6 6的元素。的元素。 顺序查找过程如下：顺序查找过程如下： 开场开场: 3 9 1 5 8 10 6 7 2 4 第第1次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第第2次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=1 第第3次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第第4次比较次比较:

8、3 9 1 5 8 10 6 7 2 4 i=3 第第5次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=4 第第6次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=5 第第7次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=6 查找胜利查找胜利,前往序号前往序号6 顺序查找的算法如下顺序查找的算法如下( (在顺序表在顺序表R0.n-1R0.n-1中查找关中查找关键字为键字为k k的记录的记录, ,胜利时前往找到的记录位置胜利时前往找到的记录位置, ,失败时前失败时前往往-1)-1)： int SeqSearch(SeqList R,int n,KeyTyp

9、e k)int SeqSearch(SeqList R,int n,KeyType k) int i=0; int i=0; while (in & Ri.key!=k) i+; / while (i=n) if (i=n) return -1; return -1; else else return i; return i; 从顺序查找过程可以看到从顺序查找过程可以看到(不思索越界比较不思索越界比较in),ci取决于所查记录在表中的位置。如查找表中取决于所查记录在表中的位置。如查找表中第第1个记录个记录R0时时,仅需比较一次；而查找表中最后仅需比较一次；而查找表中最后一个记录一个记录

10、Rn-1时时,需比较需比较n次次,即即ci=i。因此。因此,胜利时胜利时的顺序查找的平均查找长度为：的顺序查找的平均查找长度为： 21n2)1n(nn1in1icipsqASLn1in1i 查找胜利时的平均比较次数约为表长的一半查找胜利时的平均比较次数约为表长的一半 。10.2.2 10.2.2 二分查找二分查找 二分查找也称为折半查找要求线性表中的二分查找也称为折半查找要求线性表中的结点必需己按关键字值的递增或递减顺序陈列。结点必需己按关键字值的递增或递减顺序陈列。它首先用要查找的关键字它首先用要查找的关键字k k与中间位置的结点与中间位置的结点的关键字相比较的关键字相比较, ,这个中间结点

11、把线性表分成这个中间结点把线性表分成了两个子表了两个子表, ,假设比较结果相等那么查找完成假设比较结果相等那么查找完成; ;假设不相等假设不相等, ,再根据再根据k k与该中间结点关键字的比与该中间结点关键字的比较大小确定下一步查找哪个子表较大小确定下一步查找哪个子表, ,这样递归进这样递归进展下去展下去, ,直到找到满足条件的结点或者该线性直到找到满足条件的结点或者该线性表中没有这样的结点。表中没有这样的结点。 例 如例 如 , , 在 关 键 字 有 序 序 列在 关 键 字 有 序 序 列2,4,7,9,10,14,18,26,32,402,4,7,9,10,14,18,26,32,40

12、中采用二中采用二分查找法查找关键字为分查找法查找关键字为7 7的元素。的元素。二分查找过程如下：二分查找过程如下： 开场开场: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=(0+9)/2=4 第第1次比较次比较: 2 4 7 9 10 14 18 26 32 40 l o w = 0 h i g h = 3 mid=(0+3)/2=1 第第2次比较次比较: 2 4 7 9 10 14 18 26 32 40 l o w = 2 h i g h = 3 mid=(2+3)/2=2 第第3次比较次比较: 2 4 7 9 10 14 18 26 32 40

13、R2.key=7 查找胜利查找胜利,前往序号前往序号2 其算法如下其算法如下(在有序表在有序表R0.n-1中进展二分查找中进展二分查找,胜利胜利时前往记录的位置时前往记录的位置,失败时前往失败时前往-1)： int BinSearch(SeqList R,int n,KeyType k) int low=0,high=n-1,mid; while (lowk) /*继续在继续在Rlow.mid-1中查中查找找*/ high=mid-1; else low=mid+1; /*继续在继续在Rmid+1.high中查找中查找*/ return -1; 二分查找过程可用二叉树来描画二分查找过程可用二叉

14、树来描画,我们把当前我们把当前查找区间的中间位置上的记录作为根查找区间的中间位置上的记录作为根,左子表和右左子表和右子表中的记录分别作为根的左子树和右子树子表中的记录分别作为根的左子树和右子树,由此由此得到的二叉树得到的二叉树,称为描画二分查找的断定树或比较称为描画二分查找的断定树或比较树。树。 5 2 8 0 3 6 9 -1 1 23 4 56 7 89 10 01 12 34 45 67 78 910 10 = = = = = = = = = = = R0.10的二分查线的断定树的二分查线的断定树(n=11) 例例10.1对于给定对于给定11个数据元素的有序表个数据元素的有序表2,3,1

15、0,15,20,25,28,29,30,35,40,采用二分查找采用二分查找,试试问：问： (1)假设查找给定值为假设查找给定值为20的元素的元素,将依次与表中将依次与表中哪些元素比较？哪些元素比较？ (2)假设查找给定值为假设查找给定值为26的元素的元素,将依次与哪些将依次与哪些元素比较？元素比较？ (3)假设查找表中每个元素的概率一样假设查找表中每个元素的概率一样,求查找求查找胜利时的平均查找长度和查找不胜利时的平均查胜利时的平均查找长度和查找不胜利时的平均查找长度。找长度。 25 10 30 2 15 28 35 3 20 29 40 二分查二分查找断定找断定树树 (2)假设查找给定值为

16、假设查找给定值为26的元素的元素,依次与依次与25,30,28元素比较元素比较,共共比较比较3次。次。 (3)在查找胜利时在查找胜利时,会找到图中某个圆形结点会找到图中某个圆形结点,那么胜利时的那么胜利时的平均查找长度：平均查找长度：31144342211ASLsucc (1)假设查找给假设查找给定值为定值为20的元素的元素,依依次与表中次与表中25,10,15,20元素比元素比较较,共比较共比较4次。次。 在查找不胜利时在查找不胜利时, ,会找到图中某个方形结点会找到图中某个方形结点, ,那么不胜那么不胜利时的平均查找长度：利时的平均查找长度： 67. 3124834ASLunsucc 10

17、.2.3 10.2.3 分块查找分块查找 分块查找又称索引顺序查找分块查找又称索引顺序查找, ,它是一种性它是一种性能介于顺序查找和二分查找之间的查找方法。能介于顺序查找和二分查找之间的查找方法。 它要求按如下的索引方式来存储线性表：它要求按如下的索引方式来存储线性表：将表将表R0.n-1R0.n-1均分为均分为b b块块, ,前前b-1b-1块中记录个数为块中记录个数为s=s=n/bn/b , ,最后一块即第最后一块即第b b块的记录数小于等于块的记录数小于等于s s；每；每一块中的关键字不一定有序一块中的关键字不一定有序, ,但前一块中的最大关键但前一块中的最大关键字必需小于后一块中的最小

18、关键字字必需小于后一块中的最小关键字, ,即要求表是即要求表是“分分块有序的；抽取各块中的最大关键字及其起始位块有序的；抽取各块中的最大关键字及其起始位置构成一个索引表置构成一个索引表IDX0.b-1,IDX0.b-1,即即IDXi(0ib-IDXi(0ib-1)1)中存放着第中存放着第i i块的最大关键字及该块在表块的最大关键字及该块在表R R中的起中的起始位置。由于表始位置。由于表R R是分块有序的是分块有序的, ,所以索引表是一个所以索引表是一个递增有序表。递增有序表。索引表的数据类型定义如下：索引表的数据类型定义如下：#define MAXI typedef struct KeyTyp

19、e key; /*KeyType为关键字的类型为关键字的类型*/ int link; /*指向对应块的起始指向对应块的起始下标下标*/ IdxType;typedef IdxType IDXMAXI;/*索引表类型索引表类型*/ 例如,设有一个线性表,其中包含25个记录,其关键字序列为8,14,6,9,10,22,34,18,19,31,40,38,54,66, 46,71,78,68,80,85,100, 94,88,96,87。假设将。假设将25个记录分为个记录分为5块块,每块中有每块中有5个记个记录录,该线性表的索引存储构造如以下图所示。该线性表的索引存储构造如以下图所示。 14 34

20、66 85 100 0 5 10 15 20 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 100 94 88 96 87 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 key link 采用二分查找索引表的分块查找算法如下采用二分查找索引表的分块查找算法如下(索索引表引表I的长度为的长度为m)：int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k) int low=0,high=m-1,mid

21、,i; int b=n/m; /*b为每块的记录个为每块的记录个数数*/ while (low=k) high=mid-1; else low=mid+1; if (lowm) /*在块中顺序查找在块中顺序查找*/ i=Ilow.link; while (i=Ilow.link+b-1 & Ri.key!=k) i+; if (ikey=k) /*递归终结条件递归终结条件*/ return bt; if (kkey) return SearchBST(bt-lchild,k); /*在左子树中递归查找在左子树中递归查找*/ else return SearchBST(bt-rchild

22、,k); /*在右子树中递归查找在右子树中递归查找*/ 2. 二叉排序树的插入和生成二叉排序树的插入和生成 在二叉排序树中插入一个新记录在二叉排序树中插入一个新记录,要保证插入后要保证插入后仍满足仍满足BST性质。其插入过程是：假设二叉排序树性质。其插入过程是：假设二叉排序树T为空为空,那么创建一个那么创建一个key域为域为k的结点的结点,将它作为根结点；将它作为根结点；否那么将否那么将k和根结点的关键字比较和根结点的关键字比较,假设二者相等假设二者相等,那那么阐明树中已有此关键字么阐明树中已有此关键字k,无须插入无须插入,直接前往直接前往0；假；假设设kkey,那么将那么将k插入根结点的左子

23、树中插入根结点的左子树中,否那么否那么将它插入右子树中。对应的递归算法将它插入右子树中。对应的递归算法InsertBST()如如下：下：int InsertBST(BSTNode *&p,KeyType k)/*在以在以*p为根结点的为根结点的BST中插入一个关键字为中插入一个关键字为k的结点。插入的结点。插入胜利前往胜利前往1,否那么前往否那么前往0*/ if (p=NULL) /*原树为空原树为空, 新插入的记录为根结点新插入的记录为根结点*/ p=(BSTNode *)malloc(sizeof(BSTNode); p-key=k;p-lchild=p-rchild=NULL;

24、return 1; else if (k=p-key) /*存在一样关键字的结点存在一样关键字的结点,前往前往0*/ return 0; else if (kkey) return InsertBST(p-lchild,k);/*插入到左子树中插入到左子树中*/ else return InsertBST(p-rchild,k); /*插入到右子树中插入到右子树中*/ 二叉排序树的生成二叉排序树的生成,是从一个空树开场是从一个空树开场,每插入一个关键字每插入一个关键字,就调用一次插入算法将它插入到当前已生成的二叉排序树中。就调用一次插入算法将它插入到当前已生成的二叉排序树中。从关键字数组从关键

25、字数组A0.n-1生成二叉排序树的算法生成二叉排序树的算法CreatBST()如如下：下： BSTNode *CreatBST(KeyType A,int n) /*前往树根指针前往树根指针*/ BSTNode *bt=NULL; /*初始时初始时bt为空树为空树*/ int i=0; while (irchild!=NULL) Delete1(p,r-rchild);/*递归找最右下结递归找最右下结点点*/else /*找到了最右下结点找到了最右下结点*r*/ p-key=r-key; /*将将*r的关键字值赋的关键字值赋给给*p*/ q=r; r=r-lchild; /*将左子树的根结点放

26、在被删结点的位置将左子树的根结点放在被删结点的位置上上*/ free(q); /*释放原释放原*r的空间的空间*/ void Delete(BSTNode *&p) /*从二叉排序树中删除从二叉排序树中删除*p结点结点*/ BSTNode *q; if (p-rchild=NULL) /*p结点没有右子树的情况结点没有右子树的情况*/ q=p; p=p-lchild; /*其右子树的根结点放在被删结点的位置上其右子树的根结点放在被删结点的位置上*/ free(q); else if (p-lchild=NULL) /*p结点没有左子树结点没有左子树*/ q=p; p=p-rchild;

27、 /*将将*p结点的右子树作为双亲结点的相应子树结点的右子树作为双亲结点的相应子树/ free(q); else Delete1(p,p-lchild); /*p结点既没有左子树又没有右子树的情况结点既没有左子树又没有右子树的情况*/int DeleteBST(BSTNode *&bt,KeyType k)/*在在bt中删除关键字为中删除关键字为k的结点的结点*/ if (bt=NULL) return 0;/*空树删除失败空树删除失败*/ else if (kkey) return DeleteBST(bt-lchild,k); /*递归在左子树中删除为递归在左子树中删除为k的结点的

28、结点*/else if (kbt-key) return DeleteBST(bt-rchild,k); /*递归在右子树中删除为递归在右子树中删除为k的结点的结点*/else Delete(bt); /*调用调用Delete(bt)函数删除函数删除*bt结点结点*/ return 1; 10.3.2 10.3.2 平衡二叉树平衡二叉树(AVL)(AVL) 假设一棵二叉树中每个结点的左、右子树假设一棵二叉树中每个结点的左、右子树的高度至多相差的高度至多相差1,1,那么称此二叉树为平衡二叉树。那么称此二叉树为平衡二叉树。在算法中在算法中, ,经过平衡因子经过平衡因子(balancd factor

29、,(balancd factor,用用bfbf表示表示) )来详细实现上述平衡二叉树的定义。平衡因子的定来详细实现上述平衡二叉树的定义。平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域义是：平衡二叉树中每个结点有一个平衡因子域, ,每每个结点的平衡因子是该结点左子树的高度减去右子个结点的平衡因子是该结点左子树的高度减去右子树的高度。从平衡因子的角度可以说树的高度。从平衡因子的角度可以说, ,假设一棵二叉假设一棵二叉树中一切结点的平衡因子的绝对值小于或等于树中一切结点的平衡因子的绝对值小于或等于1,1,即即平衡因子取值为平衡因子取值为1 1、0 0或或-1,-1,那么该二叉树称为平衡二那么

30、该二叉树称为平衡二叉树。叉树。 5 2 6 1 4 3 7 1 0 -1 0 1 0 -1 3 1 4 2 5 6 7 (b) (a) 0 -1 -2 -3 -2 -1 0 平衡二叉树和不平衡二叉树平衡二叉树和不平衡二叉树 定义定义AVL树的结点的类型如下：树的结点的类型如下：typedef struct node /*记录类型记录类型*/KeyType key; /*关键字项关键字项*/ int bf;/*添加的平衡添加的平衡因子因子*/ InfoType data; /*其他数据域其他数据域*/ struct node *lchild,*rchild;/*左右孩子指左右孩子指针针*/ BS

31、TNode; 假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性,首先要找出插入新结点后失去平衡的最小子树根结点的指针,然后再调整这个子树中有关结点之间的链接关系,使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后,原有其他一切不平衡子树无需调整,整个二叉排序树就又成为一棵平衡二叉树。 失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点,那么调整该子树的操作可归纳为以下四种情况： (1) LL型调整 (2) RR型调整 (3) LR型调整 (4) RL型调整 例例10.3 输入关键字序列输入关键字序列16,

32、3,7,11,9,26,18,14,15,给给出构造一棵出构造一棵AVL树的步骤。树的步骤。 16 0 (a)插入插入 16 16 1 (b)插入插入 3 3 0 16 2 (c)插入插入 7 3 -1 7 0 7 0 (d)LR 调整调整 3 0 16 0 7 -1 (e)插入插入 11 3 0 16 1 11 0 7 -2 (f)插入插入 9 3 0 16 2 11 1 9 0 7 -1 (g)LL 调整调整 3 0 11 0 9 0 16 0 7 -2 3 0 11 -1 9 0 16 -1 (h)插入插入 26 26 0 7 0 3 0 11 0 9 0 16 -1 26 0 (i)R

33、R 调整调整 7 0 3 0 11 -1 9 0 16 -2 26 1 (j)插入插入 18 18 0 7 0 3 0 11 0 9 0 18 0 26 0 (k)RL 调整调整 16 0 7 0 3 0 11 -1 9 0 18 1 26 0 16 1 (l)插入插入 14 14 0 7 0 3 0 11 -2 9 0 18 2 26 0 16 2 (m)插入插入 15 14 -1 15 0 7 0 3 0 11 -1 9 0 18 1 26 0 15 0 0 14 16 0 (n)LR 调整调整 在平衡二叉树上进展查找的过程和在二叉排序树上在平衡二叉树上进展查找的过程和在二叉排序树上进展查

34、找的过程完全一样，因此，在平衡二叉树上进进展查找的过程完全一样，因此，在平衡二叉树上进展查找关键字的比较次数不会超越平衡二叉树的深度。展查找关键字的比较次数不会超越平衡二叉树的深度。 在最坏的情况下，普通二叉排序树的查找长度为在最坏的情况下，普通二叉排序树的查找长度为O(n)。那么，平衡二叉树的情况又是怎样的呢？下面。那么，平衡二叉树的情况又是怎样的呢？下面分析平衡二叉树的高度分析平衡二叉树的高度h和结点个数和结点个数n之间的关系。之间的关系。 首先，构造一系列的平衡二叉树首先，构造一系列的平衡二叉树T1，T2，T3，其，其中，中，Thh=1，2，3，是高度为是高度为h且结点数尽能够少的平且结

35、点数尽能够少的平衡二叉树，如图衡二叉树，如图10.12中所示的中所示的T1，T2，T3和和T4。为了构造。为了构造Th，先分别构造，先分别构造Th-1和和Th-2，使，使Th以以Th-1和和Th-2作为其根结作为其根结点的左、右子树。对于每一个点的左、右子树。对于每一个Th，只需从中删去一个结点，只需从中删去一个结点，就会失去平衡或高度不再是就会失去平衡或高度不再是h显然，这样构造的平衡二叉树显然，这样构造的平衡二叉树在结点个数一样的平衡二叉树中具有最大高度。在结点个数一样的平衡二叉树中具有最大高度。 T1 T2 T3 T4 Th Th-1 Th-2 图图10.12 结点个数结点个数n最少的平

36、衡二叉树最少的平衡二叉树 然后，经过计算上述平衡二叉树中的结点个数，来建立高度然后，经过计算上述平衡二叉树中的结点个数，来建立高度与结点个数之间的关系。设与结点个数之间的关系。设N(h)为为Th的结点数，从图的结点数，从图10.12中中可以看出有以下关系成立：可以看出有以下关系成立： N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1当当h1时，此关系类似于定义时，此关系类似于定义Fibonacci数的关系：数的关系： F(1)=1，F(2)=1，F(h)=F(h-1)+F(h-2)经过检查两个序列的前几项就可发现两者之间的对应关系：经过检查两个序列的前几项就可发现两者之间的

37、对应关系： N(h)=F(h+2)-1由于由于Fibonacci数满足渐近公式：数满足渐近公式：F(h)=其中，其中，故由此可得近似公式：故由此可得近似公式：N(h)=即：即：hlog2(N(h)+1)所以，含有所以，含有n个结点的平衡二叉树的平均查找长度为个结点的平衡二叉树的平均查找长度为O(log2n)。 h51251 121512 hh10.3.3 B-树树 B-树又称为多路平衡查找树树又称为多路平衡查找树,是一种组织和维护外是一种组织和维护外存文件系统非常有效的数据构造。存文件系统非常有效的数据构造。 B-树中一切结点的孩子结点最大值称为树中一切结点的孩子结点最大值称为B-树的阶树的阶

38、,通常用通常用m表示表示,从查找效率思索从查找效率思索,要求要求m3。一棵。一棵m阶阶B-树或者是一棵空树树或者是一棵空树,或者是满足以下要求的或者是满足以下要求的m叉树：叉树： (1) 树中每个结点至多有树中每个结点至多有m个孩子结点个孩子结点(即至多有即至多有m-1个关键字个关键字)； (2) 除根结点外除根结点外,其他结点至少有其他结点至少有m/2 个孩子结点个孩子结点(即至少有即至少有m/2 -1=(m-1)/2 个关键字个关键字)； (3) 假设根结点不是叶子结点假设根结点不是叶子结点,那么根结点至少有两那么根结点至少有两个孩子结点；个孩子结点； (4) 每个结点的构造为：每个结点的

39、构造为：np0k1p1k2p2knpn 其中其中,n为该结点中的关键字个数为该结点中的关键字个数,除根结点外除根结点外,其其他一切结点的他一切结点的n大于等于大于等于m/2 -1,且小于等于且小于等于m-1；ki(1in)为该结点的关键字且满足为该结点的关键字且满足kiki+1；pi(0in)为该结点的孩子结点指针且满足为该结点的孩子结点指针且满足pi(0in-1)结点上的关键字大于等于结点上的关键字大于等于ki且小于且小于ki+1,pn结点上结点上的关键字大于的关键字大于kn。 (5) 一切叶子结点都在同一层上一切叶子结点都在同一层上,即即B-树是一切结树是一切结点的平衡因子均等于点的平衡因

40、子均等于0的多路查找树。的多路查找树。 3 12 15 22 2 2 7 2 35 41 3 53 54 63 4 68 69 71 76 3 79 84 93 2 11 30 2 66 78 1 51 一棵一棵5阶阶B-树树在在B-树的存储构造中树的存储构造中,各结点的类型定义如下：各结点的类型定义如下：#define MAXM 10/*定义定义B-树的最大的阶数树的最大的阶数*/typedef int KeyType; /*KeyType为关键字类型为关键字类型*/typedef struct node /*B-树结点类型定义树结点类型定义*/ int keynum; /*结点当前拥有的关

41、键字的个数结点当前拥有的关键字的个数*/ KeyType keyMAXM; /*1.keynum存放关键字存放关键字,0不用不用*/ struct node *parent; /*双亲结点指针双亲结点指针*/ struct node *ptrMAXM;/*孩子结点指针数组孩子结点指针数组0.keynum*/ BTNode;(B-树的查找树的查找( 在在B-树中查找给定关键字的方法类似于二叉排树中查找给定关键字的方法类似于二叉排序树上的查找序树上的查找,不同的是在每个记录上确定向下查找不同的是在每个记录上确定向下查找的途径不一定是二路的途径不一定是二路(即二叉即二叉)的的,而是而是n+1路的。由

42、于路的。由于记录内的关键字序列是有序的数量记录内的关键字序列是有序的数量key1.n,故既可故既可以用顺序查找以用顺序查找,也可以用折半查找。在一棵也可以用折半查找。在一棵B-树上顺树上顺序查找关键字为序查找关键字为k的方法为：的方法为：将将k与根结点中的与根结点中的keyi进展比较：进展比较： (1) 假设假设k=keyi,那么查找胜利；那么查找胜利； (2) 假设假设kkey1,那么沿着指针那么沿着指针ptr0所指的所指的子树继续查找；子树继续查找； (3) 假设假设keyikkeyi+1,那么沿着指针那么沿着指针ptri所指的子树继续查找；所指的子树继续查找； (4) 假设假设kkeyn

43、,那么沿着指针那么沿着指针ptrn所指的所指的子树继续查找。子树继续查找。 2. B-树的插入树的插入将关键字将关键字k插入到插入到B-树的过程分两步完成：树的过程分两步完成： (1) 利用前述的利用前述的B-树的查找算法找出该关键字的插入树的查找算法找出该关键字的插入结点结点(留意留意B-树的插入结点一定是叶子结点树的插入结点一定是叶子结点)。 (2) 判别该结点能否还有空位置判别该结点能否还有空位置,即判别该结点能否满即判别该结点能否满足足nm-1,假设该结点满足假设该结点满足nm-1,阐明该结点还有空位阐明该结点还有空位置置,直接把关键字直接把关键字k插入到该结点的适宜位置上插入到该结点

44、的适宜位置上(即满足即满足插入后结点上的关键字仍坚持有序插入后结点上的关键字仍坚持有序)； 假设该结点有假设该结点有n=m-1,阐明该结点已没有空位置阐明该结点已没有空位置,需求把结点分裂成两个。需求把结点分裂成两个。 分裂的做法是分裂的做法是,取一新结点取一新结点,把原结点上的关键字把原结点上的关键字和和 k 按 升 序 排 序 后按 升 序 排 序 后 , 从 中 间 位 置从 中 间 位 置 ( 即即m/2=(m+1)/2之处之处)把关键字把关键字(不包括中间位不包括中间位置的关键字置的关键字)分成两部分分成两部分,左部分所含关键字放在旧左部分所含关键字放在旧结点中结点中,右部分所含关键

45、字放在新结点中右部分所含关键字放在新结点中,中间位置的中间位置的关键字连同新结点的存储位置插入到父亲结点中。关键字连同新结点的存储位置插入到父亲结点中。假设父结点的关键字个数也超越假设父结点的关键字个数也超越Max,那么要再分裂那么要再分裂,再往上插再往上插,直至这个过程传到根结点为止。直至这个过程传到根结点为止。例如例如 关键字序列为：关键字序列为：1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15。创建一棵创建一棵5阶阶B-树。树。建立建立B-的过程如以下图所示。的过程如以下图所示。 1 2 6 7 6 1 2 7 11 6 1 2 4 7

46、 8 11 13 6 10 1 2 4 11 13 7 8 6 10 1 2 4 5 11 13 16 7 8 9 6 10 16 1 2 4 5 7 8 9 3 6 10 16 1 2 7 8 9 17 18 19 20 4 5 10 14 15 13 16 3 6 1 2 7 8 9 (a)插入插入 1,2,6,7 (b)插入插入 11 (c)插入插入 4,8,13 (d)插入插入 10 (e)插入插入 5,17,9,16 (f)插入插入 20 (g)插入插入 3,12,14,18,19 (h)插入插入 15 11 13 17 20 17 18 19 20 11 12 13 14 4 5

47、11 12 3. B-树的删除树的删除 B-树的删除过程与插入过程类似树的删除过程与插入过程类似,只是稍为复杂一些。只是稍为复杂一些。要使删除后的结点中的关键字个数要使删除后的结点中的关键字个数m/2 -1,将涉及到将涉及到结点的结点的“合并问题。在合并问题。在B-树上删除关键字树上删除关键字k的过程分的过程分两步完成：两步完成： (1) 利用前述的利用前述的B-树的查找算法找出该关键字所在的树的查找算法找出该关键字所在的结点。结点。 (2) 在结点上删除关键字在结点上删除关键字k分两种情况：一种是在叶分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关子结点上删除关键字；另

48、一种是在非叶子结点上删除关键字。键字。 (3) 在非叶子结点上删除关键字的过程：假设要删在非叶子结点上删除关键字的过程：假设要删除关键字除关键字keyi(1in),在删去该关键字后在删去该关键字后,以该结点以该结点ptri所指子树中的最小关键字所指子树中的最小关键字keymin来替代被删关来替代被删关键字键字keyi所在的位置所在的位置(留意留意ptri所指子树中的最小关所指子树中的最小关键字键字keymin一定是在叶子结点上一定是在叶子结点上),然后再以指针然后再以指针ptri所指结点为根结点查找并删除所指结点为根结点查找并删除keymin(即再以即再以ptri所指结点为所指结点为B-树的根

49、结点树的根结点,以以keymin为要删除的关键为要删除的关键字字,然后再次调用然后再次调用B-树上的删除算法树上的删除算法),这样也就把在非这样也就把在非叶子结点上删除关键字叶子结点上删除关键字k的问题转化成了在叶子结点的问题转化成了在叶子结点上删除关键字上删除关键字keymin的问题。的问题。 (4) 在在B-树的叶子结点上删除关键字共有以下三种情树的叶子结点上删除关键字共有以下三种情况：况： 假设被删结点的关键字个数大于假设被删结点的关键字个数大于Min,阐明删去该阐明删去该关键字后该结点仍满足关键字后该结点仍满足B-树的定义树的定义,那么可直接删去该那么可直接删去该关键字。关键字。 假设

50、被删结点的关键字个数等于假设被删结点的关键字个数等于Min,阐明删去关阐明删去关键字后该结点将不满足键字后该结点将不满足B-树的定义树的定义,此时假设该结点的此时假设该结点的左左(或右或右)兄弟结点中关键字个数大于兄弟结点中关键字个数大于Min,那么把该结点那么把该结点的左的左(或右或右)兄弟结点中最大兄弟结点中最大(或最小或最小)的关键字上移到双的关键字上移到双亲结点中亲结点中,同时把双亲结点中大于同时把双亲结点中大于(或小于或小于)上移关键字的上移关键字的关键字下移到要删除关键字的结点中关键字下移到要删除关键字的结点中,这样删去关键字这样删去关键字k后该结点以及它的左后该结点以及它的左(或

51、右或右)兄弟结点都仍旧满足兄弟结点都仍旧满足B-树的树的定义。定义。 假设被删结点的关键字个数等于假设被删结点的关键字个数等于Min,并且该并且该结点的左和右兄弟结点结点的左和右兄弟结点(假设存在的话假设存在的话)中关键字个中关键字个数均等于数均等于Min,这时这时,需把要删除关键字的结点与其左需把要删除关键字的结点与其左(或右或右)兄弟结点以及双亲结点中分割二者的关键字兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。假设因此使双亲结点中关键字个合并成一个结点。假设因此使双亲结点中关键字个数小于数小于Min,那么对此双亲结点做同样处置那么对此双亲结点做同样处置,以致于能以致于能够直到对根

52、结点做这样的处置而使整个树减少一层。够直到对根结点做这样的处置而使整个树减少一层。 例如例如,对于上例生成的对于上例生成的B-树树,给出删除给出删除8,16,15,4等四个关等四个关键字的过程。键字的过程。 10 3 6 13 17 1 2 4 5 7 9 11 12 14 15 18 19 20 (a) 初始初始 5 阶阶 B- -树树 (b) 删除删除 8,16 后的结果后的结果 10 3 6 13 18 1 2 4 5 11 12 14 17 19 20 (c) 删除删除 15 后的结果后的结果 6 10 13 18 1 2 3 5 7 9 14 17 19 20 (d) 删除删除 4

53、后的结果后的结果 7 9 11 12 10 14 15 13 16 3 6 1 2 7 8 9 17 18 19 20 4 5 11 12 10.3.4 B+10.3.4 B+树树 在索引文件组织中在索引文件组织中, ,经常运用经常运用B-B-树的一些变形树的一些变形, ,其中其中B+B+树是一种运用广泛的变形。一棵树是一种运用广泛的变形。一棵m m阶阶B+B+树满足以树满足以下条件：下条件： (1) (1) 每个分支结点至多有每个分支结点至多有m m棵子树。棵子树。 (2) (2) 除根结点外除根结点外, ,其他每个分支结点至少有其他每个分支结点至少有(m+1)/2(m+1)/2棵子树。棵子

54、树。 (3) (3) 根结点至少有两棵子树根结点至少有两棵子树, ,至多有至多有m m棵子树。棵子树。 (4) (4) 有有n n棵子树的结点有棵子树的结点有n n个关键字。个关键字。 (5) 一切叶子结点包含全部一切叶子结点包含全部(数据文件中记录数据文件中记录) 关关键字及指向相应记录的指针键字及指向相应记录的指针(或存放数据文件分块或存放数据文件分块后每块的最大关键字及指向该块的指针后每块的最大关键字及指向该块的指针),而且叶子而且叶子结点按关键字大小顺序链接结点按关键字大小顺序链接(可以把每个叶子结点可以把每个叶子结点看成是一个根本索引块看成是一个根本索引块,它的指针不再指向另一级索它

55、的指针不再指向另一级索引块引块,而是直接指向数据文件中的记录而是直接指向数据文件中的记录)。 (6) 一切分支结点一切分支结点(可看成是索引的索引可看成是索引的索引)中仅包中仅包含它的各个子结点含它的各个子结点(即下级索引的索引块即下级索引的索引块)中最大关中最大关键字及指向子结点的指针。键字及指向子结点的指针。 33 18 23 48 10 12 15 18 19 20 21 22 23 30 31 33 45 47 48 50 52 一棵一棵4阶的阶的B+树树 m阶的阶的B+树和树和m阶的阶的B-树树,定义中的前三点是一样定义中的前三点是一样的的,主要的差别是：主要的差别是： (1) 在在

56、B+树中树中,具有具有n个关键字的结点含有个关键字的结点含有n棵子树棵子树,即即每个关键字对应一棵子树每个关键字对应一棵子树,而在而在B-树中树中,具有具有n个关键字个关键字的结点含有的结点含有(n+1)棵子树。棵子树。 (2) 在在B+树中树中,每个结点每个结点(除根结点外除根结点外)中的关键字个数中的关键字个数n的取值范围是的取值范围是m/2 n m,根结点根结点n的取值范围是的取值范围是1nm；而在；而在B-树中树中,它们的取值范围分别是它们的取值范围分别是m/2 -1n m-1和和1nm-1。 (3) B+树中的一切叶子结点包含了全部关键字树中的一切叶子结点包含了全部关键字,即其即其他

57、非叶子结点中的关键字包含在叶子结点中他非叶子结点中的关键字包含在叶子结点中,而在而在B-树树中中,叶子结点包含的关键字与其他结点包含的关键字是叶子结点包含的关键字与其他结点包含的关键字是不反复的。不反复的。 (4) B+树中一切非叶子结点仅起到索引的作用树中一切非叶子结点仅起到索引的作用,即结点中的即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。而在不含有该关键字对应记录的存储地址。而在B-树中树中,每个关键每个关键字对应一个记录的存储地址。字对应一个记录的存储地址。 (5) 通常在通常在

58、B+树上有两个头指针树上有两个头指针,一个指向根结点一个指向根结点,另一个指另一个指向关键字最小的叶子结点向关键字最小的叶子结点,一切叶子结点链接成一个不定长的一切叶子结点链接成一个不定长的线性链表。线性链表。10.4 10.4 哈希表查找哈希表查找10.4.1 10.4.1 哈希表的根本概念哈希表的根本概念 哈希表哈希表(Hash Table)(Hash Table)又称散列表又称散列表, ,是除是除顺序表存储构造、链接表存储构造和索引表存储顺序表存储构造、链接表存储构造和索引表存储构造之外的又一种存储线性表的存储构造。哈希构造之外的又一种存储线性表的存储构造。哈希表存储的根本思绪是：设要存

59、储的对象个数为表存储的根本思绪是：设要存储的对象个数为n,n,设置一个长度为设置一个长度为m(mn)m(mn)的延续内存单元的延续内存单元, ,以线性以线性表中每个对象的关键字表中每个对象的关键字ki(0in-1)ki(0in-1)为自变量为自变量, ,经过一个称为哈希函数的函数经过一个称为哈希函数的函数h(ki),h(ki),把把kiki映射映射为内存单元的地址为内存单元的地址( (或称下标或称下标)h(ki),)h(ki),并把该对并把该对象存储在这个内存单元中。象存储在这个内存单元中。h(ki)h(ki)也称为哈希地也称为哈希地址址( (又称散列地址又称散列地址) )。把如此构造的线性表

60、存储构。把如此构造的线性表存储构造称为哈希表。造称为哈希表。 但是存在这样的问题但是存在这样的问题,对于两个关键字对于两个关键字ki和和kj(ij),有有kikj(ij),但但h(ki)=h(kj)。我们把这种景象叫做哈。我们把这种景象叫做哈希冲突。希冲突。 通常把这种具有不同关键字而具有一样哈希地通常把这种具有不同关键字而具有一样哈希地址的对象称做址的对象称做“同义词同义词,由同义词引起的冲突称作由同义词引起的冲突称作同义词冲突。在哈希表存储构造的存储中同义词冲突。在哈希表存储构造的存储中,同义词冲同义词冲突是很难防止的突是很难防止的,除非关键字的变化区间小于等于哈除非关键字的变化区间小于等于哈希地址的变化区间希地址的变化区间