数据结构讲义第9章.ppt

《数据结构讲义第9章.ppt》由会员分享，可在线阅读，更多相关《数据结构讲义第9章.ppt（79页珍藏版）》请在三一办公上搜索。

1、数 据 结 构,吴 润 秀,南昌工程学院,9.1静态查找表9.2动态查找表9.3哈希表,目录,第 九 章 查找,查找的基本概念,查找表(Search Table)：是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。,查找表的操作：1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。3、在查找表中插入一个数据元素；4、从查找表中刪去某个数据元素。静态查找表：对查找表只作前两种操作，这两种操作统称为“查找”的操作，则称此类查找表为静态查找表。动态查找表：在查找过程中同时插入查找表中不

2、存在的数据元素，或者从查找表中删除已存在的某个元素（也即元素集合可以根据情况动态改变），则称此类表为动态查找表。,在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码簿中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读单和含义等等。其中“电话号码簿”和“字典”都可视作是一张查找表。查找：根据给定的某个值，在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功。关键字（关键码）、主关键字、次关键字。举例：P214页

3、书，（查找学生的高考成绩）,如何进行查找呢？其实，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此，对表进行查找的方法取决于表中数据元素依何种关系（这个关系是人为地加上的）组织在一起的。举例：查电话号码时，由于电话号码簿是按用户（集体或个人）的名称（或姓名）分类且依笔划顺序编排，则查找的方法就是先顺序查找待查用户的所属类别，然后在此类中顺序查找，直到找到该用户的电话号码为止。又如，查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。,同样，在计算机中进行查找的

4、方法也随数据结构不同而不同。但前面我们又说到查找表中的数据元素之间存在着完全松散的关系，这给我们查找带来不便。为此，需在数据元素之间人为地加上一些关系，以例按某种规则进行查找，即以另一种数据结构来表示查找表。,一些约定：典型的关键字类型说明：typedef float KeyType;/实型 typedef int KeyType;/整型typedef char*KeyType;/字符串型,数据元素类型定义为：typedef struct KeyType key;/关键字域.ElemType;,对两个关键字的比较约定为如下的宏定义：对数值型关键字#define EQ(a,b)(a)=(b)#d

5、efine LT(a,b)(a)(b)#define LQ(a,b)(a)=(b)对字符串型关键字#define EQ(a,b)(!strcmp(a),(b)#define LT(a,b)(strcmp(a),(b)0)#define LQ(a,b)(strcmp(a),(b)=0),静态查找表,静态查找表的抽象数据类型定义：ADT StaticSearchTable数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(初始条件：静态查找表ST存在。操作结果：销毁表ST。,9.1静态查找

6、法,Search(ST,key);初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit();初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。ADT StaticSearchTable,顺序表的查找,以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。静态查找表的顺序存储结构typedef struct El

7、emType*elem;/ElemType elem100;int length;SSTable;顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。int Search_Seq(SSTable ST,KeyType key)ST.elme0.key=key;for(i=ST.length;!EQ(ST.elemi.key,key);-i);return i;演示！,查找操作的性能分析：查找算法中的基本操作是将记录的关键字和给定值进行比较，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为

8、衡量依据。平均查找长度：为确定记录在查找表中的位置，需用和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。,其中：Pi为查找表中第i个记录的概率，且；Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。,对于含有n个记录的表，查找成功时的平均查找长度为：,假设每个记录的查找概率相等，即 Pi=1/n则在等概率情况下顺序查找的平均查找长度为：,假设查找成功与不成功的概率相同：,从顺序查找的过程可见，Ci取决于所查记录在表中的位置。如：查找表中最后一个记录时，仅需比较一次；而查找表中第一个记录时

9、，则需比较n次。一般情况下Ci=n-i+1;假设n=ST.length，则顺序查找的平均查找长度为：ASL=nP1+(n-1)P2+.+2Pn-1+Pn,前面总假设各个记录的查找概率并不相等。但实际常常情况不是这样，如果能预先知道每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列，以便提高查找效率。但是，在一般情况下，记录的查找概率预先无法测定。为了提高查找效率，我们可以在每个记录中附设一个访问频度域，并使顺序表中的记录始终不断往后移，以例在以后的逐次查找中减少比较次数。或者在每次查找之后都将刚查找到的记录直接移至表尾。,有序表的查找（可以采用折半查找来实

