算法与数据结构查找精选PPT.ppt

《算法与数据结构查找精选PPT.ppt》由会员分享，可在线阅读，更多相关《算法与数据结构查找精选PPT.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、BUPT关于算法与数据关于算法与数据结构构查找找第1页，讲稿共70张，创作于星期二BUPT SCSTBUPT8.1 基本概念与术语基本概念与术语查找表查找表 同一类型的记录(数据元素)的集合集合。查找查找 指定某个值，在查找表中确定是否存在一个记录，该记录的关键字关键字等于给定值。关键字关键字 记录(数据元素)中的某个数据项的值。主关键字主关键字该关键字可以唯一地标识一个记录。次关键字次关键字该关键字不能唯一标识一个记录。静态查找表静态查找表对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表动态查找表在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。查找成功查找成功查找

2、表中存在满足查找条件的记录。查找不成功查找不成功 查找表中不存在满足查找条件的记录。第2页，讲稿共70张，创作于星期二BUPT SCSTBUPT内查找内查找 整个查找过程都在内存中进行。外查找外查找在查找过程中需要访问外存。平均查找长度平均查找长度ASL查找方法时效的度量为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：n：记录的个数pi：查找第i个记录的概率，(不特别声明时认为等概率pi=1/n)ci：找到第i个记录所需的比较次数约定：无特殊说明，一般默认关键字的类型为整型约定：无特殊说明，一般默认关键字的类型为整型第3页，讲稿共70张，创作于星期二

3、BUPT SCSTBUPT8.2 顺序表的查找顺序表的查找 0 1 n-1 n r0.n a0 a1 an-1 rn.key=K算法描述算法描述int seqsearch(int*a,const int n,const int K)int i=0;an=K;while(ai!=K)i+;return i;第4页，讲稿共70张，创作于星期二BUPT SCSTBUPT程序设计技巧程序设计技巧设置监视哨，提高算法效率。性能分析性能分析v空间：一个辅助空间。v时间：1)查找成功时的平均查找长度设表中各记录查找概率相等ASLs(n)=(1+2+.+n)/n=(n+1)/22)查找不成功时的平均查找长度A

4、SLf=n+1算法特点算法特点v算法简单，对表结构无任何要求vn很大=查找效率较低v改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。第5页，讲稿共70张，创作于星期二BUPT SCSTBUPT8.3 二分查找二分查找满足满足 ri.key ri+1.key,0 i n-1仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。折半折半(二分二分)查找法查找法12345678910110513192137566475808892lowmidhigh=(low+high)/2K=21lhmK=85lhm111611161537119454101110109第6

5、页，讲稿共70张，创作于星期二BUPT SCSTBUPT算法描述算法描述int binsearch(int K,int v,int n)int low,high,mid;low=1;high=n;while(low=high)mid=(low+high)/2;if(K vmid)low=mid+1;else/*找到了匹配的值找到了匹配的值*/return mid;return-1;/*没有查到没有查到*/第7页，讲稿共70张，创作于星期二BUPT SCSTBUPT性能分析性能分析h=log2n+1同完全二叉树，二叉树性质4成功查找时的平均查找长度（等概率）：ASLs=例：ASLS=(1*1+2

6、*2+3*4+4*4)/11=3不成功查找时的查找长度：h-1或h次 -13-46-79-101-22-34-55-67-88-910-1111-639147 102581112h判定树判定树（描述查找过程的二叉树）外结点内结点lc,flag)；/中序遍历左子树if(pre=NULL)pre=t；/中序的第一个结点不判断elseif(pre-datadata)pre=t；/前驱指针指向当前结点elseflag=FLASE；/不是完全二叉树JudgeBST(t-rc,flag)；/中序遍历右子树第19页，讲稿共70张，创作于星期二BUPT SCSTBUPT方法2：照定义，二叉排序树的左右子树都是

