《数据结构(第9章查找)》由会员分享，可在线阅读，更多相关《数据结构(第9章查找)（63页珍藏版）》请在文档大全上搜索。
1、安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学第第9章章 查查 找找1. 掌握顺序查找、二分查找和分块查找的方法。掌握顺序查找、二分查找和分块查找的方法。2. 掌握二叉排序树的相关运算和查找过程。掌握二叉排序树的相关运算和查找过程。3. 理解平衡二叉树的建树方法。理解平衡二叉树的建树方法。4. 掌握哈希表的建立方法和查找过程。掌握哈希表的建立方法和查找过程。5. 掌握各种查找方法在等概率下的平均查找长度的计算方掌握各种查找方法在等概率下的平均查找长度的计算方法。法。学习要点学习要点安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 基本概念基本
2、概念l 查找表查找表 ：是由同一类型的数据元素构成的集合，由于是由同一类型的数据元素构成的集合，由于“集合集合”中的数据元素之间存在着中的数据元素之间存在着松散松散的关系，因此查找的关系，因此查找表是一种应用灵便的数据结构。表是一种应用灵便的数据结构。l 有关操作有关操作u 查询某个查询某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；u 在查找表中插入一个数据元素；在查找表中插入一个数据元素；u 从查找表中删去某个数据元素。从查找表中删去某个数据元素。安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学l 查找表的分类查找表的分类u 静态查找表：仅作查询
3、和检索操作的查找表。静态查找表：仅作查询和检索操作的查找表。u 动态查找表：在查找过程中同时插入查找表中不存在的动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。数据元素，或者从查找表中删除已存在的某个数据元素。l 关键字关键字 是数据元素中某个数据项的值，用以标识一个数据元是数据元素中某个数据项的值，用以标识一个数据元素。若此关键字可以识别唯一的一个记录，则称之谓素。若此关键字可以识别唯一的一个记录，则称之谓“主主关键字关键字”。若此关键字能识别若干记录，则称之谓。若此关键字能识别若干记录，则称之谓“次关次关键字键字”。v 基本概念基本概念安安
4、安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学l 查找查找 根据给定的某个值，在查找表中确定一个其关键字根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。等于给定值的数据元素。 若查找表中存在这样一个记录，则称若查找表中存在这样一个记录，则称“查找成功查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称中的位置；否则称“查找不成功查找不成功”，查找结果：给出，查找结果：给出“空空记录记录”或或“空指针空指针”。v 基本概念基本概念安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大
5、大大大大学学学学学学l 数据元素类型定义为：数据元素类型定义为： typedef struct KeyType key; /关键字域关键字域 /其他域其他域 ElemType;v 基本概念基本概念安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学9.1.1 顺序表的查找顺序表的查找应用范围：以顺序表或线性链表表示的静态查找表，表内元素应用范围：以顺序表或线性链表表示的静态查找表，表内元素之间无序。之间无序。顺序查找基本思想：从表中最后一个记录开始，逐个进行记录顺序查找基本思想：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较的关键
6、字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功；若直至第一个记录，其关键字和给定值比相等，则查找成功；若直至第一个记录，其关键字和给定值比较都不等，则查找不成功。顺序存储结构的表示：较都不等，则查找不成功。顺序存储结构的表示： typedef struct ElemType * elem ; int length ; SSTable ;9.1 静态查找表静态查找表安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学int Search_Seq( Stable ST, KeyType key ) /在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字
7、等于key的数据元素的数据元素 ST.elem0.key = key; /哨兵哨兵 for( i = ST.length; ! EQ(ST.elemi.key, key); - -i ) ; return i; /查找不成功时查找不成功时i为为0 /Search_Seq免去查找过程中每免去查找过程中每一步都要检测整个一步都要检测整个表是否查找完毕表是否查找完毕v 顺序查找算法顺序查找算法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学int Search_Seq( Stable ST, KeyType key ) /在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其
8、关键字等于key的数据元素的数据元素 for( i =0; i ST.length ;+i ) if(ST.elemi.key=key) return i; return(0); /查找不成功时查找不成功时i为为0 /Search_Seqv 顺序查找算法顺序查找算法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学8012n-3n-2n-1nST.elem key例例1：在下表中查找：在下表中查找 key = 8 的结点。的结点。100100713iiiiiii查找不成功，查找不成功，i = 08012n-3n-2n-1nST.elem key例例2：在下表中查找：在下表
9、中查找 key = 8 的结点。的结点。100100813iii查找成功，查找成功，i = n-2v 举例说明举例说明安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学1n查找成功情况下：查找成功情况下：设每个结点的查找概率相等设每个结点的查找概率相等ASL (n-i+1) (n+1)/ 2i=1n 和给定值进行比较的关键和给定值进行比较的关键字个数的期望值称为查找成功字个数的期望值称为查找成功时的平均查找长度。时的平均查找长度。v 性能分析性能分析安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学l 折半查找折半查找查找方式：每次将待查记录所在区间
10、缩小一半。查找方式：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。适用条件：采用顺序存储结构的有序表。算法实现：算法实现： 设表长为设表长为n，low、high和和mid分别指向待查元素所在区间的分别指向待查元素所在区间的上界、下界和中点，上界、下界和中点，k为给定值为给定值。 初始时，令初始时，令low=1，high=n ，mid= (low+high)/2 。 让让k与与mid指向的记录比较指向的记录比较l 若若k=ST.elemmid.key，查找成功查找成功；l 若若k ST.elemmid.key，则，则low=mid+1。 重复上述操作，直至重复上述操作，直至
11、lowhigh时，时，查找失败查找失败。9.1.2 有序表的查找有序表的查找安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 举例说明举例说明(1)low找找 key=215113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhigh安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学low找找key=70 511321932143755666477588
12、0988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighv 举例说明举例说明(2)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学low5113219321437556664775880988109211midhighlow5113219321437556664775880988109211highv 举例说明举例说明(2)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学int Search_b
13、in ( SStable ST, KeyType key ) /在有序表在有序表ST中折半查找关键字等于中折半查找关键字等于key的数据元素的数据元素low = 1 ; high = ST.length ;while( low data.key) return(T); else if (LT(key,T-data.key) return SearchBST(T-lchild,key); else return SearchBST(T-rchild,key); v二叉排序树查找算法二叉排序树查找算法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学例如：在下图中分别查找关键
14、字值等于例如：在下图中分别查找关键字值等于37，61和和95过程。过程。45125333710024619078从上述查找过程可见，在查找过程中，生从上述查找过程可见，在查找过程中，生成了一条查找路径：成了一条查找路径：1. 从根结点出发，沿着左分支或右分支逐从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点，表层向下直至关键字等于给定值的结点，表明查找成功。明查找成功。2. 或者从根结点出发，沿着左分支或右分或者从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止，表明支逐层向下直至指针指向空树为止，表明查找不成功。查找不成功。v二叉排序树查找过程二叉排序树查找过程安
15、安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学基本思想：在每一步插入过程中，二叉排序树中原有的结点位置均基本思想：在每一步插入过程中，二叉排序树中原有的结点位置均不动，只是将待插入的结点作为一个叶结点插入到适当的位置，使不动，只是将待插入的结点作为一个叶结点插入到适当的位置，使得树中任何结点与其左、右子树结点之间的关系仍然满足二叉排序得树中任何结点与其左、右子树结点之间的关系仍然满足二叉排序树的性质，向二叉树树的性质，向二叉树T插入一个新结点插入一个新结点s的过程为：的过程为：v 若若T为空的二叉树，则将新结点作为根结点插入。为空的二叉树，则将新结点作为根结点插入。v
16、若新结点若新结点s的值等于二叉排序树的根结点，说明该结点已存在，的值等于二叉排序树的根结点，说明该结点已存在，不需要插入。不需要插入。v 若将新结点若将新结点s的值小于二叉排序树的值小于二叉排序树T的根结点，则将的根结点，则将s插入到插入到T的的左子树中去。左子树中去。v 若新结点若新结点s的值大于二叉排序树的值大于二叉排序树T的根结点，则将的根结点，则将s插入到插入到T的右的右子树中去。二叉排序树的插入操作是一个递归过程。子树中去。二叉排序树的插入操作是一个递归过程。v二叉排序树插入算法思想二叉排序树插入算法思想安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 Sta
17、tus SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)/ 若查找成功，则指针若查找成功，则指针p指向该数据元素结点，返回指向该数据元素结点，返回TRUE，否则，否则p指指向查找路径上访问的最后一个结点并返回向查找路径上访问的最后一个结点并返回FALSE，f 是指向是指向T的双亲的双亲 if (!T) p=f; return FALSE; else if (EQ(key,T-data.key)p=T;return TRUE; else if (LT(key,T-data.key) return SearchBST(T-lchild,k
18、ey,T,p); else return SearchBST(T-rchild,key,T,p);v具体实现具体实现(1)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学Status InsertBST(BiTree &T,ElemType e) if (!SearchBST(T,e.key,NULL,p) s=(BiTree)malloc(sizeof(BiTNode); s-data=e; s-lchild=s-rchild=NULL; if (!p) T=s; else if (LT(e.key,p-data.key) p-lchild=s; else p
19、-rchild=s; return TRUE; else return FALSE; v具体实现具体实现(2)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学2712从空树出发，经过一系列的查找插入操作后，便可生成一棵二叉从空树出发，经过一系列的查找插入操作后，便可生成一棵二叉排序树。排序树。例例 对于关键字序列对于关键字序列10，18，3，8，12，2，7，构造一棵，构造一棵BST。101838注意：注意：对于同样的数据，输入顺序不同，对于同样的数据，输入顺序不同，建立起来的二叉排序树的形态也不同。建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。这
20、直接影响到二叉排序树的查找性能。 如果输入序列选得不好，会建立起一棵如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最单支树，使得二叉排序树的高度达到最大，这样必然会降低查找性能。大，这样必然会降低查找性能。v 建立二叉排序树建立二叉排序树安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 中序遍历二叉排序树便可得到一个关键字的有序序列，也就是中序遍历二叉排序树便可得到一个关键字的有序序列，也就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。对下图所示的二叉排序进行中序遍历，结果为序
21、列。对下图所示的二叉排序进行中序遍历，结果为(2，3，7，8，10，12，18)。 每次插入的新结点都是二叉排序树上新的叶子结点，不必移动每次插入的新结点都是二叉排序树上新的叶子结点，不必移动其它结点，仅需修改某个结点的指针。这相当于在其它结点，仅需修改某个结点的指针。这相当于在一个有序列上插入一个记录而又不需要移动其他一个有序列上插入一个记录而又不需要移动其他记录。记录。 二叉排序树既拥有折半查找的特性，二叉排序树既拥有折半查找的特性，又采用链式存储。又采用链式存储。7212101838v 结论结论安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 和插入相反，删除在
22、查找成功之后进行，并且要求在删除和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：可分三种情况讨论： 被删除的结点是叶子；被删除的结点是叶子； 被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树； 被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也有右子树。v 二叉排序树的删除二叉排序树的删除安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学q 删除叶子结点，只需将其双亲结点指向它的指针置为空删除叶子结点，只需将其双
23、亲结点指向它的指针置为空，再释放它即可。如：删除关键字值为，再释放它即可。如：删除关键字值为7的结点。的结点。1018381227q 删除叶子结点删除叶子结点安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学q 删除的结点只有左子树或者只有右子树，则使其双亲结点删除的结点只有左子树或者只有右子树，则使其双亲结点的相应指针域的值改为的相应指针域的值改为 “指向被删除结点的左子树或右子指向被删除结点的左子树或右子树树”。如：。如：(1)删除关键字值为删除关键字值为2的结点，它只有右子树。的结点，它只有右子树。(2)删除关键字值为删除关键字值为18的结点，它只有左子树。的结点，
24、它只有左子树。1018581223q 删除的结点只有左子树或只有右子树删除的结点只有左子树或只有右子树安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学RQD中序遍历：中序遍历：PLDRQ 删除后：删除后： PLRQPLRQPLRDQ中序遍历：中序遍历： QRPLD 删除后：删除后： QRPLPLRQPLRQD中序遍历：中序遍历：DPRRQ 删除后：删除后： PRRQPRRQPRRDQ中序遍历：中序遍历： QRDPR 删除后：删除后： QRPRPRRQPRq 具体解释具体解释安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 删除叶结点和删除的结点
25、只有左子树或者只有右子树这两删除叶结点和删除的结点只有左子树或者只有右子树这两种操作，可通过下面语句实现。种操作，可通过下面语句实现。if (!p-rchild) q=p;p=p-lchild;free(q);else if (!p-lchild) q=p;p=p-rchild;free(q);1018581223pq 具体实现具体实现安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学q 方法一：首先将结点方法一：首先将结点D的右子树链接到其中序前驱结点的右子树链接到其中序前驱结点(结点结点D的左子树中的左子树中“最右下最右下”且右指针域为空的结点且右指针域为空的结点)的
26、右指针域，的右指针域，然后把结点然后把结点R(结点结点D的双亲结点的双亲结点)指向结点指向结点D的指针链接到结点的指针链接到结点D的左子树上即可。的左子树上即可。RDQRRDRCCLQLGLGpfRQRRDRCCLQLGLGf该二叉排序树的中序遍历结果为：该二叉排序树的中序遍历结果为：CL CQLQGLGDDR R RRq 删除的结点既有左子树又有右子树删除的结点既有左子树又有右子树安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学q 方法二：把结点方法二：把结点D 的中序前驱结点的中序前驱结点G的值赋给结点的值赋给结点D，因，因为该中序前驱结点为该中序前驱结点G只有左子
27、树只有左子树GL，然后将结点，然后将结点G的双亲结的双亲结点的右指针链接到点的右指针链接到GL即可。即可。 RDQRRDRCCLQLGLGpfRGQRRDRCCLQLGLpf该二叉排序树的中序遍历结果为：该二叉排序树的中序遍历结果为：CL CQLQGLGDDR R RRq 删除的结点既有左子树又有右子树删除的结点既有左子树又有右子树安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 删除的结点既有左子树又有右子树，可通过下面语句实删除的结点既有左子树又有右子树，可通过下面语句实现。现。q=p;s=p-lchild;while (s-rchild) q=s;s=s-rch
28、ild;p-data=s-data;if (q!=p) q-rchild=s-lchild;else q-lchild=s-lchild;free(s);RDQRRDRCCLQLGLGpfq 具体实现具体实现安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v BST 上查找过程，是从根结点到所找到结点的一条路径。与给上查找过程，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度定值比较次数等于该路径长度+1，最大次数不超过树的深度。但，最大次数不超过树的深度。但含有含有n个结点的个结点的BST却不唯一。因此，含有却不唯一。因此，含有n个结点的个结点的BST
29、的的ASL和树的形态有关。和树的形态有关。 最差情况是退化为单支树，最差情况是退化为单支树，ASL=(n+1)/2 (同顺序查找同顺序查找)。最好。最好情况与折半查找相同，与情况与折半查找相同，与log2n成正比。成正比。12452453123793(45, 24, 53, 12, 37, 93)2437455393(12, 24, 37, 45, 53, 93)ASL(a)=(1+2+2+3+3+3)/6 =14/6ASL(b)=(1+2+3+4+5+6)/6 =21/6q 查找分析查找分析安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 平衡二叉树是二叉排序树的另
30、一种形式，其特点为：树中平衡二叉树是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树高度之差的绝对值不大于每个结点的左、右子树高度之差的绝对值不大于1 。若。若平衡平衡因子因子定义为结点左子树的高度减去右子树的高度，则平衡二定义为结点左子树的高度减去右子树的高度，则平衡二叉树所有结点的平衡因子只可能是叉树所有结点的平衡因子只可能是-1、0、1的二叉排序树。的二叉排序树。例如：例如：20210平衡树平衡树非平衡树非平衡树-2-20-100101v 平衡二叉树平衡二叉树安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 采取的方法是在向平衡二叉树插入结点时进行平衡
31、化旋转。基采取的方法是在向平衡二叉树插入结点时进行平衡化旋转。基本思想为：假定向平衡树插入一个结点后破坏了其平衡性，则首本思想为：假定向平衡树插入一个结点后破坏了其平衡性，则首先要找出唯一一棵最小不平衡子树，然后再调整该子树中有关结先要找出唯一一棵最小不平衡子树，然后再调整该子树中有关结点之间的链接关系，使之成为一棵新的平衡二叉树。最小不平衡点之间的链接关系，使之成为一棵新的平衡二叉树。最小不平衡子树被调整为平衡子树后，整个二叉排序树又成为一棵平衡树。子树被调整为平衡子树后，整个二叉排序树又成为一棵平衡树。 最小不平衡子树最小不平衡子树是指是指离插入结点最近，且平衡离插入结点最近，且平衡因子绝
32、对值大于因子绝对值大于1的祖先的祖先结点作为根的子树。结点作为根的子树。027511018 410-110127511018 410-211160v 构造平衡二叉树的方法构造平衡二叉树的方法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学(1)单向右旋平衡处理单向右旋平衡处理( LL型型) ： 新插入结点在新插入结点在A的左子树根结点的左子树上。的左子树根结点的左子树上。A的平衡因子由的平衡因子由1增至增至2，导致失衡。，导致失衡。 调整规则：将结点调整规则：将结点A 的左孩子的左孩子B向上旋转成为新二叉树的根，将向上旋转成为新二叉树的根，将结点结点A 及其右子树向右下
33、旋转成为结点及其右子树向右下旋转成为结点B的右子树，而结点的右子树，而结点B原来原来的右子树的右子树BR则成为结点则成为结点A的左子树。的左子树。(进行一次顺时针旋转进行一次顺时针旋转)q 调整方法分四种情况调整方法分四种情况h+1h-1ABARBRBLh-10+2+1hh-1ABARBRBL00具体实现：具体实现：lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;p安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学(2)单向左旋平衡处理单向左旋平衡处理( RR型型) ： 新插入结点在新插入结点在A的右子树根结点的右子树上。的
34、右子树根结点的右子树上。A的平衡因子由的平衡因子由-1增至增至-2，导致失衡。，导致失衡。 调整规则：将结点调整规则：将结点A 的右孩子的右孩子B向上旋转成为新二叉树的根，向上旋转成为新二叉树的根，将结点将结点A 及其左子树向左下旋转成为结点及其左子树向左下旋转成为结点B的左子树，而结点的左子树，而结点B原原来的左子树来的左子树BL则成为结点则成为结点A的右子树。的右子树。(进行一次逆时针旋转进行一次逆时针旋转)q 调整方法分四种情况调整方法分四种情况-2hh-1h-1BABRBLAL-10-1h0BABRBLALh-10具体实现：具体实现：rc=p-rchild;p-rchild=rc-lc
35、hild;rc-rchild=p;p=rc;p安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学(3)先左后右平衡处理先左后右平衡处理( LR型型) ： 新插入结点在新插入结点在A的左子树根结点的右子树上。的左子树根结点的右子树上。A的平衡因子由的平衡因子由1增至增至2，导致失衡。，导致失衡。 调整规则：将调整规则：将A的左孩子的右子树的根结点的左孩子的右子树的根结点C旋转到结点旋转到结点A的位的位置成为新二叉树的根，将结点置成为新二叉树的根，将结点B及其左子树向左下旋转成为及其左子树向左下旋转成为C的左的左子树，而子树，而C 结点原来的左子树结点原来的左子树CL则作为结
36、点则作为结点B的右子树；将结点的右子树；将结点A及其右子树向右下旋转成为结点及其右子树向右下旋转成为结点C的右子树，的右子树，C 结点原来的右子结点原来的右子树树CR作为结点作为结点A的左子树。的左子树。(需进行两次旋转，先逆时针后顺时针需进行两次旋转，先逆时针后顺时针)q 调整方法分四种情况调整方法分四种情况安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学+2-1+1h-1ABARCLBLh-10CCRh-20h-1+1+2h-1CBARCLBLh-10CRh-2A+2h-10CBARCLBL0CRA-1 将将A的左孩子的右子树的根结点的左孩子的右子树的根结点C旋转到
37、结点旋转到结点A的位置成为新二的位置成为新二叉树的根，将结点叉树的根，将结点B及其左子树向左下旋转成为及其左子树向左下旋转成为C的左子树，而的左子树，而C 结结点原来的左子树点原来的左子树CL则作为结点则作为结点B的右子树。的右子树。(第一次逆时针旋转第一次逆时针旋转) 将结点将结点A及其右子树向右下旋转成为结点及其右子树向右下旋转成为结点C的右子树，的右子树，C 结点原结点原来的右子树来的右子树CR作为结点作为结点A的左子树。的左子树。(第二次顺时针旋转第二次顺时针旋转) 调整过程调整过程安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学q调整方法分四种情况调整方法分四
38、种情况(4)先右后左平衡处理先右后左平衡处理( RL型型) ： 新插入结点在新插入结点在A的右子树根结点的左子树上。的右子树根结点的左子树上。A的平衡因子由的平衡因子由-1增至增至-2，导致失衡。，导致失衡。 调整规则：它与调整规则：它与LR旋转情况正好对称的。旋转情况正好对称的。安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学调整实例调整实例 假设一组数据对象为假设一组数据对象为(40，28，16，56，50，32，30，63)，按次序插入每个对象生成一棵平衡二叉树，根据插入，按次序插入每个对象生成一棵平衡二叉树，根据插入过程指出每一步的调整类型：过程指出每一步的调整
39、类型：“单向左旋转单向左旋转”、“单向右旋单向右旋转转”、“先左后右旋转先左后右旋转”、“先右后左旋转先右后左旋转”、 “无无”。解释：解释： 左子树的左子树上插入左子树的左子树上插入 “单向右旋转单向右旋转” 右子树的右子树上插入右子树的右子树上插入 “单向左旋转单向左旋转” 左子树的右子树上插入左子树的右子树上插入 “先左后右旋转先左后右旋转” 右子树的左子树上插入右子树的左子树上插入 “先右后左旋转先右后左旋转”安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学9.3 哈希表哈希表9.3.1 什么是哈希表？什么是哈希表？哈希查找：哈希查找：又叫散列查找，利用哈希函数
40、进行查找的过程。又叫散列查找，利用哈希函数进行查找的过程。其基本思想是在记录的存储地址和它的关键字之间建立一个其基本思想是在记录的存储地址和它的关键字之间建立一个确定的对应关系。这样，不经过比较，一次存取就能得到所确定的对应关系。这样，不经过比较，一次存取就能得到所查元素的查找方法。查元素的查找方法。哈希函数：哈希函数：在记录的关键字与记录的存储地址之间建立的一在记录的关键字与记录的存储地址之间建立的一种对应关系。按这种思想建立的表称为哈希表。种对应关系。按这种思想建立的表称为哈希表。安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学例例 假设有一批关键字序列假设有一批关
41、键字序列18，75，60，43，54，90，46，给定散列函，给定散列函数数H(k)=k%13，存贮区的内存地址从，存贮区的内存地址从0到到15，则可以得到每个关键字的，则可以得到每个关键字的散列地址为：散列地址为： H(18)=18%13=5， H(75)=75%13=10， H(60)=60%13=8 H(43)=43%13=4， H(54)=54%13=2， H(90)=90%13=12 H(46)=46%13=7于是，根据散列地址，可以将上述于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组个关键字序列存贮到一个一维数组HT(散列表散列表)中，具体表示为：中，具体表示为：9
42、0756046184354151413121110987654321 0HT 其中其中HT就是散列存贮的表，称为散列表。从散列表中查找一个元就是散列存贮的表，称为散列表。从散列表中查找一个元素相当方便，例如，查找素相当方便，例如，查找75，只需计算出，只需计算出H(75)=75%13=10，则可以，则可以在在HT10中找到中找到75。v 举例说明举例说明安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 上面讨论的散列表是一种理想的情形，即每一个关键字对上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的应一个唯一的地址
43、。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址。这样，将导致后放的关键关键字有可能对应同一个内存地址。这样，将导致后放的关键字无法存贮，我们把这种现象叫做字无法存贮，我们把这种现象叫做冲突冲突(collision)。 即即key1key2，而，而f(key1)=f(key2)。在散列存贮中，冲突。在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为的关键字互称为“同义词同义词”。
44、 v 冲突问题冲突问题安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学1. 直接定址法直接定址法 可表示为可表示为H(key)=a *key+b，其中，其中a、b均为常数。均为常数。 这种方法计算特别简单，并且不会发生冲突，但当关键字这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，将造成大量存贮单元的分布不连续时，会出现很多空闲单元，将造成大量存贮单元的浪费。实际中使用此方法较少。浪费。实际中使用此方法较少。例例 关键字集合为关键字集合为100，300，500，700，800，900，选取哈，选取哈希函数为希函数为H(key)=key
45、/100，则在哈希表中存放如下：，则在哈希表中存放如下： 9.3.2 哈希函数的构造方法哈希函数的构造方法0100123003450056700780089009安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学2. 数字选择法数字选择法 对关键字序列进行分析，取那些位上数字变化多的、频率对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。例如，对如下的关键字序列：大的作为散列函数地址。例如，对如下的关键字序列： 4 3 0 1 0 4 6 8 1 0 1 5 3 5 5 4 3 0 1 0 1 7 0 1 1 2 8 3 5 2 4 3 0 1 0
46、3 7 2 0 8 1 8 3 5 0 4 3 0 1 0 2 6 9 0 6 0 5 3 5 1 通过对上述关键字序列分析，发现前通过对上述关键字序列分析，发现前5位相同，第位相同，第6、8、10位上的数字变化多些，若规定地址取位上的数字变化多些，若规定地址取3位，则散列函数可取位，则散列函数可取它的第它的第6、8、10位。于是有：位。于是有： H(430104681015355)480 H(430101701128352)101 H(430103620805351)328 H(430102690605351)296 9.3.2 哈希函数的构造方法哈希函数的构造方法安安安安安安徽徽徽徽徽徽理
47、理理理理理工工工工工工大大大大大大学学学学学学3. 平方取中法平方取中法 取关键字平方后的中间几位为散列函数地址。在选定散列取关键字平方后的中间几位为散列函数地址。在选定散列函数时不一定知道关键字的全部信息，取其中哪几位也不一定函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到函数地址。此，可以使用随机分布的关键字得到函数地址。 如图，随机给出一些关键字，并取平方后的第如图，随机给出一些关键字，并取平方后的第2到到4位为函位为函数地址。数地址。 9.3
48、.2 哈希函数的构造方法哈希函数的构造方法关键字关键字0100 (关键字关键字)20010000函数地址函数地址01011001200121000014400002104401160206113704004310541370310安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学4. 折叠法折叠法 将关键字分割成位数相同的几部分将关键字分割成位数相同的几部分(最后一部分的位数可最后一部分的位数可以不同以不同)，然后取这几部分的叠加和，然后取这几部分的叠加和(舍去进位舍去进位)作为散列函数地作为散列函数地址，称为折叠法。例如：址，称为折叠法。例如： 假设关键字为某人身份证号
49、码假设关键字为某人身份证号码430104681015355，则可以，则可以用用4位为一组进行叠加，即有位为一组进行叠加，即有5355+8101+1046+430=14932，舍去高位，则有舍去高位，则有H(430104681015355)4932为该身份证关键为该身份证关键字的散列函数地址。字的散列函数地址。9.3.2 哈希函数的构造方法哈希函数的构造方法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学5. 除留余数法除留余数法 该方法是用关键字序列中的关键字该方法是用关键字序列中的关键字k除以除以p(p是小于等于散是小于等于散列表长度列表长度m)所得余数作为散列函数的
50、地址，即有所得余数作为散列函数的地址，即有H(k)kp 。 除留余数法计算简单，适用范围广，是一种最常使用的方除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想的法。这种方法的关键是选取较理想的p值，使得每一个关键字值，使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等，通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性。从而尽可能减少发生冲突的可能性。 一般情形下，设散列表中允许的地址数为一般情形下，设散列表中允许的地址数为m，取一个不大，取一个不大于于m，但最接近于或等于，但最接近于或等于m的质数的质数p。9
51、.3.2 哈希函数的构造方法哈希函数的构造方法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 由于散列存贮中选取的散列函数不是线性函数，故不可避由于散列存贮中选取的散列函数不是线性函数，故不可避免地会产生冲突，下面给出常见的解决冲突方法。免地会产生冲突，下面给出常见的解决冲突方法。1开放定址法开放定址法 开放定址法就是从发生冲突的那个单元开始，按照一定的次开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中找出一个空闲的存储单元，把发生冲突的待插序，从散列表中找出一个空闲的存储单元，把发生冲突的待插入关键字存储到该单元中，从而解决冲突的发生。入关键字存储
52、到该单元中，从而解决冲突的发生。9.3.3 解决冲突的方法解决冲突的方法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学l 假设散列表的地址为假设散列表的地址为0m-1，则散列表的长度为，则散列表的长度为m。若一个。若一个关键字在地址关键字在地址d处发生冲突，则依次探查处发生冲突，则依次探查d+1，d+2，m-1(当达到表尾当达到表尾m-1时，又从时，又从0，1，2，.开始探查开始探查)等地址，直等地址，直到找到一个空闲位置来装冲突处的关键字，将这一种方法称为到找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。探查下一位置的公式为线性探查法。探查下一位置的
53、公式为di=(di-1+1)%m (1im-1)，最后将冲突位置的关键字存入最后将冲突位置的关键字存入di地址中。地址中。v 线性探查法线性探查法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学l 例例 给定序列为给定序列为19，14，23，1，68，20，84，27，55，11，10，79，散到函数，散到函数H(k)=k%13，散列表空间地址为，散列表空间地址为012，用，用线性探查法建立散列存贮结构。得到的散列表如下图所示。线性探查法建立散列存贮结构。得到的散列表如下图所示。 H(19)=19%13=6; H(14)=14%13=1; H(23)=23%13=10;
54、 H(1)=1%13=1; H(68)=68%13=3; H(20)=20%13=7; H(84)=84%13=6; H(27)=27%13=1; H(55)=55%13=3; H(11)=11%13=11; H(10)=10%13=10; H(79)=79%13=1;v 线性探查法线性探查法012345678910111219142316820 842755111079安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，直到冲突不再发生。即：地址，直到冲突不再
55、发生。即：Hi=Rhi(key) i=1,2,k其中：其中：Rhi不同的哈希函数不同的哈希函数特点：计算时间增加特点：计算时间增加v 再哈希法再哈希法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 是把相互发生冲突的同义词用一个单链表链接起来，若干是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个单链表。组同义词可以组成若干个单链表。例例 对给定的关键字序列对给定的关键字序列19,14,23,1,68,20,84,27,55,11,10,79，给定散列函数为给定散列函数为H(k)=k%13，试用拉链法解决冲突建立散列表，试用拉链法解决冲突建立散列
56、表。v 链地址法链地址法安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 14 0123456789101112 1 2768 55 19 84 20 23 10 11 79 v 链地址法示意图链地址法示意图安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学决定哈希表查找的决定哈希表查找的ASL的因素：的因素：1. 选用的哈希函数选用的哈希函数;2. 选用的处理冲突的方法选用的处理冲突的方法;3. 哈希表饱和的程度，装载因子哈希表饱和的程度，装载因子=n/m 值的大小值的大小(n表中填入表中填入的记录数，的记录数，m表的长度表的长度)9.3.4 哈
57、希表的查找及性能分析哈希表的查找及性能分析安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学v 平均查找长度平均查找长度例例 给定关键字序列为给定关键字序列为19，14，23，1，68，20，84，27，55，11，10，79，散到函数，散到函数H(k)=k%13 ，散列表空间地址为，散列表空间地址为012，求该哈希表的平均查找长度。求该哈希表的平均查找长度。 H(19)=6，H(14)=1，H(23)=8，H(1)=1， H(68)=3，H(20)=7，H(84)=7，H(27)=1， H(55)=3，H(11)=11，H(10)=10，H(79)=1 0 1 2 3
58、4 9 10 7 8 5 6 11 12 19 114 123 1 1 268 120 184 227 455 311 110 179 9ASL=(1+1+1+2+1+1+2+4+3+1+3+9)/12=29/12哈希地址哈希地址关键字关键字探查次数探查次数安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学 散列查找按理论分析，它的时间复杂度应为散列查找按理论分析，它的时间复杂度应为O(1)，它的平，它的平均查找长度应为均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均，但实际上由于冲突的存在，它的平均查找长度将会比查找长度将会比1大。大。1. 线性探查法的性能分
59、析线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平均由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小查找长度与表的大小m无关，只与所选取的散列函数无关，只与所选取的散列函数H及装填及装填因子因子的值和该处理方法有关，这时的成功的平均查找长度为的值和该处理方法有关，这时的成功的平均查找长度为ASL=1/2 (1+1/(1- ) 。 2. 拉链法查找的性能分析拉链法查找的性能分析 由于拉链法查找就是在单链表上查找，查找单链表中第一由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为个结点的次数为1，第二个结点次数为，第二个结点次数为2，其余依次
60、类推。它的，其余依次类推。它的平均查找长度平均查找长度ASL=1+/2。v 性能分析性能分析(1)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学从以上结果可见：从以上结果可见： 哈希表的平均查找长度是哈希表的平均查找长度是 的函数的函数，而不是，而不是 n 的函数。这的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得，使得平均查找长度限定在某个范围内。平均查找长度限定在某个范围内。 这是哈希表所这是哈希表所特有的特点。特有的特点。注意：在非链地址处理冲突的哈希表中删除一个记录，则需在注意：在非链地址处理冲突的哈希表中删除一个记录，则需在该记录的位置上填入一个特殊符号，以免找不到在它之后填入该记录的位置上填入一个特殊符号，以免找不到在它之后填入的的“同义词同义词”记录。记录。v 性能分析性能分析(2)安安安安安安徽徽徽徽徽徽理理理理理理工工工工工工大大大大大大学学学学学学作业：作业：数据结构习题集数据结构习题集 P56 四、基础知识题四、基础知识题 9.9、9.21 P48 五、算法设计题五、算法设计题 9. 31 、9. 38