10、现）,以有序表表示静态查找表时，Search函数可用折半查找来实现。折半查找（Binary Search）的查找过程是：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。,见演示！,折半查找的查找实现int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;while(low=high)mid=(low+high)/2;if EQ(key,ST.elemmid.key)return mid;else if LT(key,ST.elemmid.key)high=mid-1;else low=mid+1;ret

11、urn 0;/Search_Bin;,折半查找的性能分析 看书中的一个具体的情况，假设：n=11i 12 3 4 5 6 7 8 9 10 11Ci 3 4 2 3 4 1 3 4 2 3 4 现构造一棵二叉树，将Ci=i的结点放在这棵树的第i层该二叉树可用以描述折半查找的过程，称之谓“折半查找的判定树”,折半查找在查找成功时和给定值进行比较的关键字个数至多为：,例如:折半查找在n=11 时的判定树如下,一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同,那末，折半查找的平均查找长度是多少呢？假设 n=2h-1（反之，h=log2(n+1)）并且查找概率相等则：,

12、在n50时，可得近似结果,可见，折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构（对线性链表无法进行折半查找）。,索引顺序表的查找 若以索引顺序表表示静态查找表，则Search函数可用分块查找来实现。分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需建立一个“索引表”。,22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53,48 861 7 13,索引表,最大关键字 起始地址,整个表中含有18个记录，可分为三个子表（R1,R2,R6）、(R7,R12)、(R13,R18)对每个子表（

13、或称块）建立一个索引项，其中包括两项内容：最大关键字项 该子表的起始地址,对索引表按关键字有序，则表或者有序或者分块有序。P225页书划上概念！,由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。由此，分块查找的算法即为这两种查找算法的简单合成。分块查找的平均查找长度为：ASLbs=Lb+Lw其中：Lb为查找索引表确定所在块的平均查找长度，Lb为在块中查找元素的平均查找长度。一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每块含有s个记录，即b=n/s；又假定表中每个记录的查找概率相等，则每块查找的

14、概率为1/b，块中每个记录的查找概率为1/s。若用顺序查找确定所在块，则分块查找的平均查找长度为：,1.索引顺序表：存储数据的表+索引；2.存储方法：数据分块存放，且块内无序，但块间有序；每块一个索引项，包括块地址和块中最大数据值。3.查找方法：首先在索引表中查找，索引是有序顺序表，可以采用折半查找方法；然后在 块内查找进行（只能）是顺序查找。,总结：,9.2动态查找法,动态查找表的定义 动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。以下是动态查找表抽象数据类型的定义：,ADT D