7、二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。bool JudgeBST(BTreet)if(t=NULL)return TRUE；if(JudgeBST(t-lc)&JudgeBST(t-rc)m=max(t-llink)；n=min(t-rlink)；/左子树中最大值和右子树中最小值return(t-datam&t-datarc！=null)p=p-rc；return p-data；int min(BTreep)/求右子最小值if(p=NULL)return maxint；else while(p-lc!=NULL)p=p-l

8、c；return p-data；第20页，讲稿共70张，创作于星期二BUPT SCSTBUPT在二叉排序树上的操作在二叉排序树上的操作1.查找查找例例K=28K=32bst45241228bst455390241228325390查找步骤：若根结点的关键字值等于查找的关键字，成功。查找步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查其左子树。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字值，查其右子树。若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。在左右子树上的操作类似。第21页，讲稿共70张，创作于星期二BUPT SCSTBUPT

9、BitreeSearchBST(BiTreeT,KeyTypekey)/在二叉分类树查找关键字之值为key的结点，找到返回该结/点的地址，否则返回空。T为根结点的指针。if (T=NULL)|(key=T-data)return(T);else if(keydata.key)return(SearchBST(T-lc,key);else return(SearchBST(T-rc,key);查找算法查找算法第22页，讲稿共70张，创作于星期二BUPT SCSTBUPT2.插入插入首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树

10、为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。注意：新插入的结点总是叶子结点。3.生成生成算法步骤算法步骤 反复执行以下操作a.读入一个记录，设其关键字为K；b.调用查找算法，确定插入位置；c.调用插入算法，实施插入结点的操作；第23页，讲稿共70张，创作于星期二BUPT SCSTBUPT例：将序列122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099第24页，讲稿共70张，创作于星期二BUPT SCSTBUPT4.删除删除依据被删除结点p的不同情况分析：1.p

11、是叶子结点：修改其双亲指针即可2.p只有左孩子：用p的左子树代替以p为根的子树p只有右孩子：用p的右子树代替以p为根的子树3.p有两个孩子：找到p的中序后继(或前趋)结点q，q的数据复制给p，删除只有右子(或左子)/无孩子的q第25页，讲稿共70张，创作于星期二BUPT SCSTBUPT例：(1)(2)(2)(3)5320901050869541241528891304539878992第26页，讲稿共70张，创作于星期二BUPT SCSTBUPTvoid Delete(BSTree T,keytype X)/在二叉排序树T上，删除为X的结点。BSTreef,p=T;while(p&p-key

12、!=X)/查找值为X的结点if(p-keyX)f=p;p=p-lc;/f为p的双亲elsef=p;p=p-rc;if(p=NULL)printf(“无关键字为X的结点n”);exit(0);if(p-lc=NULL)/被删结点无左子树if(f-lc=p)f-lc=p-rc;/将被删结点的右子树接到其双亲上elsef-rc=p-rc;else/被删结点有左子树q=p;s=p-lc;while(s-rc!=NULL)/查左子树中最右下的结点（中序最后结点）q=s;s=s-rc;p-key=s-key;/结点值用其左子树最右下的结点的值代替if(q=p)p-lc=s-lc;/被删结点左子树的根结点无

13、右子女elseq-rc=s-lc;/s是被删结点左子树中序序列最后一个结点free(s);第27页，讲稿共70张，创作于星期二BUPT SCSTBUPT4.性能分析性能分析v给定树的形态，等概率查找成功时的ASL=ci/n最差(单支树)：(n+1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：1+4log2nv关键字有序出现时，构造出“退化”的二叉排序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树第28页，讲稿共70张，创作于星期二BUPT SCSTBUPT8.7 平衡二叉树平衡二叉树(AVL树树)1.定义定义平衡二叉树平衡二叉树或者是空树，或者是满足如下性质的二

14、叉排序树：1)它的左、右子树的高度之差的绝对值不超过1；2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子平衡因子：该结点的左子树高度减去右子树的高度。平衡二叉树非平衡二叉树302010252235383020353233001-10-1100-12-2平衡二叉树：每个结点的平衡因子都为平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉排序树。的二叉排序树。第29页，讲稿共70张，创作于星期二BUPT SCSTBUPT2.结点的存储结构结点的存储结构lcbfkeyotherinforclc：左孩子指针rc：右孩子指针bf：平衡因子key：记录的关键字otherinfo：记录的其

15、它数据成分第30页，讲稿共70张，创作于星期二BUPT SCSTBUPT4.在平衡二叉树上的操作在平衡二叉树上的操作查找查找查找方法同二叉排序树。插入插入 插入新结点之后仍应保持平衡二叉树的性质不变。例平衡二叉树的生成过程15001525-1-2-1000000-1-1001-2-20000-11525353525152515359015253590651525653590第31页，讲稿共70张，创作于星期二BUPT SCSTBUPT调整范围的确定调整范围的确定插入结点后，找到离插入结点最近且平衡因子绝对值超过1的祖先结点（危机节点），则以该危机节点为根的子树将是可能不平衡的最小子树，可将重新

16、平衡的范围局限于这棵子树。调整的类型调整的类型 LL型型-表示新插入结点在危机结点的左子左子的左子树左子树上LR型型-表示新插入结点在危机结点的左子左子的右子右子树上RL型型-表示新插入结点在危机结点的右右子子的左子树左子树上RR型型-表示新插入结点在危机结点的右右子子的右右子树子树上第32页，讲稿共70张，创作于星期二BUPT SCSTBUPT调整的方法调整的方法LL型平衡旋转型平衡旋转一次顺时针旋转AB+1h-10+2+1hh-1h-1LL 型调整型调整BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点调整前：高度为调整前：高度为 h+1 中序序列：中序序列：ABBLBRAR调

17、整后：高度为调整后：高度为 h+1 中序序列：中序序列：ABBLBR注意：调整后注意：调整后 平衡因子为平衡因子为 0ABAR第33页，讲稿共70张，创作于星期二BUPT SCSTBUPTLR型平衡旋转型平衡旋转一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR 型调整型调整BLAR危机结点危机结点CBCCLCRh-2h-2h-10+1CB0h-1BLARACRh-2CLh-1-10ABBLARCCLCR调整后：调整后：高度为高度为 h+1 中序序列：中序序列：ABBLARCCLCRA调整前：调整前：高度为高度为 h+1 中序序列：中序序列：h-1情形情形A注意：调整后注意：调整

18、后 平衡因子为平衡因子为+1,0,0第34页，讲稿共70张，创作于星期二BUPT SCSTBUPTLR型平衡旋转型平衡旋转一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR 型调整型调整BLAR危机结点危机结点调整前：调整前：高度为高度为 h+1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2+10ABBLARCCRCL调整后：调整后：高度为高度为 h+1 中序序列：中序序列：AABBLARCCRCL情形情形B第35页，讲稿共70张，创作于星期二BUPT SCSTBUPT注

19、意：调整后注意：调整后 平衡因子为平衡因子为 0,0,0LR型平衡旋转型平衡旋转一次逆时针旋转+一次顺时针旋转AB+10+2-1LR 型调整型调整危机结点危机结点调整前：调整前：高度为高度为 2 中序序列：中序序列：CBC0ABCA新插入结点新插入结点ABC调整后：调整后：高度为高度为 2 中序序列：中序序列：ca0b00情形情形C第36页，讲稿共70张，创作于星期二BUPT SCSTBUPTRR型平衡旋转型平衡旋转一次逆时针旋转AB-1h-10-2-1hh-1h-1RR 型调整型调整BLBRALBA0h0h-1h-1BLAL危机结点危机结点调整前：高度为调整前：高度为 h+1 中序序列：中序

20、序列：BAALBLBR调整后：高度为调整后：高度为 h+1 中序序列：中序序列：注意：调整后注意：调整后 平衡因子为平衡因子为 0ABBRBAALBLBR第37页，讲稿共70张，创作于星期二BUPT SCSTBUPTRL型平衡旋转型平衡旋转一次顺时针旋转+一次逆时针旋转AALCRCLBRALCRCLBRALCLBRCRBCABCACB-100h-1h-2h-1 h-211(-1)00(1)-1(0)危机结点危机结点第38页，讲稿共70张，创作于星期二BUPT SCSTBUPT删除删除（思路同插入）v将删除结点q转化为q最多有一个孩子的情形，即若q有两个孩子，则以其中序前驱/后继结点r取代它，删

21、除r；v若树的平衡性被破坏，利用单一/双重旋转恢复。性能性能定理：一个具有n个结点的平衡二叉树形，其高度h为log2(n+1)h1.4404log2(n+2)-0.328结论：最坏情况下，AVL树的高度约为1.44log2n，而完全平衡的二叉树高度约为log2n，因此AVL树是接近最优的，其平均查找长度与log2n同数量级。第39页，讲稿共70张，创作于星期二BUPT SCSTBUPT8.7 B+树与树与B-树树采用B+与B-树的意义大量数据存放在外存中，由于是海量数据，不可能一次调入内存。因此，要多次访问外存，速度慢。所以，主要矛盾变为减少访外次数。内存内存第40页，讲稿共70张，创作于星期

22、二BUPT SCSTBUPT用用二叉树组织文件，需访问外存次数太多。如：当文件的记录个数为100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！502510751535609020304055708095索引索引文件文件数数据据文文件件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件存在内存、数据文件存在盘上文件访问示意图：索引文件存在内存、数据文件存在盘上第41页，讲稿共70张，创作于星期二BUPT SCSTBUPTB-树树B-树是一种平衡的多路查找树。应用于文件系统。1.定义定义一棵m 阶阶B-树树，或为空树，或为满足下列特性的m叉树：1、

23、树中每个结点最多有m棵子树；2、若根结点不是叶子结点，则最少有两两棵子树；3、除根之外的所有非终端结点最少有 m/2 棵子树；4、所有非终端结点包含（n,A0,K1,A1,K2,Kn,An）信息数据；其中n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。5、所有叶子结点在同一层上，且不带信息。第42页，讲稿共70张，创作于星期二BUPT SCSTBUPT例如：m=4阶B_树。除根结点和叶子结点之外，每个结点的儿子个数至少为m/2=2个；结点的关键字个数至少为1。该B_树的深度为4。叶子结点都在第4层上。1，993，47，58，641，391，271，112，43，781，181，35F

24、FFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层)m/2 m棵子树棵子树叶第43页，讲稿共70张，创作于星期二BUPT SCSTBUPT2.B-树结点结构树结点结构(n,A0,K1,A1,K2,A2,.,Kn,An)n:关键字的个数A0：K1且Kn的结点的地址（指在该B_树中）K1=K2=.=Kn第44页，讲稿共70张，创作于星期二BUPT SCSTBUPT127阶B-树中每个结点最多有_个关键字；除根结点外所有非终端结点至少有_棵子树；65阶B+树中除根结点外所有结点至少有_个关键字；最多有_棵子树。高度为5（除叶子层之外）的三阶B-树至少有

25、_个结点。31126643365思考：高度为思考：高度为h的的m阶阶B-树（除叶子层）至少有多少个结点？树（除叶子层）至少有多少个结点？第45页，讲稿共70张，创作于星期二BUPT SCSTBUPT3.B-树查找过程树查找过程类似于二叉树的查找。如查找关键字为KEY的记录。从根开始查找，如果Ki=KEY则查找成功。若KiKEYKi+1;查找Ai指向的结点若KEYKn;查找An指向的结点若找到叶子，则查找失败。第46页，讲稿共70张，创作于星期二BUPT SCSTBUPT设关键字的总数为N，求m阶B_树的最大层次L。层次层次 结点数结点数关键字的个数（最少）关键字的个数（最少）1 112 22(

26、m/2-1)3 2(m/2)2(m/2)(m/2-1)4 2(m/2)22(m/2)2(m/2-1)L 2(m/2)L-22(m/2)L-2(m/2-1)L+12(m/2)L-1所以，N=2(m/2)L-1-1故：Llogm/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,A2,Km,Am)该结点以K m/2 为界，进行分裂：.(K m/2 ,p).(m/2-1,A0,(K1,A1)(K

27、m/2-1,A m/2-1)(m-m/2,A m/2,K m/2+1 Km,Am)生成新结点p,将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。(K m/2 ,p)数据项插入上数据项插入上层结点之中层结点之中PP第48页，讲稿共70张，创作于星期二BUPT SCSTBUPT例：例：3 阶阶 B_ 树的插入树的插入key=73，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插

28、入插入第49页，讲稿共70张，创作于星期二BUPT SCSTBUPT5.B-树删除过程树删除过程1、查找具有给定键值的关键字Ki2、如果在第L层，可直接删除（注意：第L+1层为叶子结点），转4。3、否则，则首先生成“替身”。用该关键字的右边子树中的最左面的结点的关键字取代。然后，删除第L层上的该关键字。4、从第L层开始进行删除。A、不动：若删除关键字值的那个结点的关键字的个数仍处于m/2-1和m-1之间。则结束。B、借：若删除关键字值的那个结点的关键字的个数原为m/2-1。而它们左右兄弟结点的关键字个数m/2-1;则借一关键字过来，结束。C、并：若该结点的左右兄弟结点的关键字的个数为m/2-1

29、;则执行合并结点的操作。如结点原为：（.(Ki,Ai),(Ki+1,Ai+1),.）（A0,(K1,A1)）（A0,(K1,A1)）K1 第第 L 层：找到了被删结点的替身。层：找到了被删结点的替身。第50页，讲稿共70张，创作于星期二BUPT SCSTBUPT例如：3阶B_树的删除操作。3244553 90371005061，70被删关键字被删关键字3244561 90371005370借：向被删结点方向旋转借：向被删结点方向旋转假定再删除该关键字假定再删除该关键字32445 903710061，703，2445 9010061，703，24 45 9010061，70并并并并并并并：和父结

30、点的一个关键字、及兄弟合并。有可能进行并：和父结点的一个关键字、及兄弟合并。有可能进行到根，使到根，使B_ 树的深度降低一层！树的深度降低一层！假定再删除该关键字假定再删除该关键字第51页，讲稿共70张，创作于星期二BUPT SCSTBUPTB+树树B+树是一种B-树的变形树。应用于索引顺序文件系统。1.m阶阶B+树与树与 B-树的不同之处树的不同之处1)有n棵子树的结点中有n个关键字；2)非叶结点可以看成是索引部分索引集索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字3)所有叶子结点中包含了全部关键字的信息及指向这些关键字记录的指针，且叶子结点以关键字大小自小至大顺序链

