小学教育查找课件

《小学教育查找课件》由会员分享，可在线阅读，更多相关《小学教育查找课件（111页珍藏版）》请在金锄头文库上搜索。

1、第八章 查找8.1 8.1 基本概念基本概念8.2 8.2 静态查找表静态查找表8.3 8.3 动态查找表动态查找表8.4 8.4 哈希表哈希表 小学教育 查找查找查找也叫检索，是根据给定的某个值，也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或在表中确定一个关键字等于给定值的记录或数据元素数据元素关键字关键字是数据元素中某个数据项的值，是数据元素中某个数据项的值，它可以标识一个数据元素它可以标识一个数据元素查找方法评价查找方法评价查找速度查找速度占用存储空间多少占用存储空间多少算法本身复杂程度算法本身复杂程度平均查找长度平均查找长度ASL(Average Search L

2、ength)ASL(Average Search Length)：为为确定记录在表中的位置，需和给定值进行比较的确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的关键字的个数的期望值叫查找算法的 小学教育 查找小学教育 查找8.2.1 8.2.1 顺序表的查找顺序表的查找 查找过程：从表的一端开始逐个进行记查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较录的关键字和给定值的比较i例例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 18 21 37 56 64 75 80 88 92找找6464监视哨监视哨iiii比较次数比较次数=5比较次数：比

3、较次数：查找第查找第n个元素：个元素： 1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素： n查找第查找第i个元素：个元素： n+1-i查找失败：查找失败： n+1小学教育 查找#define MAXSIZE 100#define KEYTYPE inttypedef structKEYTYPE key; otherdata ; / 记录的其余数据部分SSELEMENT;typedef struct SSELEMENT rMAXSIZE; int len;SSTABLE;小学教育 查找int seq_search (KEYTYPE k, SSTABLE st) int j;

4、 j = st.len; st.r0.key = k; while(st.rj.key != k) j-; return j;顺序查找算法：顺序查找算法：小学教育 查找顺序查找方法的顺序查找方法的ASLASL小学教育 查找查找过程查找过程：每次将待查记录所在区间缩小一半每次将待查记录所在区间缩小一半适用条件适用条件：采用顺序存储结构的：采用顺序存储结构的有序有序表表算法实现算法实现: :设表长为设表长为n n，lowlow、highhigh和和midmid分别指向待查元素分别指向待查元素所在区间的上界、下界和中点所在区间的上界、下界和中点,k,k为给定值为给定值初始时，令初始时，令low=1,

5、high=n,mid=low=1,high=n,mid= (low+high)/2(low+high)/2 让让k k与与midmid指向的记录比较指向的记录比较若若k=rmid.keyk=rmid.key，查找成功查找成功若若krmid.keykrmid.keykrmid.key，则，则low=mid+1low=mid+1重复上述操作，直至重复上述操作，直至lowhighlowhigh时，查找失败时，查找失败8.2.2 8.2.2 有序表查找（折半查找）有序表查找（折半查找）小学教育 查找算法描述：lowhighmid例例 1 2 3 4 5 6 7 8 9 10 115 13 18 21

6、37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid小学教育 查找例例 1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid1 2 3

7、4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid小学教育 查找1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92小学教育 查找算法评价算法评价: :判定树：描述查找过程的二叉树叫判

8、定树：描述查找过程的二叉树叫 有有n n个结点的判定树的深度为个结点的判定树的深度为 loglog2 2n n +1+1折半查找法在查找过程中进行的比较次数最折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度多不超过其判定树的深度小学教育 查找折半查找的折半查找的ASLASL：小学教育 查找8.2.3 8.2.3 索引顺序表查找（分块查找）索引顺序表查找（分块查找）查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找适用条件：分块有序表算法实现用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针