15、ymanicSearchTable 数据对象：是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系：数据元素同属一个集合。,特点：用于频繁进行插入、删除、查找的所谓动态查找表。,基本操作：InitDSTable(初始条件：动态查找表DT存在，e为待插入的数据元素；操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。,DeleteDSTable(初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ADT Dyn

16、amicSearchTable,二叉排序树及其查找过程 什么是二叉排序树？二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；、它的左、右子树了分别为二叉排序树。,122,250,300,110,200,99,L,N,P,E,M,C,Y,105,230,216,通常，取二叉链表作为二叉排序树的存储结构,二叉排序树又称二叉查找树,也可以称为二叉分类树,1、分割式查找法：查找步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于

17、根结点的关键字值，查其左子树。大于根结点的关键字值，查其右子树。在左右子树上的操作类似。,122,250,300,110,200,99,105,230,216,BiTree SearchBST(BiTree T,KeyType key)/在二叉分类树查找关键字之值为 key 的结点，找到返回该结/点的地址，否则返回空。T 为二叉分类树的根结点的地址。if(!T)|EQ(key,T-data.key)return(T);else if(LT(key,T-data.key)return(SearchBST(T-lchild,key);else return(SearchBST(T-rchild,k

18、ey);/SearchBST,表示：typedef struct BiTNode ElemType data;struct BiTNode*lchild,*rchild;BiTNode;*BiTree;,见演示!,2、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,2、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父

19、亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,2、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树树。,122,122,99,2、插入算法：首先

20、执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,2、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作

21、为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,122,250,110,99,2、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,122,250,110,99,122,250,300,110,99,2、插入算法：首先执行查找算法，找出被插结点的父亲结

22、点。判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,122,250,300,110,280,99,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,122,250,110,99,122,250,300,110,99,2、插入算法：,Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree/SearchBST,程序实现：,122,250,300,1

23、10,99,T,p,f:null,f:T 的父亲结点p:指向最后一个结点，TRUE 找到；FALSE 叶子的父亲结点。如：插入 280 的过程。,280,2、插入算法：,执行实例：插入值为 280 的结点,2、插入算法：,Status Inset BST(BiTree/Insert BST,程序实现：,122,250,300,110,99,T,p,f:T 的父亲结点p:指向最后一个结点，TRUE 找到；FALSE 叶子的父亲结点。如：插入 280 的过程。,280,f:null,15,60,70,30,20,50,3、二叉排序树的查找分析,平均情况分析（在成功查找两种的情况下）,e.g:下述两

24、种情况下的成功的平均查找长度 ASL,15,60,70,30,20,50,ASL=(1+2+2+3+3+3)/6=14/6,ASL=(1+2+3+4+5+6)/6=21/6,3、二叉排序树的查找分析,平均情况分析（在成功查找两种的情况下）,在一般情况下，设 P（n，i）且它的左子树的结点个数为 i 时的平均查找长度。右图的结点个数为 n=6 且 i=3;则 P（n,i）=P（6,3）=1+(P(3)+1)*3+(P(2)+1)*2/6=1+(5/3+1)*3+(3/2+1)*2/6注意：这里 P(3)、P(2)是具有 3 个结点、2 个结点的二叉排序树的平均查找 长度。在一般情况下，P（i）为

25、具有 i 个结点二叉排序树的平均查找 长度。P(3)（1+2+2）/3=5/3 P(2)（1+2）/2=3/2 P（n,i）=1+(P(i)+1)*i+(P(n-i-1)+1)*(n-i-1)/n n-1 P（n）=P（n,i）/n i=0=1.465log2n,15,60,70,30,20,50,左子树0到n-1个结点,右子树n-1到0个结点,4、二叉排序树的删除操作,叶子结点：直接删除，更改它的父亲结点的相应指针为空。如：删除数据场为 15、70 的结点。,15,60,70,30,20,50,60,30,20,50,子树的根结点：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁

26、哪？左子树中最大的结点 或 右子树中最小的结点，参看下图。要点：维持二叉排序树的特性不变。在中序遍历 中紧靠着被删结点的结点 才有资格作为“替身”。,4、二叉排序树的删除操作,122,250,300,110,200,99,105,230,216,400,450,500,子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场的关键字值为为 99、300 的结点。,被删结点,122,250,300,200,230,216,400,450,500,110,105,删除,99,4、二叉排序树的删除操作,122,250,300,110,200,99,105,330,316,40

27、0,450,500,被删结点,122,250,330,230,216,400,450,500,删除,300,110,99,105,子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场的关键字值为为 99、300 的结点。,316,4、二叉排序树的删除操作,122,250,300,110,200,99,105,330,316,400,450,500,被删结点,结论：将被删结点的另一儿子作为它的父 亲结点的儿子，究竟是作为左儿子 还是右儿子依原替身结点和其父亲 结点的关系而定。释放被删结点的空间。,被删结点,子树的根结点：若被删结点的左儿子为空或者右儿子为空。如下图所示

28、，删除结点的数据场的关键字值为为 99、300 的结点。,4、二叉排序树的删除操作,子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空)或 右子树中最小的 结点(被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为“替身”。,122,250,300,110,200,99,105,330,316,400,450,500,被删结点,替身,替身,110,250,300,105,20

29、0,99,330,316,400,450,500,做法：将替身的数据场复制到被删结 点的数据场。将结点 的左儿子作为 的父结点 的右儿子。,110,110,99,注意：结点 右儿子必为空 结点 的父结点为,110,110,99,4、二叉排序树的删除操作,122,250,300,110,200,99,105,330,316,400,450,500,被删结点,替身,替身,200,250,300,110,99,105,216,400,450,500,子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点(被删结点的左子树中的

30、最右的结点，其右儿子指针场为空)或 右子树中最小的 结点(被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为“替身”。,做法：将替身的数据场复制到被删结 点的数据场。将结点 的右儿子作为 的父结点 的左儿子。,注意：结点 左儿子必为空 结点 的父结点为,200,200,200,200,250,330,316,4、二叉排序树的删除操作,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,替身,替身,子树的根结点：若被删结点的左、右子树皆不空，则：通常的做

31、法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针场为空)或 右子树中最小的 结点(被删结点的右子树中的最左的结点，其左儿子指针场为空)，参看下图。要点：维持二叉分类树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为“替身”。,结论：先将替身的数据场复制到被删结点 将原替身的另一儿子作为它的父亲 结点的儿子，究竟是作为左儿子还 是右儿子依原替身结点和其父亲结 点的关系而定。释放原替身结点的空间。,4、二叉排序树的删除操作,F,S,C,Q,QL,SL,F,C,Q,QL,S,SL,F,PL、PR皆 空，直接删除。,PL

32、或PR为空，,PL为空，删除后的情况。,1.删除法,2.删除法,Status DeleteBST(BiTree/DeleteBST,程序实现：,4、二叉排序树的删除操作,Status Delete(BiTree/DeleteBST,程序实现：,4、二叉排序树的删除操作,注意：删除根结点而相应的二叉树没有另增的头结点的情况。,被删结点 P,若：P-rchild=NULL,被删结点 f,原 f-lchild 即为 P；现 p=p-lchild故 f-lchild 即为 PL,二叉排序树的插入,二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给

33、定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。,Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree/SearchBST,见演示！,插入算法：Status InsertBST(BiTree/InsertBST,在二叉排序树中删除一个节点的算法,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：假设在二叉排序树上被删结点为*p（指向结点的指针为p），其双亲结点为*f（结点指针为f），且不失

34、一般性可设*p是*f的左孩子。,（1）被删除的结点是叶子；若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。（2）被删除的结点只有左子树或者只有右子树；若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。,以*f为根的子树,（3）被删除的结点既有左子树，也有右子树。显然，此时不能如上简单处理。我们从下列图中来分析一下：在删去*p结点之前，中序遍历该二叉树得到的序列为.CLCQLQSLSPPRF.，在删*p之后，为保持其它元素之间的相对位置不变，可

35、以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图(c).CLCSLSPRF.其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。如图（d）.CLCQLQSLSPRF.,(b)删除*p之前,(c)删除*p之后，以PR作为*s的右子树的情形,F,S,f,p,C,c,Q,q,(d)删除*p之后，以*s替代的情形,二叉排序树上删除一个结点的算法所示：Status DeleteBST(BiTree,/从二叉排序树中删除结点p，并重接它的左或右子树void Delete(BiTree/重接*q的左子树,二叉排序树的查找分析,

36、通过前面的知识我们在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1（或结点所在层次数），因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然则，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序却不唯一。看书P231页例子！,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字构造所得的，不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大，,平衡二叉树,平衡二叉树（Balanced Binary Tree或Height-Bala

37、nced Tree）是另一种形式的二叉查找树，又称AVL树。它或者是一棵空树，或者是具有下列性质（特点）的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不大于1。若将二叉树上结点的平衡因子BF（Balance Factor）定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡。看书P223页图9.11,在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。假设深度为h的二叉平衡树上所含结点数的最

38、小值为Nh，则显然 Nh=Nh-1+Nh-2+1 由此可以推导出：hlog（n）因此，在平衡树上进行查找的时间复杂度为O(log(n),9.3哈希表,哈希表的概念及作用 一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。,什么是 hashing 表?特点：不用比较的办法，直接根据

39、所求结点的关键字值 KEY 找到这个结点。追求更快的速度 O(1)，优于任何其它的查找算法。定义：设 M 存区由 m 个单元构成，它的第一个单元的地址为 0。设表具有 n 个结点 a1,a2,a3,.An；这些结点相应的关键字值分别为：k1,k2,k3,kn。又设 f 函数是一个确定的函数，它能将关键字 值 ki 映射为 M 存区的地址：即，f(ki)-0 m-1（注意：是一个确定的地址）该地址就是结点 ai 的存放地址。f 函数通常称之为 hashing 函数，而 M 存区称之为 hashing 表。负载系数：n/m,e、g：将 31 个常用的英文单词，映射到 M 存区。设 m=41,映射是

40、等可能性的。,哈希表,0,1,40,39,A、AND、YOU:总的可能分布为 4131，不冲突的分布为 A41；不冲突的可能性为 1/10,000,000,31,如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？,a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 刘丽 刘宏英 吴军 吴小艳 李秋梅 陈伟.姓名中各字拼音首字母 ll lhy wj wxy lqm cw.用所有首

41、字母编号值相加求和 24 46 33 72 42 26.最小值可能为3 最大值可能为78 可放75个学生 用上述得到的数值作为对应记录在表中的位置，得到下表：,举例：哈希表最常见的例子是以学生学号为关键字的成绩表，号学生的记录位置在第一条，号学生的记录位置在第条,成绩一 成绩二.3.24 刘丽 82 95 25.26 陈伟.33 吴军.42 李秋梅.46 刘宏英.72 吴小艳.78.,上面这张表即哈希表。,如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：李秋梅:lqm 12+17+13=42 取表中第42条记录即可。问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？这个问

42、题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。,哈希表的构造方法,、直接定址法 例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。,地址 01 02.25 26 27.100 年龄 1 2.25 26 27.人数 3000 2000.1050.,、数字分析法有学生的生日数据如下：年.月.日.经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。,、平方取中法取关键字平方后的中间几位为哈希地址。,、折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分

43、的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：5864 5864 4220 0224+)04+)04-10088 6092 H(key)=0088 H(key)=6092(a)移位叠加(b)间界叠加,、除留余数法 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p(p=m)、随机数法 选择一个随机函数，取关键字的随机函数值为

44、它的哈希地址，即H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法。,处理冲突的方法,成绩一 成绩二.3.24 刘丽 82 95 25.26 陈伟.33 吴军.42 李秋梅.46 刘宏英.72 吴小艳.78.,上面这张表即哈希表。,如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：,、开放定址法 Hi=(H(key)+di)MOD m i=1,2,.,k(k=m-1)其中m为表长，di为增量序列如果di

45、值可能为1,2,3,.m-1，称线性探测再散列。如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,.k*k,-k*k(k=m/2)称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：,0 1 2 3 4 5 6 7 8 9 10 60 17 29(a)插入前,0 1 2 3 4 5 6 7 8 9 10 60 17 29 38(b)线性探测再散列,0 1 2 3 4 5 6 7 8 9 10 60 17 29

46、(c)二次探测再散列,0 1 2 3 4 5 6 7 8 9 10 38 60 17 29(d)伪随机探测再散列,、再哈希法 当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。、链地址法 将所有关键字为同义词的记录存储在同一线性链表中。,、建立一个公共溢出区 假设哈希函数的值域为0,m-1,则设向量HashTable0.m-1为基本表，另外设立存储空间向量OverTable0.v用以存储发生冲突的记录。,哈希表的查找,/开放定址哈希表的存储结构int hashsize=997,.;typedef struct ElemType*elem;int count;

47、int sizeindex;HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE-1,Status SearchHash(HashTable H,KeyType K,int,Status InsertHash(HashTable,结束！,静态树表的查找,在上面我们对有序表的查找性能的讨论是在“等概率”的前提下进行的，即当有序表中的各记录的查找概率相等时，进行折半查找，其性能最优。在不等概率查找的情况下，情况又如何呢？例如:关键字:A B C D E Pi:0.2 0.3 0.05 0.3 0.15 Ci:2 3 1 2

48、3 此时的 ASL=2.4若改变Ci的值:2 1 3 2 3 则 ASL=1.9 这就说明，当有序表中各记录的查找概率不等时，折半查找时未必是最优的查找方法。那末此时应如何进行查找呢？换句话说，描述查找过程的判定树为何类二叉树时，其查找性能最佳？,如果只考虑查找成功的情况，则使查找性能达最佳的判定树是其带权内路径长度之和PH值取最小值的二叉树。,其中：n为二叉树上结点的个数（即有序表的长度）；hi为第 i个结点在二叉树上的层次数；结点的wi=cpi(I=1,2,n)，其中pi为结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树（Static Optimal Search Tr

49、ee）。,二叉排序树的查找算法：若二叉排序树为空，则查找不成功；否则1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,见演示！,如果取二叉链表作为二叉排序树的存储结构，则上述查找过程如下：BiTree SearchBST(BiTree T,KeyType key)if(!T)|EQ(key,T-data.key)return(T);else if LT(key,T-data.key)return(SearchBST(T-lchild,key);else return(SearchBST(T-rchild.key);/SearchBST,