31、接；数据数据集集第52页，讲稿共70张，创作于星期二BUPT SCSTBUPT结点结构结点结构非叶结点(A1,K1,.,Ai,Ki,.,An,Kn)索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字叶结点全部关键字及指向关键字记录的指针数据集2 15 334 40 47 58 672 79 853 90 96 1052 85 1323 33 67 852 105 1322 114 1324阶B+树rootsqt第53页，讲稿共70张，创作于星期二BUPT SCSTBUPT2.B+树上的基本运算树上的基本运算1)查找查找v方式1：从根结点开始，利用索引集结构，向下查找直到叶子

32、结点v方式2：从最小关键字开始，沿叶结点数据集的链结构顺序查找2)插入插入仅在叶子结点上进行，关键字个数大于m则分裂3)删除删除也仅在叶子结点上进行，关键字个数小于m/2时，需进行合并第54页，讲稿共70张，创作于星期二BUPT SCSTBUPT8.8 哈希表哈希表哈希表的基本思想哈希表的基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，理想状态不经过比较，一次存取就能得到所查元素。术语术语 哈希表哈希表 一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。哈希函数哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。Loc(ri)=H(keyi)冲突冲突 对于k

33、eyikeyj，ij，出现的H(keyi)=H(keyj)的现象。第55页，讲稿共70张，创作于星期二BUPT SCSTBUPT 同义词同义词 在同一地址出现冲突的各关键字。哈希哈希(散列散列)地址地址 根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。装填因子装填因子 表中填入的记录数n和哈希表表长m之比。=n/m设计哈希表的过程设计哈希表的过程1)明确哈希表的地址空间范围。即确定哈希函数的值域。2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。3)设定处理冲突的方法。哈希表bb+(m-1)L第56页，讲稿共70张，创作于

