《数据结构 第7章 查找更新【ppt】》由会员分享，可在线阅读，更多相关《数据结构 第7章 查找更新【ppt】（81页珍藏版）》请在金锄头文库上搜索。
1、开场白12/08/20241内容提要v查找概论v静态查找表v动态查找表v哈希表12/08/20242查找概论12/08/20243v查找表(Search Table)：同一类型的数据元素（或记录）构成的集合。v关键字(Key)：数据元素中某个数据项的值，又称键值 。若某关键字可以唯一地标记一个记录，则称主关键字(Primary Key)。对于可以识别多个数据元素的关键字，称为次关键字(Secondary Key)。v查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。主关键码主关键字数据元素(记录）次关键字数据项（字段）查找表的种类12/0
2、8/20244v静态查找表(Static Search Table): 只作查找操作的查找表。v主要操作：v（1）查询某个“特定的”数据元素是否在查找表中v（2）检索某个“特定的”数据元素和各种属性。v应用：查字典/查个人信息等v动态查找表(Dynamic Search Table):在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。v主要操作：v（1）查找时插入数据元素v（2）查找时删除数据元素v应用：清理网站的注册用户等v查找结构：为提高查找效率而专门为查找操作设置的数据结构v如：线性表/树/散列表 等。内容提要v查找概论v静态查找表v动态查找表v哈希
3、表12/08/20245顺序表查找v顺序查找(Sequential Search)又叫线性查找，是最基本的查找技术。从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等，则表中没有所查记录，查找不成功。12/08/20246顺序表查找算法12/08/20247/* 顺序查找, a为数组, n为要查找的数组个数, key为要查找的关键字，朴素版 */1.int Sequential_Search(int *a, int n, int key)2. int i;
4、3. for (i=1; i=n; i+)4. if (ai = key)5. return i;6. return 0;/* 有哨兵顺序查找，改进版 */1.int Sequential_Search2(int *a, int n, int key) 2. int i; a0 = key; /* 设置a0为关键字值，我们称之为“哨兵” */3. for (i=n; ai!=key; -i);4. return i; /* 返回0则说明查找失败 */5./* 有哨兵顺序查找，教科书版 */1.int Search_Seq(SSTable ST, KeyType key)2. ST.elem0.
5、key = key;3. for (i=ST.length; !EQ(ST.elemi.key, key); -i);4. return i;5./* 静态查找表*/typedef struct ElemType *elem; int length;SSTable;查找操作的性能分析v平均查找长度(Average Search Length)：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。对于含有n个记录的表，查找成功时的平均查找长度为：其中：Pi为查找表中第i个记录的概率，且v顺序查找分析：假设n=ST.length，则顺序查找的平均查找长度为q假设每个记录的查找概率相
6、等，即则等概率情况下顺序查找的平均查找长度为q假设各个记录的查找概率不相等且已知，记录该如何排列才能提高检索效率？q如果查找概率预先未知，如何提高检索效率？q如果考虑查找不成功的情况，平均查找长度如何计算？(假设查找成功与不成功的可能性相同)12/08/20248有序表查找v书架上的书有序排放，查找起来比无序排列来得快。v有序表查找算法q折半查找q插值查找q斐波那契查找12/08/20249折半查找及算法实现12/08/2024101.int Binary_Search(int *a, int n, int key)2.3. int low, high, mid;4. low = 1;5. h
7、igh = n;6. while (low=high)7. 8. mid = (low+high)/2;9. if (keyamid)12. low = mid+1;13. else14. return mid;15. 16. return 0;17./* 调用参数*/a =0,1,16,24,35,47,59,62,73,88,99n = 10key = 62v折半查找技术，又称二分查找。它的前提是线性表中的记录必须是关键码有序且采用顺序存储。基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若小于，则在中间记录的左半区继续查找，否则在右半区继续查找
8、。不断重复，直到查找成功（或失败）。99887362594735241610a下标下标987654321010lowhighmidlowmidhighmidlowmid时间复杂度：O(logn)折半查找的性能分析12/08/20241147大了小了73大了小了24大了小了1大了小了35大了小了164759大了小了88大了小了6299/* 调用参数*/a =0,1,16,24,35,47,59,62,73,88,99n = 10key = 62平均搜索长度注意：对于需要频繁执行插入删除的数据集，不建议使用。插值查找及算法实现12/08/2024121.int Interpolation_Sear
9、ch(int *a, int n, int key)2.3. int low, high, mid;4. low = 1;5. high = n;6. while (low=high)7. 8. mid = low+(high-low)*(key-alow)/(ahigh-alow); /* 插值 */9. if (keyamid)12. low = mid+1;13. else14. return mid;15. 16. return 0;17./* 调用参数*/a =0,1,16,24,35,47,59,62,73,88,99n = 10key = 16折半查找需要查找几次？插值查找呢？v
10、为什么一定要折半，而不是折四分之一或者其他呢？插值查找：根据要查找的关键字key与查找表中最大最小记录的关键字比较后使用插值公式计算下一步查找范围的查找方法。时间复杂度：O(logn)注意：适合数据分布均匀情况，若极度不均则不是合适选择。斐波那契查找v基本思想：q当key=amid时，查找成功；q当keyamid时，新范围是第mid+1个到第high个，此时范围个数为Fk-2-1个。12/08/202413lowmidhighFk-1Fk-1-1Fk-2-134921813786553423121100.F下标下标0 7斐波那契查找的代码实现12/08/2024141.int Fibonacc
11、i_Search(int *a, int n, int key)2.3. int low, high, mid, i, k;4. low = 1; high = n; k = 0;5. while (nFk-1) k+;6. for (i=n; iFk-1; i+) 7. ai=an;8. while (low = high) 9. mid = low+Fk-1-1;10. if (key amid)14. low = mid+1; k = k-2;15. 16. else 17. if (mid = n)18. return mid;19. else20. return n;21. 22.
12、23.9988736259473524161034921813786553423121100.F下标下标a下标下标98765432101011129999./* 调用参数*/a =0,1,16,24,35,47,59,62,73,88,99n = 10key = 59lowhighmidk6highmidlow4midhigh3mid思考：三种mid的不同计算方式有什么影响?k-1k-1k-1k-1线性索引查找v问题:如何从几千万条记录中快速查找到需要的数据?v方法:建立索引,即把一个关键字与它对应的记录相关联.一个索引由多个索引项构成, 每个索引项至少需包含关键字和其对应的记录在存储器中的位
13、置等信息。v索引结构:q线性索引：将索引项集合组织为线性结构。也称索引表。我们将介绍三种线性索引。q树形索引q多级索引12/08/202415稠密索引v引子：对于经常在家里找不到东西的人，用一个小本子记录家里物品的位置将非常有帮助。v稠密索引：将每个记录对应一个索引项q索引项有序，以便使用有序查找算法查找。q数据量过大时产生性能问题12/08/202416012318263257489下标 关键码 指针5518263257895关键码其它数据项分块索引v引子：图书馆里的藏书是怎样分类摆放的？v分块索引：把数据集的记录分成若干块，使得“块内无序，块间有序”。v平均查找长度分析q假设n个记录被平均
14、分成m块，每块t条记录q设Lb为查找索引表的平均查找长度，则Lb=(m+1)/2q设Lw为块中查找记录的平均查找长度，则Lw=(t+1)/2q分块索引查找的平均查找长度为：ASLw=Lb+Lw=(n/t+t)/2+1q最佳情况是m=t即 n=mt=t2则ASLw=t+1=12/08/2024170125796最大关键码 块长 块首指针271318275234第一块5736第二块967762第三块分块索引表倒排索引v引子：搜索引擎如何达成这样快的查找效率呢？是在网页全文中查找匹配吗？v倒排技术（Inverted Index）：最简单最基础的搜索技术，基于索引表，索引项包括“次关键码”和“记录号表
15、”，其中，记录号表存储具有相同次关键码的所有记录的记录号（可以是指向记录的指针或者该记录的主关键字）。q例如，有两篇短文：1.Books and friends should be few but good.2.A good book is a good friend.12/08/202418英文单词文章标号a2and1be1book1,2but1few1friend1,2good1,2is2shoud1内容提要v查找概论v静态查找表v动态查找表v哈希表12/08/202419二叉排序树v之前介绍的线性表查找方法中，折半查找具有很高的效率(O(logn)，但是它使用的是顺序存储结构，查找表中的
16、数据增、删都不方便。v于是，我们考虑树形结构12/08/202420二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树6040803050689836二叉排序树的特点12/08/202421由BST性质可得：1.二叉排序树中任一结点x，其
17、左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。2.二叉排序树中，各结点关键字是惟一的。3.按中序遍历该树所得到的中序序列是一个递增有序序列。6040803050689836注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的“小于”改为“大于等于”，或将BST性质(2)里的“大于”改为“小于等于”，甚至可同时修改这两个性质。二叉排序树结点定义12/08/2024221./*/2./* 二叉排序树用的头文件 */3./* 文件名：bstree.h */4./*/5.#include6.#include7.typedef
18、 int datatype;8.typedef struct node /* 二叉排序树结点定义 */9. 10. datatype key; /* 结点值 */11. struct node *lchild,*rchild; /* 左、右孩子指针 */12.bsnode;13.typedef bsnode* bstree;二叉排序树的查找运算12/08/2024231.#include “bstree.h”2./*-二叉排序树的递归查找-*/3./* 在根指针t所指二叉排序树中递归地查找某关键字4. 等于key的数据元素，若查找成功，则返回指向5. 该数据元素结点的指针，否则返回空指针 */
19、6.bstree SearchBST(bsnode* t, datatype x)7. 8. if (t=NULL | x=t-key)9. 10. return t;11. 12. if (xkey) /*递归地在左子树中检索*/13. 14. return SearchBST(t-lchild, x); 15. 16. else /*递归地在右子树中检索*/17. 18. return SearchBST(t-rchild, x); 19. 20.对于一棵给定的二叉排序树，树中的查找运算很容易实现，其算法可描述如下：（1）当二叉树为空树时，检索失败；（2）如果二叉排序树根结点的关键字等于待
20、检索的关键字，则检索成功；（3）如果待检索的关键字小于二叉排序树根结点的关键字，则用相同的方法继续在根结点的左子树中检索；（4）如果待检索的关键字大于二叉排序树根结点的关键字，则用相同的方法继续在根结点的右子树中检索。二叉排序树的查找算法性能分析v在二叉排序树上进行检索的方法与二分检索相似，和关键字的比较次数不会超过树的深度。因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。 v在最坏的情况下，含有n个结点的二叉排序树退化成一棵深度为n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序检索相同，即ASL=（n+1）/2。v在最好的情况下，二叉排序树形态比较匀称，对于含有n个结点
21、的二叉排序树，其深度不超过log2n，此时的平均查找长度为O（log2n）。 12/08/20242430404650556065707580例如，对于右图中的两棵二叉排序树，其深度分别是4和10，在检索失败的情况下，在这两棵树上的最大比较次数分别是4和10；在检索成功的情况下，若检索每个结点的概率相等，则对于图（a）所示的二叉排序树其平均查找长度为：ASLa=对于图（b）所示的二叉排序树其平均查找长度为：ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.5（b）（a）6040703050 65804655 75二叉排序树的插入运算12/08/2024251.void Inse
22、rtBST(bstree &t, datatype x)2. 3. /* f用于保存新结点的最终插入位置 */4. bstree f, p;5. p = t;6. while (p) /* 查找插入位置 */7. if (x = p-key) 8. return;9. f = p; 10. p = (xkey)?p-lchild:p-rchild;11. 12. /* 生成待插入的新结点 */13. p = (bstree)malloc(sizeof(bsnode); 14. p-key = x;15. p-lchild = p-rchild = NULL;16. if (t=NULL) 17
23、. t = p; /* 原树为空 */18. 19. else 20. if (xkey) f-lchild = p;21. else f-rchild = p;22. 23.假设待插入的数据元素为x，则二叉排序树的插入算法可以描述为：1.若二叉排序树为空，则生成一个关键字为x的新结点，并令其为二叉排序树的根结点；2.否则，将待插入的关键字x与根结点的关键字进行比较，若二者相等，则说明树中已有关键字x，无须插入；若x小于根结点的关键字，则将x插入到该树的左子树中，否则将x插入到该树的右子树中去。1.将x插入子树的方法与在整个树中的插入方法是相同的，如此进行下去，直到x作为一个新的叶结点的关键字
24、插入到二叉排序树中，或者直到发现树中已有此关键字为止。二叉排序树的建立12/08/2024261.bstree CreatBST() /*根据输入的结点序列，建立一棵二叉排序树，并返回根结点的地址*/ 2. 3. bstree t=NULL;4. datatype key;5. printf(n请输入一个以-1为结束标记的结点序列：n);6. scanf(%d,&key); /*输入一个关键字*/7. while (key!=-1) InsertBST(&t,key); scanf(%d,&key); 8. return t; /*返回建立的二叉排序树的根指针*/9.对于输入实例（30，20，
25、40，10，25，45），创建二叉排序树的过程如下：（a）空树30（b）插入303020（c）插入20302040（d）插入40302040103020401025302040102545（e）插入10（f）插入25（g）插入45思考：1.对于输入实例（30，20，10，25，40，45）或（30，40，45，20，10，25），生成的二叉排序树一样吗？2.如果是（10，20，25，30，40，45）或（45，40，30，25，20，10）呢？二叉排序树的删除（一）v原则：从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足BST性质v删除操作的一
26、般步骤：(1) 进行查找：查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NULL)。开始查找，若树中找不到被删结点则返回，否则p指向被删结点。(2) 删去*p：删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。 根据二叉排序树的结构特征，删除*p可以分四种情况来考虑：q待删除结点为叶结点q待删除结点只有左子树，而无右子树q待删除结点只有右子树，而无左子树q待删除结点既有左子树又有右子树12/08/202427二叉排序树的删除（二）（情况1）待删除结点为叶结点，则直接删除该结点即可。若该结点同时也是根结点，则删除后二叉排序树变为空树。下图给出了一个删除叶结点的
27、例子：12/08/20242860407030503680457520删除叶子结点20和756040703050368045二叉排序树的删除（三）（情况2）待删除结点只有左子树，而无右子树。根据二叉排序树的特点，可以直接将其左子树的根结点替代被删除结点的位置。即如果被删结点为其双亲结点的左孩子，则将被删结点的唯一左孩子收为其双亲结点的左孩子，否则收为其双亲结点的右孩子。下图给出了一个例子。 12/08/20242960407030503680457520删除只有左子树的单孩子结点50604070304536807520二叉排序树的删除（四）（情况3）待删除结点只有右子树，而无左子树。与情况2类
28、似，可以直接将其右子树的根结点替代被删除结点的位置。即如果被删结点为其双亲结点的左孩子，则将被删结点的唯一右孩子收为其双亲结点的左孩子，否则收为其双亲结点的右孩子。下图给出了一个例子。12/08/20243060407030503680457520删除只有右子树的单孩子结点70604080305036 457520二叉排序树的删除（五）（情况4）待删除结点既有左子树又有右子树。根据二叉排序树的特点，可以用被删除结点中序下的前趋（或后继）结点代替被删除结点，同时删除其中序下的前趋（或后继）结点。而被删除的中序下的前趋(后继）结点必然无右（左）子树，因而问题转换为第 2 种情况或第 3 种情况。1
29、2/08/202431删除具有2棵子树的结点4060407030503880437520364560387030508043752036456043703050388075204536二叉排序树的删除（六）（情况4续）除此之外，还可以直接将被删结点的右子树代替被删除结点，同时将被删除结点的左子树收为被删结点右子树中序首点的左孩子。也可以直接将被删除结点的左子树代替被删除结点，同时将被删结点的右子树收为被删结点左子树中序尾点的右孩子。下图给出示例。12/08/20243260407030503680457520删除具有2棵子树的结点40605070303680457520607030503680
30、457520二叉排序树的删除的代码实现12/08/2024331./* 若二叉排序树T中存在关键字等于key的2. 数据元素时，则删除该数据元素结点，3. 并返回TRUE；否则返回FALSE */4.Status DeleteBST(BiTree &T, KeyType key)5.6. / 不存在关键字等于key的数据元素7. if (!T) 8. return FALSE; 9. else10. / 找到关键字等于key的数据元素11. if (EQ(key, T-data.key) 12. return Delete(T); 13. else if (LT(key, T-data.key
31、) 14. return DeleteBST(T-lchild, key);15. else 16. return DeleteBST(T-rchild, key);17. 18.19./* 从二叉排序树中删除结点p，20. 并重接它的左或右子树 */21.Status Delete(BiTree &p)22. / 右子树空则只需重接它的左子树23. if (!p-rchild)24. q = p; p = p-lchild; free(q);25. / 左子树空则只需重接它的右子树26. else if (!p-lchild) 27. q = p; p = p-rchild; free(q)
32、;28. 29. else / 左右子树均不空30. q = p; s = p-lchild;31. while (s-rchild) 32. q = s; s = s-rchild; 33. 34. p-data = s-data;35. if (q != p) 36. q-rchild = s-lchild;37. else 38. q-lchild = s-lchild;39. delete s;40. 41. return TRUE;42.思考：这段代码针对情况4采用了那种删除办法？二叉排序树中结点的删除操作的主要时间在于查找被删除结点及查找被删结点的右子树的中序首点上，而这个操作的时
33、间花费与树的深度密切相关。因此，删除操作的平均时间亦为O（log2n）平衡二叉树v二叉排序树上实现的插入、删除和查找等基本操作的平均时间虽然为O（log2n），但在最坏情况下，二叉排序树退化成一个具有单个分支的单链表，此时树高增至n，这将使这些操作的时间相应地增至O（n）。为了避免这种情况发生，人们研究了许多种动态平衡的方法，包括如何建立一棵“好”的二叉排序树；如何保证往树中插入或删除结点时保持树的“平衡”，使之既保持二叉排序树的性质又保证树的高度尽可能地为O（log2n）。v平衡二叉树又称为AVL树，它或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树
34、高度之差的绝对值不超过1。q此处规定二叉树的高度是二叉树的树叶的最大层数，也就是从根结点到树叶的最大路径长度，空的二叉树的高度定义为-1。q相应地，二叉树中某个结点的左子树高度与右子树高度之差称为该结点的平衡因子（或平衡度）。由此可知，平衡二叉树也就是树中任意结点的平衡因子的绝对值小于等于1的二叉树。 12/08/202434CBADGE101-1-1F00DBACGE001-1-2F00思考：这两棵树是不是平衡二叉树？平衡二叉树结点定义12/08/2024351.typedef struct2.3. ElemType data; / 结点的数据域4. int bf; / 结点的平衡因子5.
35、struct BSTNode *lchild, *rchild; / 左、右孩子指针6.BSTNode, * BSTNode;#define LH 1/ 左高1.#define EH 0/ 等高2.#define RH -1/ 右高平衡二叉树的插入算法v G.M.Adelson-Velskii和E.M.Landis在1962年提出了动态保持二叉排序树平衡的一个有效办法，后称为Adelson方法。下面介绍Adelson方法如何将一个新结点k插入到一棵平衡二叉排序树T中去。 vAdelson方法由三个依次执行的过程插入、调整平衡度和改组所组成：（1）插入：不考虑结点的平衡度，使用在二叉排序树中插入
36、新结点的方法，把结点k插入树中，同时置新结点的平衡度为0。 （2）调整平衡度：假设k0，k1，km=k是从根k0到插入点k路径上的结点，由于插入了结点k，就需要对这条路径上的结点的平衡度进行调整。q调整方法是：从结点k开始，沿着树根的方向进行扫描，当首次发现某个结点kj的平衡度不为零，或者kj为根结点时，便对kj与km-1之间结点进行调整。令调整的结点为ki （j i m），若k在ki的左子树中，则ki的平衡度加1；若k在ki的右子树中，则ki的平衡度减1；此时，kj+1，kj+2，km-1结点不会失去平衡，唯一可能失去平衡的结点是kj。若kj失去平衡，即kj的平衡因子不是-1，0和1时，便对
37、以kj为根的子树进行改组，且保证改组以后以kj为根的子树与未插入结点k之前的子树高度相同，这样，k0，k1，kj-1的平衡度将保持不变，这就是为何不需要对这些结点进行平衡度调整的原因。反之，若kj不失去平衡，则说明，新结点k的加入并未改变以kj为根的子树的高度，整棵树无需进行改组。（3）改组：改组以kj为根的子树除了满足新子树高度要和原来以kj为根子树的高度相同外，还需使改造后的子树是一棵平衡二叉排序树。12/08/202436AVL树插入结点失去平衡的调整方法（一）v下面具体讨论AVL树上因插入新结点而导致失去平衡时的改组方法v为叙述方便，假设在AVL树上因插入新结点而失去平衡的最小子树的根
38、结点为A（即A为距离插入结点最近的，平衡因子不是-1、0和1的结点）。失去平衡后的改组操作可依据失去平衡的原因归纳为下列四种情况分别进行。qLL型平衡旋转qRR型平衡旋转qLR型平衡旋转qRL型平衡旋转12/08/202437C CB BA ADDGGE E1 10 01 1-1-1-1-1F F0 00 0AVL树插入结点失去平衡的调整方法（二）v（1）LL型平衡旋转：由于在A的左孩子的左子树上插入新结点，使A的平衡度由1增至2，致使以A为根的子树失去平衡，如下图所示。此时应进行一次顺时针旋转，“提升”B（即A的左孩子）为新子树的根结点，A下降为B的右孩子，同时将B原来的右子树Br调整为A的
39、左子树。12/08/202438A2B1BLBrArhhhLL型A0B0BLBrArhhh1.void R_Rotate(BSTree &p)2.3. lc = p-lchild;4. p-lchild = lc-rchild;5. lc-rchild = p; 6. p = lc;7.plclcpAVL树插入结点失去平衡的调整方法（三）v（2）RR型平衡旋转：由于在A的右孩子的右子树上插入新结点，使A的平衡度由-1变为-2，致使以A为根的子树失去平衡，如下图所示。此时应进行一次逆时针旋转， “提升”B（即A的右孩子）为新子树的根结点，A下降为B的左孩子，同时将B原来的左子树BL调整为A的右子
40、树。12/08/202439A-2B-1BrBLALhhhRR型A0B0BrALBLhhh1.void L_Rotate(BSTree &p)2.3. rc = p-rchild;4. p-rchild = rc-lchild;5. rc-lchild = p; 6. p = rc;7.prcrcpAVL树插入结点失去平衡的调整方法（四）v（3）LR型平衡旋转：由于在A的左孩子的右子树上插入新结点，使A的平衡度由1变成2，致使以A为根的子树失去平衡，如下图所示。此时应进行两次旋转操作（先逆时针，后顺时针），即“提升”C（即A的左孩子的右孩子）为新子树的根结点；A下降为C的右孩子；B变为C的左孩
41、子；C原来的左子树CL调整为B现在的右子树；C原来的右子树Cr调整为A现在的左子树12/08/202440A2B-1ArhBLhLR型CCLh-1Crh-11A-1B0ArhBLhCLh-1Crh-1C0A2B0BLhCLh-1C 2ArhplcprcT1.2.L_Rotate(T-lchild);3.R_Rotate(T);4.Crh-1AVL树插入结点失去平衡的调整方法（五）v（4）RL型平衡旋转：由于在A的右孩子的左子树上插入新结点，使A的平衡度由-1变成-2，致使以A为根的子树失去平衡，如下图所示。此时应进行两旋转操作（先顺时针，后逆时针），即“提升”C（即A的右孩子的左孩子）为新子树
42、的根结点；A下降C的左孩子；B变为C的右孩子；C原来的左子树CL调整为A现在的右子树；C原来的右子树Cr调整为B现在的左子树。 12/08/202441B-1A0BrhALhCLh-1Crh-1C0A-2B1BrhALhRL型CLh-1Crh-1C11.2.R_Rotate(T-rchild);3.L_Rotate(T);4.A-2ALhC-1CLh-1B-1BrhCrh-1plcTprc平衡二叉树的插入算法描述综上所述，在平衡的二叉排序树t上插入一个新的数据元素x的算法可描述如下：v（一）若AVL树t为空树，则插入一个数据元素为x的新结点作为t的根结点，树的深度增1；v（二）若x的关键字和A
43、VL树t的根结点的关键字相等，则不进行插入；v（三）若x的关键字小于AVL树t的根结点的关键字，则将x插入在该树的左子树上，并且当插入之后的左子树深度增加1时，分别就下列不同情况进行分情形处理：q（1）若AVL树的根结点的平衡因子为-1（右子树的深度大于左子树的深度），则将根结点的平衡因子调整为0，并且树的深度不变； q（2）若AVL树的根结点的平衡因子为0（左、右子树的深度相等），则将根结点的平衡因子调整为1，树的深度同时增1；q（3）若AVL树的根结点的平衡因子为1（左子树的深度大于右子树的深度），则当该树的左子树的根结点的平衡因子为1时需进行LL型平衡旋转；当该树的左子树的根结点的平衡因
44、子为-1时需进行LR型平衡旋转。v（四）若x的关键字大于AVL树t的根结点的关键字，则将x插入在该树的右子树上，并且当插入之后的右子树深度增加1时，需要分别就不同情况进行处理。其处理操作和（三）中所述相对称，读者可以自行分析。 12/08/202442平衡二叉树插入新结点的过程示例12/08/202443结点序列（120，80，30，90，45，60）逐个插入一棵空的AVL树的过程如下：1200120180012028013001200800300120180-1300900120180030-1900450120180030-290045-16001201800300900450600B-树
45、（一）v前面所讨论的查找算法都是在内存中进行的，它们适用于较小的文件，而对较大的、不能一次全部放在内存而不得不存放在外存储器上的文件就不合适了。1972年R.Bayer和E.M.McCreight提出了一种称为B-树的多路平衡查找树，它能减少硬盘的读取次数,适合在磁盘等直接存取设备上组织动态的查找表。 vB-树的定义：B-树是一种平衡的多路查找树，在文件系统中，已经成为索引文件的一种有效结构，并得到泛的应用。q一棵m阶（m 3）B-树，或为空树，或为满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）若根结点不是叶子结点，则至少有两棵子树；。（待续） 12/08/2024442 50
46、 80root 160 153 143 122 197 188 1752 20 402 55 701 9021019例：一棵例：一棵3 3阶的阶的B-B-树树B-树（二）q一棵m阶（m 3）B-树，或为空树，或为满足下列特性的m叉树：（续前）（3）所有的非终端结点中包含下列信息 （n，p0，k1，p1，k2，p2，kn，pn）其中：ki（1 i n）为关键字，且kiki+1（1 i n）；pj（0 j n）为指向子树根结点的指针，且pj（0 j1时冲突是不可避免的。因此，散列存储必须考虑解决冲突的办法。v综上所述，对于Hash方法，需要研究下面两个主要问题：（1）选择一个计算简单，并且产生冲突
47、的机会尽可能少 的Hash函数；（2）确定解决冲突的方法。12/08/202461 = 散列表中结点的数目散列表中结点的数目基本区域能容纳的结点数基本区域能容纳的结点数USk1k2k3k5k40H(k1)H(k5)H(k2)=H(k4)H(k3)H(km-1)散列函数的构造12/08/202462构造哈希函数时的几点要求：1.哈希函数的定义域必须包括需要存储的全部关键字，如果哈希表允许有 m 个地址时, 其值域必须在 0 到 m-1 之间。2.哈希函数计算出来的地址应能均匀分布在整个地址空间中：若 key 是从关键字集合中随机抽取的一个关键字，哈希函数应能以同等概率取 0 到 m-1 中的每一
48、个值。3.哈希函数应是简单的，能在较短的时间内计算出结果。散列函数的构造方法（一）12/08/202463（1）除留余数法v选择一个适当的正整数P，用P去除关键字，取所得得余数作为散列地址，即： hash ( key ) = key % p p mv这个方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大质数比较好。例如 m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1019v适用情况：除留余数法的地址计算公式简单，而且在很多情况下效果较好，因此是一种常用的构造散列
49、函数的方法例如S=5，21，65，22，69，若m=7且H（x）=x % 7，则可以得到如下表所示的Hash表。0123456212265569散列函数的构造方法（二）12/08/202464（2）直接定址法直接定址法v散列函数是关键码的线性函数，即： H(key) = a key + b （a，b为常数）v适用情况：事先知道关键码，关键码集合不是很大且连续性较好。例：关键码集合为10, 30, 50, 70, 80, 90，选取的散列函数为H(key)=key/10，则散列表为 0 1 2 3 4 5 6 7 8 9103050708090散列函数的构造方法（三）12/08/202465（3
50、）数字分析法v根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址：v适用情况：能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。例：关键码为8位十进制数，散列地址为2位十进制数 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 7 散列函数的构造方法（四）12/08/202466（4）平方取中法v对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。v适用情况：事先不知道关键码的分布且关键码的位数不
51、是很大。例：散列地址为2位，则关键码123的散列地址为： (1234)21522756散列函数的构造方法（五）12/08/202467（5）折叠法v将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。 v适用情况：关键码位数很多，事先不知道关键码的分布。 例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位： 2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位叠加 2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 间界叠加散列函数的构造方法（六）12/08/202468（6）随机数法v选择一个随机函数，取关键字的
52、随机函数值作为它的散列地址。即： H(key) = random(key)v适用情况：通常，当关键字长度不等时采用此法构造散列地址比较恰当。 处理散列冲突的方法（一）（1）开放定址法v开放定址法的基本做法是在发生冲突时，按照某种方法继续探测基本表中的其它存储单元，直到找到一个开放的地址（即空位置）为止。显然这种方法需要用某种标记区分空单元与非空单元。v开放定址法的一般形式可表示为：Hi（k）=（H（k）+di）mod m（i=1，2，k（k m-1）其中，H（k）为键字为k的直接哈希地址，m为哈希表长，di为每次再探测时的地址增量。v当di=1，2，3，m-1时，称为线性探测再散列；当di=1
53、2，-12，22，-22，k2，-k2（k m/2）时，称为二次探测再散列；当di=随机数序列时，称为随机探测再散列。12/08/202469例如，有数据（654，638，214，357，376，854，662，392），现采用数字分析法，取得第二位数作为哈希地址，将数据逐个存放入大小为10的散列表（此处为顺序表）中。若采用线性探测法解决地址冲突，则8个数据全部插入完成后，散列表的状态如下表所示。3922146386543573768546620123456789处理散列冲突的方法（二）（2）再哈希法v采用再哈希法解决冲突的做法是当待存入散列表的某个元素k在原散列函数H（k）的映射下与其它数据
54、发生碰撞时，采用另外一个Hash函数Hi（k）（i=1，2，n）计算k的存储地址（Hi均是不同的Hash函数），这种计算直到冲突不再发生为止。 12/08/202470处理散列冲突的方法（三）（3）拉链法v拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T0.m-1，凡是散列地址为i的结点，均插入到以Ti为头指针的单链表中。v拉链法的缺点主要是指针需要用额外的空间，故当结点规模较小时，开放定址法较为节省空间。v例如，关键字集合为1，13，20，5，14，33，散列表长度m=5，现采用除余法为哈希函数
55、并采用拉链法解决地址冲突，所创建的Hash链表如下图所示。12/08/202471t0t1t2t3t451 20 3313 14 处理散列冲突的方法（四）（4）其他方法v除了上述三种方法外，还有差值法可解决地址冲突。这种方法在发生冲突时，处理原则以现在的数据地址加上一个固定的差值，当数据地址超出数据大小时，则让数据地址采用循环的方式处理。v另外，还可以建立一个公共溢出区的方法去解决冲突。即m个Hash地址用数组t0.m-1表示，称此表为基本表，每一个分量存放一个关键字，另外设立一个数组v0.n为溢出表。若关键字和基本表中关键字为同义词，不管它由Hash函数得到的Hash地址是什么，一旦发生冲突
56、，都填入溢出表。12/08/202472开放定址哈希表的结构定义12/08/2024731.int hashsize = 997, .; / 哈希表容量递增表,2. / 一个合适的素数序列3.typedef struct4. ElemType *elem; / 数据元素存储基址，动态分配数组5. int count; / 当前数据元素个数6. int sizeindex; / hashsizesizeindex为当前容量7.HashTable;8.#define SUCCESS 19.#define UNSUCCESS 010.#define DUPLICATE -1开放定址哈希表的插入实现1
57、2/08/2024741.Status InsertHash (HashTable &H, Elemtype e) 2. / 若开放定址哈希表H中不存在记录 e 时则进行插入，并返回OK；3. / 若在查找过程中发现冲突次数过大，则需重建哈希表4. c = 0;5. / 表中已有与 e 有相同关键字的记录6. if (SearchHash ( H, e.key, j, c ) = SUCCESS )7. return DUPLICATE; 8. else if ( c hashsizeH.sizeindex/2 ) 9. / 冲突次数c未达到上限，（阀值c可调）10. H.elemj = e;
58、 11. +H.count; 12. return OK; / 插入记录 e13. 14. else 15. RecreateHashTable(H); / 重建哈希表16. 开放定址哈希表的查找实现12/08/2024751.Status SearchHash (HashTable H, KeyType kval, int &p, int &c)2. 3. / 在开放定址哈希表H中查找关键字为kval的元素,若查找成功,以p指4. / 示待查记录在表中位置,并返回SUCCESS;否则,以p指示插入位置,并5. / 返回UNSUCCESS,c 用以计冲突次数,其初值置零,供建表插入时参考6.
59、p = Hash(kval);/ 求得哈希地址7. while ( H.elemp.key != NULLKEY / 该位置中填有记录8. & ( H.elemp.key != kval) ) / 并且关键字不相等9. collision(p, +c); / 求得下一探测地址p10. if ( H.elemp.key = kval )11. return SUCCESS; / 查找成功，p 返回待查记录位置12. else 13. return UNSUCCESS; / 查找不成功(H.elemp.key = NULLKEY)，14. / p返回的是插入位置15. 一个简化的哈希表实现12/0
60、8/2024761.#define SUCCESS 12.#define UNSUCCESS 03.#define HASHSIZE 124.#define NULLKEY -327685.typedef struct6.7. int *elem;8. int count;9.HashTable;10.int m = 0;11./* 初始化散列表 */12.Status InitHashTable(HashTable &H)13.14. int i;15. m = HASHSIZE;16. H.count = m;17. H.elem = (int*)malloc(m*sizeof(int);
61、18. for (i=0; im; i+)19. H.elemi = NULLKEY;20. return OK;21.22./* 散列函数 */23.int Hash(int key)24.25. return key%m;26.27./* 向散列表插入关键字 */28.void InsertHash(HashTable &H, int key)29.30. int addr；31. if (SearchHash(H, key, addr) =SUCCESS) return;32. addr = Hash(key);33. while (H.elemaddr != NULLKEY)34. a
62、ddr = (addr+1)%m;35. H.elemaddr = key;36.37./* 散列表查找关键字 */38.Status SearchHash(HashTable H, int key, int &addr)39.40. addr = Hash(key);41. while (H.elemaddr != key)42. 43. addr = (addr+1)%m;44. if (H.elemaddr=NULLKEY | addr=Hash(key)45. 46. return UNSUCCESS;47. 48. 49. return SUCCESS;50.哈希表查找性能分析12/
63、08/202477散列表的平均查找长度取决于负载系数和处理冲突的方法而不是记录个数，假设负载系数为，则：（1）如果用开开放放定定址址线线性性探探测测再散列法解决冲突，Hash表查找成功和查找不成功的平均查找长度Sn和Un分别为：SnUn（2）如果用二二次次探探测测再散列解决冲突，Hash查找成功和查找不成功的平均查找长度Sn和Un分别为：SnUn（3）如果用拉拉链链法法解决冲突，Hash表查找成功和查找不成功的平均查找长度Sn和Un分别为：SnUn使用时，直接删除本页！使用时，直接删除本页！精品课件，你值得拥有精品课件，你值得拥有！精品课件，你值得拥有精品课件，你值得拥有！使用时，直接删除本页！使用时，直接删除本页！精品课件，你值得拥有精品课件，你值得拥有！精品课件，你值得拥有精品课件，你值得拥有！使用时，直接删除本页！使用时，直接删除本页！精品课件，你值得拥有精品课件，你值得拥有！精品课件，你值得拥有精品课件，你值得拥有！总结回顾v主题：“查找”v重要概念：表/记录/关键字/静态查找表/动态查找表v顺序表查找和“哨兵”v有序查找：折半查找/插值查找/斐波那契查找v线性索引：稠密索引/分块索引/倒排索引v二叉排序树/平衡二叉树：构建/插入/删除/保持平衡vB-树/B+树：构建/插入/删除操作v散列表：散列函数的选择和处理冲突的方法12/08/202481