9、小学教育 查找1 2 3 4 5 6 7 8 8 10 11 12 13 14 15 16 17 1822 12 13 8 8 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38算法描述:小学教育 查找typedef struct int key; int link;SD;typedef struct int key; float info;JD;int blocksrch(JD r ,SD nd ,int b,int k,int n) int i=1,j;while(kndi.key)&(ib) printf(nNot fou

10、nd); return(0); j=ndi.link; while(jn)&(k!=rj.key)&(rj.keylchild = NULL; p-rchild = NULL; p-key = k; else if(k p-key) insert_btree_onenode(k,p-rchild else insert_btree_onenode(k,p-lchild 小学教育 查找typedef struct node int data; struct node *lchild,*rchild;JD;JD *insertbst(JD *r,int x) JD *p,*q,*s; s=(JD

11、*)malloc(sizeof(JD); s-data=x; s-lchild=s-rchild=NULL; q=NULL; if(r=NULL) r=s; return(r); p=r; 小学教育 查找while(p!=NULL) q=p; if(xdata) p=p-lchild; else p=p-rchild; if(xdata) q-lchild=s; else q-rchild=s; return(r);小学教育 查找要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情况：结点，分三种情况：p为叶子结点，只需修改为叶子结点，只需修改p双亲双亲f的指针的指针 f-lchild=N

12、ULL f-rchild=NULLp只有左子树或右子树只有左子树或右子树p只有左子树，用只有左子树，用p的左孩子代替的左孩子代替p (1)(2)p只有右子树，用只有右子树，用p的右孩子代替的右孩子代替p (3)(4)p左、右子树均非空左、右子树均非空沿沿p左子树的根左子树的根C的右子树分支找到的右子树分支找到S，S的右子的右子树为空，将树为空，将S的左子树成为的左子树成为S的双亲的双亲Q的右子树，的右子树，用用S取代取代p (5)若若C无右子树，用无右子树，用C取代取代p (6)二叉排序树的删除二叉排序树的删除小学教育 查找SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍

13、历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Q(1)小学教育 查找中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)SPPRQ中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SQPRP小学教育 查找FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍历：中序遍历：CL C P PR FFCPRCL中序遍历：中序遍历：CL C

14、PR F(6)小学教育 查找例例805012060110150557053删除删除508060120110150557053删除删除60805512011015053701042581354删除删除1084255134删除删除58425413删除算法删除算法小学教育 查找JD *delnode(JD *r,JD *p,JD *f) JD *q,*s; int flag=0; if(p-lchild=NULL) s=p-rchild; else if(p-rchild=NULL) s=p-lchild; else 删除算法删除算法:小学教育 查找 q=p; s=p-lchild; while(s

15、-rchild!=NULL) q=s; s=s-rchild; p-data=s-data; if(q=p) q-lchild=s-lchild; else q-rchild=s-lchild; free(s); flag=1;FPCPRCLQQLSSLFPCPRCL小学教育 查找if(flag=0) if(f=NULL) r=s; else if(f-lchild=p) f-lchild=s; else f-rchild=s; free(p); return(r);小学教育 查找查找性能的分析： 对于每一棵特定的二叉排序树，均对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的可按

16、照平均查找长度的定义来求它的ASLASL值，显然，由值相同的值，显然，由值相同的n n个关键字构个关键字构造所得的，不同形态的各棵二叉排序树造所得的，不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差的平均查找长度的值不同，甚至可能差别很大别很大小学教育 查找例如：例如： 由关键字序列由关键字序列1 1，2 2，3 3，4 4，5 5构造而得的二叉排序构造而得的二叉排序树树 ASL =ASL =（1+2+3+4+51+2+3+4+5）/ 5 = 3/ 5 = 3 由关键字序列由关键字序列3 3，1 1，2 2，5 5，4 4构造而得的二叉排序构造而得的二叉排序树树 ASL =ASL =

17、（1+2+3+2+31+2+3+2+3）/ 5 = 2.2/ 5 = 2.2 一般情况下，考虑含有一般情况下，考虑含有n n个关键字可能出现的个关键字可能出现的n!n!种种序列出现的可能性相等。序列出现的可能性相等。小学教育 查找 不失一般性，假设某个序列中有不失一般性，假设某个序列中有k k个关键字小于第个关键字小于第一个关键字，即有一个关键字，即有n-k-1n-k-1个关键字大于第一个关键个关键字大于第一个关键字，由它构造的二叉排序树的平均查找长度是字，由它构造的二叉排序树的平均查找长度是n n和和k k的函数的函数P(n, k)(0kn-1)P(n, k)(0kn-1)则含则含n n个关

18、键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度 而在等概率的情况下，而在等概率的情况下，小学教育 查找由此由此可类似于解差分方程，此递归方程有解：可类似于解差分方程，此递归方程有解：从查找的角度看，希望由任意序列生成的二叉排序树，从查找的角度看，希望由任意序列生成的二叉排序树，其左、右子树的深度近似相等，但实际上有其左、右子树的深度近似相等，但实际上有47%47%的情况的情况生成的二叉排序树非如此。生成的二叉排序树非如此。小学教育 查找9.5 9.5 平衡二叉树平衡二叉树 起因：提高查找速度，避免最坏情况出现。起因：提高查找速度，避免最坏情况出现。如右图情况的出现。如右图情况

19、的出现。 DGEDABCFEGBACF小学教育 查找 平衡因子（平衡度）：平衡因子（平衡度）：结点的平衡度是结点的平衡度是结点的左子树的高度右子树的高度。结点的左子树的高度右子树的高度。 平衡二叉树：平衡二叉树：每个结点的平衡因子都为每个结点的平衡因子都为 1 1、1 1、0 0 的二叉树。或者说每个的二叉树。或者说每个 结结点的左右子树的高度最多差一的二叉树。点的左右子树的高度最多差一的二叉树。小学教育 查找 平衡二叉排序树的平衡二叉排序树的 AdelsonAdelson 算法的本质特点：算法的本质特点： 以插入为例：以插入为例： 在左图所示的平衡二叉排序树中插入数据场为在左图所示的平衡二叉

20、排序树中插入数据场为2 2的结点。的结点。 插入之后仍应保持平衡二叉排序树的性质不变。插入之后仍应保持平衡二叉排序树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点如何用最简单、最有效的办法保持平衡二叉如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？排序树的性质不变？小学教育 查找 平衡二叉排序树的平衡二叉排序树的 Adelson 算法的本质特点：算法的本质特点： 以插入为例：以插入为例：

21、在左图所示的平衡二叉排序树中插入数据场为在左图所示的平衡二叉排序树中插入数据场为 2 的结点。的结点。 插入之后仍应保持平衡二叉排序树的性质不变。插入之后仍应保持平衡二叉排序树的性质不变。原平衡原平衡度为度为 0141253928635360501718730+1+1-1-1-1000000002+1+1+2危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？持平衡二叉排序树的性质不变？解决方案：解决方案：不涉及到危机结点的父亲结点，即以危不涉及到危机结点的父亲结点，即以危机结点为根的子树的高度应保持不变机结点为根的子树的高度应保持不变（左图为（

22、左图为 3 ）。）。新结点插入后，找到第一个平衡度不为新结点插入后，找到第一个平衡度不为 0 的结点（如左图结点的结点（如左图结点 ）即可。新）即可。新插入的结点和插入的结点和第一个平衡度不为第一个平衡度不为 0 的结点（也可能是的结点（也可能是危机结点）之间的结点，其平衡度皆为危机结点）之间的结点，其平衡度皆为 0在调整中，仅调整那些在平衡度变化的在调整中，仅调整那些在平衡度变化的路径上的结点（如：路径上的结点（如： ），其它结点不予调整。），其它结点不予调整。仍应保持二叉树排序树的性质不变。仍应保持二叉树排序树的性质不变。9359小学教育 查找 平衡二叉排序树的平衡二叉排序树的 Adels

23、on 算法的本质特点：算法的本质特点： 以插入为例：以插入为例： 在左图所示的平衡树中在左图所示的平衡树中插入插入数据场为数据场为 2 的结点。的结点。 插入之后仍应保持平衡二叉排序树的性质不变。插入之后仍应保持平衡二叉排序树的性质不变。141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？持平衡二叉排序树的性质不变？23597122359712不可以以结点不可以以结点 为子树的根为子树的根结点！虽然，对本例来说是可结点！虽然，

24、对本例来说是可以行得通的。以行得通的。7小学教育 查找 平衡二叉排序树的平衡二叉排序树的 Adelson 算法的本质特点：算法的本质特点： 以插入为例：以插入为例： 在左图所示的平衡二叉排序树中插入数据场为在左图所示的平衡二叉排序树中插入数据场为 2 的结点。的结点。 插入之后仍应保持平衡二叉排序树的性质不变。插入之后仍应保持平衡二叉排序树的性质不变。141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点关键：将导致出现关键：将导致出现危机结点的情况危机结点的情况全部分析全部分析清除，就可以使得平衡二叉排序树的

25、性质保清除，就可以使得平衡二叉排序树的性质保持不变！持不变！14932528635360501718730+1+1-1-1-100000001200小学教育 查找 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：1、LL 情况：（情况：（LL：表示新插入结点在危机结点的表示新插入结点在危机结点的左子树左子树的的左子树上左子树上）AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：高度为 h + 1 中序序列：中序序列：ABBLB

26、RAR改组后：高度为改组后：高度为 h + 1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平衡度为平衡度为 0AB小学教育 查找 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：2、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的左子树左子树的的右子树上右子树上） 情况情况A：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前： 高度为高度为 h + 1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,-

27、1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：改组后： 高度为高度为 h + 1 中序序列：中序序列：ABBLARCCLCRA小学教育 查找 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：2、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的左子树左子树的的右子树上右子树上） 情况情况B：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前： 高度为高度为 h + 1 中序

28、序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 +1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACRh-1CLh-2+10ABBLARCCRCL改组后：改组后： 高度为高度为 h + 1 中序序列：中序序列：AABBLARCCRCL小学教育 查找 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：2、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的左子树左子树的的右子树上右子树上） 情况情况C：AB+10+2-1LR 改组改组危机结点危机结

29、点改组前：改组前： 高度为高度为 2 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,0CBC0ABCA新插入结点新插入结点ABC改组后：改组后： 高度为高度为 2 中序序列：中序序列：CB0A00 四种情况的区分：四种情况的区分： 如果如果 的平衡度为的平衡度为1 则为则为 LL型改组；型改组； 否则为否则为 LR型改组：若型改组：若 的平衡度为的平衡度为1、1 、0 ；则分别为；则分别为 LRA、LRB、LRC型改组。型改组。BC小学教育 查找 右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析：右改组（新插入结点出现在危机结点的右子树上进行的调整）的

30、情况分析：1、RR 情况：（情况：（RR：表示新插入结点在危机结点的表示新插入结点在危机结点的右子树右子树的的右子树上右子树上） 处理图形和处理图形和 LL 镜象相似镜象相似2、RL 情况：（情况：（RL：表示新插入结点在危机结点的表示新插入结点在危机结点的右子树右子树的的左子树上左子树上） A、处理图形和处理图形和 LRA 镜象相似镜象相似 B、处理图形和处理图形和 LRB 镜象相似镜象相似 C、处理图形和处理图形和 LRC 镜象相似镜象相似 删除情况：略删除情况：略 程序实现：略程序实现：略小学教育 查找8.6、B_ 树和树和 B+ 树树 1、为什么采用、为什么采用B_ 树和树和 B+ 树

31、：树：大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。在在 1970 年由年由 R bayer 和和 E macreight 提出用提出用B_ 树作为索引组织文件。提高访问速度、减少时间。树作为索引组织文件。提高访问速度、减少时间。内存内存E.G: 用二叉树组织文件，当文件用二叉树组织文件，当文件的记录个数为

32、的记录个数为 100，000时，要找时，要找到给定关键字的记录，需访问外存到给定关键字的记录，需访问外存17次（次（log100,000）,太长了！太长了！502510751535609020304055708095索索引引文文件件数数据据文文件件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件、数据文件存在盘上文件访问示意图：索引文件、数据文件存在盘上小学教育 查找2、B_ 树是一种多分支数，首先介绍树是一种多分支数，首先介绍 m 阶阶 B_ 树：树： 定义：定义： m 阶阶 B_ 树满足或空，或：树满足或空，或：A、根结点要么是叶子，要么至少有两个儿子根结点要么是叶子，要么至少

33、有两个儿子B、除根结点和叶子结点之外，每个结点的儿子个数为除根结点和叶子结点之外，每个结点的儿子个数为: m/2 = s = mC、有有 s 个儿子的非叶结点具有个儿子的非叶结点具有 n = s 1 个关键字，即个关键字，即: s = n + 1 这些结点的数据信息为：这些结点的数据信息为： （n, A0, K1, R1, A1, K2, R2, A2, Kn, Rn, An） 这里：这里：n: 关键字的个数关键字的个数 A0： K1 且且 Kn 的结点的地址（指在该的结点的地址（指在该 B_ 树中）树中） 注意：注意：K1 =K2 = . = KnD、所有的叶子结点都出现在同一层上，不带信息

34、（可认为外部结点或失败结点）。所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。小学教育 查找例如：例如：m = 4 阶阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个树。除根结点和叶子结点之外，每个结点的儿子个数数至少为至少为 m/2 = 2 个；结点的关键字个数至少为个；结点的关键字个数至少为 1 。该。该 B_ 树的深树的深度为度为 4。叶子结点都在第叶子结点都在第 4 层上。层上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层

35、)小学教育 查找B_ 树和树和 B+ 树树 3、B_ 树的查找代价分析：树的查找代价分析： 查找过程，类似于二叉树的查找。如查找关键字为查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。的记录。 从根开始查找，如果从根开始查找，如果 Ki = KEY 则查找成功，则查找成功，Ri 为关键字为为关键字为 KEY 的记录的地址。的记录的地址。 若若 Ki KEY Ki+1; 查找查找 Ai 指向的结点指向的结点 若若 KEY Kn; 查找查找 An指向的结点指向的结点 若若 找到叶子，则查找失败。找到叶子，则查找失败。注意：每次查找将去掉注意：每次查找将去掉 （s-1）/s 个分支，比

36、二分查找快得多。个分支，比二分查找快得多。 设关键字的总数为设关键字的总数为 N ，求求 m阶阶 B_ 树的最大层次树的最大层次 L。层次层次结点数结点数关键字的个数（最少）关键字的个数（最少）111222（ m/2 -1）3 2（ m/2 ） 2（ m/2 ） （ m/2 -1）4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1）L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1）L+1 2（ m/2 ）L-1所以，所以，N=1 2（ m/2 -1） +.+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1故：故：Llog （N+1）/2

37、）+ 1小学教育 查找B_ 树和树和 B+ 树树 3、B_ 树的查找代价分析：树的查找代价分析： 设关键字的总数为设关键字的总数为 N ，求求 m阶阶 B_ 树的最大层次树的最大层次 L。故：故：Llog m/2 （N+1）/2）+ 1设设 N 1000，000 且且 m256 ，则则 L m-1, 则该结点满。必须分裂成两个结点。否则不满结束。则该结点满。必须分裂成两个结点。否则不满结束。如结点原为：如结点原为： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)）插入一个关键字之后变为：插入一个关键字之后变为： （m, A0, (K1, A1), (K2,

38、 A2), (Km, Am)）该结点将进行分裂：该结点将进行分裂： . (K m/2 , p ) .（m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。PP(K m/2 , p ) 数据数据项插入上层结点之项插入上层结点之中中小学教育 查找B_ 树和树和 B+ 树树 例如：例如：3 阶阶 B_ 树的插入操作。树的插入操作。m=3, m/2 - 1 =

39、 1; 至少至少 1 个关键字，二个儿子结点。个关键字，二个儿子结点。3，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入插入小学教育 查找B_ 树和树和 B+ 树树 5、B_ 树的删除操作树的删除操作1、查找具有给定键值的关键字、查找具有给定键值的关键字 Ki 2、如果如果 在第在第 L 层，可直接删除（注意：第层，可直接删除（注意：第 L+1 层为叶子结点），转层为叶子结点），转 4 。

40、3、否则，则首先生成、否则，则首先生成 “替身替身”。用。用 的右子树中的最左面的结点的关键字值，即的右子树中的最左面的结点的关键字值，即 处于第处于第 L 层上的最层上的最小小 关键字值取代关键字值取代 。然后，删除第。然后，删除第 L 层上的该关键字。层上的该关键字。4、从第、从第 L 层开始进行删除。层开始进行删除。 A、不动：若删除关键字值的那个结点的关键字的个数仍处于、不动：若删除关键字值的那个结点的关键字的个数仍处于 m/2 -1和和 m-1之间。则结束。之间。则结束。 B、借：若删除关键字值的那个结点的关键字的个数原为、借：若删除关键字值的那个结点的关键字的个数原为 m/2 -1

41、 。而它们的左或右邻居结。而它们的左或右邻居结 点的关键字的个数点的关键字的个数 m/2 -1 ; 则借一个关键字过来。处理结束。则借一个关键字过来。处理结束。 C、并：若该结点的左或右邻居结点的关键字的个数为、并：若该结点的左或右邻居结点的关键字的个数为 m/2 -1 ; 则执行合并结点的操作。则执行合并结点的操作。如结点原为：如结点原为： （ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1L 第第 L 层：找到了被删结点的替身。层：找到了被删结点的替身。小学教育 查找B_ 树和树和 B+ 树树 例如：

42、例如：3 阶阶 B_ 树的删除操作。树的删除操作。m=3, m/2 - 1 = 1; 至少至少 1 个关键字，二个儿子结点。个关键字，二个儿子结点。3244553 90371005061，70被删关键字被删关键字3244561 90371005370借：向被删结点方向旋转借：向被删结点方向旋转假定再删除该关键字假定再删除该关键字32445 903710061，70假定再删除该关键字假定再删除该关键字3，2445 9010061，703，24 45 9010061，70并并并并并并并：和父结点的一个关键字、及邻居合并。有可并：和父结点的一个关键字、及邻居合并。有可能进行到根，使能进行到根，使B_

43、 树的深度降低一层！树的深度降低一层！小学教育 查找小学教育 查找9.3 哈希表哈希表基本思想：基本思想：在记录的存储地址和它的关键字之间建在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法存取就能得到所查元素的查找方法定义定义哈希函数哈希函数在记录的在记录的关键字关键字与记录的与记录的存储地址存储地址之间之间建立的一种对应关系叫建立的一种对应关系叫 哈希函数是一种映象，是从关键字空间到存储地址哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象空间的一种映象哈希函数可写成：哈希函数可写

44、成：addr(ai)=H(ki)ai是表中的一个元素是表中的一个元素addr(ai)是是ai的存储地址的存储地址ki是是ai的关键字的关键字关键字关键字集合集合存储地址存储地址集合集合hash小学教育 查找哈希表哈希表应用哈希函数，由记录的关键字确定记录在应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫表中的地址，并将记录放入此地址，这样构成的表叫 哈希查找哈希查找又叫散列查找，利用哈希函数进行查找的又叫散列查找，利用哈希函数进行查找的过程叫过程叫 例例 30个地区的各民族人口统计表个地区的各民族人口统计表编号编号 地区别地区别 总人口总人口 汉族汉族 回族

45、回族.1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造构造哈希函数：哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区以地区别作关键字，取地区名称第一个拼音字母的在字母表名称第一个拼音字母的在字母表中序号作哈希函数：中序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19小学教育 查找从例子可见：从例子可见：哈希函数只是一种映象，所以哈希函数的哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可数值都落在表长允许的范围之

46、内即可冲突冲突：key1 key2，但但H(key1)=H(key2)的现象叫的现象叫同义词同义词：具有相同函数值的两个关键字，：具有相同函数值的两个关键字，叫该哈希函数的叫该哈希函数的哈希函数通常是一种压缩映象，所以冲突哈希函数通常是一种压缩映象，所以冲突不可避免不可避免，只能尽量减少；同时，冲突发，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法生后，应该有处理冲突的方法小学教育 查找9.3.2 哈希函数的构造方法哈希函数的构造方法直接定址法直接定址法构造：取关键字或关键字的某个线构造：取关键字或关键字的某个线性函数作哈希地址，即性函数作哈希地址，即H(key)=key 或或 H(ke

47、y)=akey+b特点特点直接定址法所得地址集合与关键字集直接定址法所得地址集合与关键字集合大小相等，不会发生冲突合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少实际中能用这种哈希函数的情况很少小学教育 查找数字分析法数字分析法构造：对关键字进行分析，取关键字的构造：对关键字进行分析，取关键字的若干位或若干位组合作哈希地址若干位或若干位组合作哈希地址适于关键字位数比哈希地址位数大，且适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况可能出现的关键字事先知道的情况小学教育 查找例例 有有80个记录，关键字为个记录，关键字为8位十进制数，哈位十进制数，哈希地址为希地址为2位十

48、进制数位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析：分析： 只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位 与另两位的叠加作哈希地址与另两位的叠加作哈希地址小学教育 查找平方取中法平方取中法构造：取关键字平方后中间几位作构造：取关键字平方后中间几位作哈希地址哈希地址适于不知道全部关键字情况适于

49、不知道全部关键字情况小学教育 查找折叠法折叠法构造：将关键字分割成位数相同的几部分，然后取这几构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址部分的叠加和（舍去进位）做哈希地址种类种类移位叠加：将分割后的几部分低位对齐相加移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情适于关键字位数很多，且每一位上数字分布大致均匀情况况例例 关键字为关键字为 ：0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 00 4

50、1 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加小学教育 查找除留余数法除留余数法构造：取关键字被某个不大于哈希表表长构造：取关键字被某个不大于哈希表表长m的的数数p除后所得余数作哈希地址，即除后所得余数作哈希地址，即H(key)=key MOD p，p m特点特点简单、常用，可与上述几种方法结合使用简单、常用，可与上述几种方法结合使用p的选取很重要；的选取很重要；p选的不好，容易产生同义词选的不好，容易产生同义词随机数法随机数法构造：取关键字的随机函数值作哈希地址，即构造：取关键字的随机函数值作哈

51、希地址，即H(key)=random(key)适于关键字长度不等的情况适于关键字长度不等的情况小学教育 查找选取哈希函数，考虑以下因素：选取哈希函数，考虑以下因素：计算哈希函数所需时间计算哈希函数所需时间关键字长度关键字长度哈希表长度（哈希地址范围）哈希表长度（哈希地址范围）关键字分布情况关键字分布情况记录的查找频率记录的查找频率小学教育 查找9.3.3 9.3.3 处理冲突的方法处理冲突的方法开放定址法开放定址法方法：当冲突发生时，形成一个探查序列；方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的

52、记录放到置（开放的地址），将发生冲突的记录放到该地址中，即该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(k m-1)其中：其中：H(key)哈希函数哈希函数 m哈希表表长哈希表表长 di增量序列增量序列小学教育 查找di增量序列增量序列(有三种取法有三种取法)线性探测再散列：线性探测再散列：di=1,2,3,m-1二次探测再散列：二次探测再散列：di=1,-1,2,-2,3,k(k m/2)伪随机探测再散列：伪随机探测再散列：di=伪随机数序列伪随机数序列小学教育 查找例例 表长为表长为11的哈希表中已填有关键字为的哈希表中已填有关键字为17，60，29的记录，的记录，

53、H(key)=key MOD 11,现有第现有第4个记录，其关键字为个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中按三种处理冲突的方法，将它填入表中(1) H(38)=38 MOD 11=5 冲突冲突 H1=(5+1) MOD 11=6 冲突冲突 H2=(5+2) MOD 11=7 冲突冲突 H3=(5+3) MOD 11=8 不冲突不冲突 (2) H(38)=38 MOD 11=5 冲突冲突 H1=(5+1) MOD 11=6 冲突冲突 H2=(5 -1) MOD 11=4 不冲突不冲突(3) H(38)=38 MOD 11=5 冲突冲突 设伪随机数序列为设伪随机数序列为9，则

54、：，则： H1=(5+9) MOD 11=3 不冲突不冲突0 1 2 3 4 5 6 7 8 9 1060 17 29 383838小学教育 查找再哈希法再哈希法方法：构造若干个哈希函数，当发生方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,k其中：其中：Rhi不同的哈希函数不同的哈希函数特点：计算时间增加特点：计算时间增加链地址法链地址法方法：将所有关键字为同义词的记录方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存储在一个单链表中，并用一维数组存放头指针存放头指针小学教育 查找例例 已知一

55、组关键字已知一组关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函数为：哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14681920231112779558410小学教育 查找哈希查找过程及分析哈希查找过程及分析哈希查找过程哈希查找过程给定给定k值值计算计算H(k)此地址为空此地址为空关键字关键字=k查找失败查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiYNYN小学教育 查找哈希查找分析哈希查找分析哈希查找过程仍是一个给

56、定值与关键哈希查找过程仍是一个给定值与关键字进行比较的过程字进行比较的过程评价哈希查找效率仍要用评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关哈希查找过程与给定值进行比较的关键字的个数取决于：键字的个数取决于：哈希函数哈希函数处理冲突的方法处理冲突的方法哈希表的填满因子哈希表的填满因子 =表中填入的记录数表中填入的记录数/哈希表长度哈希表长度小学教育 查找例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：哈希函数为：H(key)=key MOD 13, 哈哈希表长为希表长为m=16， 设每个记录的查找概率相等设

57、每个记录的查找概率相等 (1) 用线性探测再散列处理冲突，即用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m小学教育 查找0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 1 68 27 55 19 20 84 79 23 11 10H(55)=3 冲突，冲突，H1=(3+1)MOD16=4 冲突，冲突，H2=(3+2)MOD16=5H(79)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4 冲突，冲突，H4=(1+4)MOD16=5 冲突，冲突，H5=(1

58、+5)MOD16=6 冲突，冲突，H6=(1+6)MOD16=7 冲突，冲突，H7=(1+7)MOD16=8 冲突，冲突，H8=(1+8)MOD16=9ASL=(1*6+2+3*3+4+9)/12=2.5H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，冲突，H1=(6+1)MOD16=7 冲突，冲突，H2=(6+2)MOD16=8H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4H(11)=11H

59、(10)=10 冲突，冲突，H1=(10+1)MOD16=11 冲突，冲突，H2=(10+2)MOD16=12(19,14,23,1,68,20,84,27,55,11,10,79)H(key)=key MOD 13 Hi=(H(key)+di) MOD m小学教育 查找(2) 用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(19,14,23,1,68,20,84,27,55,11,10,79)小学教育 查找哈希查找算法实现哈希查找算法实现

60、用线性探测再散列法处理冲突用线性探测再散列法处理冲突实现实现查找过程：同前查找过程：同前删除：只能作标记，不能真正删除删除：只能作标记，不能真正删除插入：遇到空位置或有删除标记的位置就可以插入插入：遇到空位置或有删除标记的位置就可以插入算法描述：算法描述：用链表处理冲突算法用链表处理冲突算法小学教育 查找#define M 100int h(int k) return(k%97);int slbxxcz(int t,int k) int i,j=0; i=h(k); while(jM)&(t(i+j)%M!=k)&(t(i+j%M!=0) j+; i=(i+j)%M; if(ti=k) ret

61、urn(i); else return(-1);小学教育 查找int slbxxcr(int t,int k) int i,j=0; i=h(k); while(j0) j+; if(j=M) return(0); i=(i+j)%M; if(ti=0) ti=k; return(1); if(ti=k) return(1);小学教育 查找int slbxxsc(int t,int k) int i,j=0; i=h(k); while(jdata= =x) /查找成功 return BST; else if (BST-datax) /进入左子树查找 return find ( BST-lef

62、t,x); else /进入右子树查找 return find (BST-right,x); 小学教育 查找二叉排序树查找的性能分析二叉排序树查找的性能分析在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。小学教育 查找平衡二叉树查找平衡二叉树查找若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深

63、度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。小学教育 查找小学教育 查找非平衡二叉树的平衡处理若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与扦入点最近的、而平衡因子又比1大或比-1小的结点。小学教育 查找（1）LL型型 的处理的处理(左左型左左型)在C的左孩子B上扦入一个左孩子结点A，使C的平衡因子由1变成了2，成为不平衡的二叉树序

64、树。这时的平衡处理为：将C顺时针旋转，成为B的右子树，而原来B的右子树则变成C的左子树，待扦入结点A作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子)小学教育 查找（2）LR型的处理型的处理(左右型左右型)在C的左孩子A上扦入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将B变到A与C 之间，使之成为LL型，然后按第(1)种情形LL型处理。小学教育 查找（3）RR型的处理型的处理(右右型右右型)在A的右孩子B上扦入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的

65、左子树则变成A的右子树，待扦入结点C成为B的右子树。小学教育 查找（4）RL型的处理型的处理(右左型右左型)在A的右孩子C上扦入一个左孩子B，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将B变到A与C之间，使之成为RR型，然后按第(3) 种情形RR型处理。小学教育 查找给定一个关键字序列4,5,7,2 ,1,3,6，试生成一棵平衡二叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。小学教育 查找小学教育 查找小学教育 查找平衡二叉树的查找及性能分析 平衡二

66、叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。 小学教育 查找对例8-2给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-14，得到的二叉排序树见图8-15。 小学教育 查找从图8-15的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+

67、3+4)/7=18/72.57。从图8-14的平衡二叉树可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。 小学教育 查找学习要点1、熟练掌握顺序表和有序表的查找方法，并能灵活应用。2、熟练掌握二叉排序树和平衡二叉排序树的构造方法和查找方法。3、熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的区别。4、掌握计算各种查找方法在等概率情况下查找成功时的平均查找长度。小学教育 查找作业： 9.8 9.3 9.4 9.7 9.10 9.18 9.21 9.23 9.26 9.31 9.32 9.35 9.36 9.37小学教育 查找