34、星期二BUPT SCSTBUPT哈希函数的基本构造方法哈希函数的基本构造方法构造原则：算法简单，运算量小；均匀分布，减少冲突。1.直接定址法直接定址法H(key)=a*key+ba、b为常数e.g:令：a、b为1，有两个关键字k1,k2值为10、1000；选10、1000作为存放地址。特点：计算简单，冲突最少。2.数字分析法数字分析法/基数转换法基数转换法取关键字在某种进制下的若干数位作为哈希地址。e.g:key=236076基数为10，看成是13进制的。则：(236075)13=841547；选取4154作为散列地址(假设表长m=10000)。第57页，讲稿共70张，创作于星期二BUPT S

35、CSTBUPT3.平方取中法平方取中法取关键字平方后的中间几位作为哈希地址。e.g:(4731)2 =223 82 361；选取；选取 82（假设（假设 m=100）。）。4.随机数法随机数法H(key)=random(key)特点：较适于关键字长度不等时的情况。5.折叠法折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址。e.g:key=381，412，975选取选取 768 或或 570 作为散列地作为散列地址（址（假设假设 m=1000）。）。381 412 9751 768 975 214 381 1 570第58页，讲稿共

36、70张，创作于星期二BUPT SCSTBUPT6.除留余数法除留余数法H(key)=keyMODp(pm)m:哈希表的表长；p:最好为素数最常用，余数总在0p-1之间。通常p选m的最大质数如：m=1024,则p=1019。e.g:选取选取 p 为质数的理由：为质数的理由：设设 key 值都为奇数，选值都为奇数，选 p 为偶数；为偶数；则则 H(key)=key MOD p，结果为奇数，结果为奇数，一半单元被浪费掉。一半单元被浪费掉。设设 key 值都为值都为 5 的倍数，选的倍数，选 p 为为 95；则则 H(key)=key MOD p，结果为：，结果为：0、5、10、15、90奇数。奇数。

37、4/5 的单元被浪费掉。的单元被浪费掉。第59页，讲稿共70张，创作于星期二BUPT SCSTBUPT处理冲突的常用方法处理冲突的常用方法1.开放定址法开放定址法(空缺编址法空缺编址法)Hi=(H(key)+di)MOD m0H(key)m-1i=1,2,.,k(km-1)m:哈希表的表长；di:增量序列1)线性探测再散列线性探测再散列di=1,2,.,m-1缺陷：有聚集(堆积)现象非同义词地址冲突。第60页，讲稿共70张，创作于星期二BUPT SCSTBUPTe.g:假定采用的hashing函数为：H(key)=keyMOD11假定的关键字序列为：17、60、29、38；它们的散列过程为：H

38、(17)=6H(60)=5H(29)=7 H(38)=5012345678910Hashing 表表1760293838当散列当散列 38 时发生冲突，时发生冲突，同同 60 争夺第争夺第 5 个单元个单元解决办法解决办法：探测下一个：探测下一个 空单元空单元Hi=(H(key)+di)MOD 11其中：其中：di 为为 1、210冲突：冲突：初级冲突：不同关键字值的结点得到同初级冲突：不同关键字值的结点得到同一个散列地址。一个散列地址。二次聚集：同不同散列二次聚集：同不同散列地址的结点争夺同一个单元。地址的结点争夺同一个单元。结果：冲突加剧，最坏时可能达到结果：冲突加剧，最坏时可能达到 O(

39、n)级代价。级代价。思考思考：假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行多少次探测？k(k+1)/2第61页，讲稿共70张，创作于星期二BUPT SCSTBUPT2)二次探测再散列二次探测再散列 di=12,-12,22,-22,32,.,k2km/2缺陷：不易探查到整个散列空间。3)伪随机探测再散列伪随机探测再散列 di=伪随机数序列4)双重散列函数探查法双重散列函数探查法 di=i*h1(key)0im-1要求：h1(key)的值与m互素。m为素数时，h1(key)可取1到m-1之间的任何数，建议：h1(key)=keymod(m-2)+1m为2

40、的方幂时，h1(key)可取1到m-1之间的任何奇数注意：开放定址法不宜执行删除操作注意：开放定址法不宜执行删除操作第62页，讲稿共70张，创作于星期二BUPT SCSTBUPT2.再哈希法再哈希法Hi=RHi(key)i=1,2,.,k出现冲突时，采用多个hashing函数计算散列地址，直到找到空单元为止。如：H1(key)=keyMOD11H2(key)=(key+MOD9)1H3(key)=.H10(key)=.第63页，讲稿共70张，创作于星期二BUPT SCSTBUPT3.链地址法链地址法为每个哈希地址建立一个单链表，存储所有具有同义词的记录。100123456789 K1K2K3

41、K4K5K6 同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。冲突处理简单，无堆积现象，平均查找长度较短；较适合于事先无法确定表长的情况；可取1，当结点信息规模较大时，节省空间删除结点的操作易于实现第64页，讲稿共70张，创作于星期二BUPT SCSTBUPT4.建立公共溢出区建立公共溢出区将发生冲突的结点都存放在一个公共溢出区内。通常用于组织存在于外存设备上的数据文件。hash表(基本区)只存放一个记录。发生冲突的记录都存放在公共溢出区内。012345678910 K1K2K3K4K5 K2K3K5K6基本区（基本区（hash表）表）公共溢出区公共溢出

42、区第65页，讲稿共70张，创作于星期二BUPT SCSTBUPT哈希表的查找及其分析哈希表的查找及其分析查找方法同查找方法同 hashing 函数的产生办法。函数的产生办法。例：key=entotrefirefemsekssyvH(key)=2030481解决冲突方法：线性探测再散列012345678ASLs=(1+1+1+2+1+1+5)/7=12/7ASLf=(7+6+5+4+3+2+1+1+8)/9=37/9=7/9entotrefirefemsekssyv第66页，讲稿共70张，创作于星期二BUPT SCSTBUPT平均查找长度与哈希表的装填因子的关系平均查找长度与哈希表的装填因子的关

43、系在一般情况下，冲突的可能性，ASL，但空间的浪费。成功ASL失败ASL线性探测再散列伪随机探测再散列链地址法第67页，讲稿共70张，创作于星期二BUPT SCSTBUPT作业作业1.包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程。）2.试从空树开始，画出按以下次序向3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后B-树的状态。3.已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法，删除p所指结点。typedefstructnodeint data；structno

44、de*left，*right;BiTNode，*BSTree；voidDelete(BSTreeroot,p,fp)第68页，讲稿共70张，创作于星期二BUPT SCSTBUPT4.试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。5.已知含12个关键字的有序表及其相应权值为：123456789101112关键字ABCDEFGHIJKL权值463493261534(1)画出对以上有序表进行折半查找的判定树，求折半查找时查找成功的平均查找长度ASL。(2)若为等概率查找，求折半查找时查找成功的平均查找长度ASL。6.假设一棵平衡二叉树的每个结点都标明了平衡因子bf,试设计一个算法，利用bf值求平衡二叉树的高度。int Height(BSTree t)typedefstructnodeint data；structnode*left，*right;BiTNode，*BSTree；第69页，讲稿共70张，创作于星期二BUPT感谢大家观看第70页，讲稿共70张，创作于星期二