《《算法与数据结构》教学课件第6章 字典和高级字典C语言描述（第2版）张乃孝编著》由会员分享，可在线阅读，更多相关《《算法与数据结构》教学课件第6章 字典和高级字典C语言描述（第2版）张乃孝编著（96页珍藏版）》请在金锄头文库上搜索。
1、6 集合与字典集合与字典 6.1 集合及其抽象数据类型*6.2 集合的实现*6.3 字典及其抽象数据类型6.4 字典的顺序表示6.5 字典的散列表示6.3 字典及其抽象数据类型6.3.1 基本概念 字典：是一种集合，其中每个元素由两部分组成，分别称为关键码和属性。这种包含关键码和属性得二元组称作关联。 对字典进行的操作主要有：检索、插入元素和删除元素。字典中最主要的运算是进行检索。 静态字典：一经建立就基本保持不变； 动态字典：经常需要改动。 存储方法存储方法：顺序法、散列法、二叉树法和B树。 存储方法的选择：考虑检索效率、元素的插入和删除是否简便。 检索效率的标准检索效率的标准：检索过程中和
2、关键码的平均比较次数，即平均检索长度ASL，定义为： ASL = pici 每个元素的检索概率相等时， pi=1/n。ni=16.3.2 抽象数据类型抽象数据类型ADT6.2 字典的抽象数据类型字典的抽象数据类型ADT dictionary isoperation Dictionary createEmptyDictionary(void) int search(Dictionary dic,KeyType key,Position p) int insert(Dictionary dic,DicElement ele) int delete(Dictionary dic,KeyType ke
3、y)end ADT dictionary6.4 字典的顺序表示字典的顺序表示定义如下typedef int KeyType;typedef int DataType;typedef struct KeyType key; /* 字典元素的关键码字段字典元素的关键码字段*/DataType value; /* 字典元素的属性字段字典元素的属性字段*/DicElement;typedef struct int MAXNUM;int n; /*字典中元素的个数字典中元素的个数 */ DicElement *element; SeqDictionary; 6.4.1 6.4.1 存储结构存储结构算法算
4、法6.11顺序检索算法顺序检索算法intseqSearch(SeqDictionary*pdic,KeyTypekey,int&position)/*在字典中顺序检索关键码为在字典中顺序检索关键码为key的元素的元素*/ inti;for(i=0;in;i+)/*从头开始向后扫描从头开始向后扫描*/if(pdic-elementi.key=key)position=i;return(1);/*检索成功检索成功*/position=pdic-n;return(0);/*检索失败检索失败*/6.4.2 6.4.2 算法的实现算法的实现l算法算法6.11 6.11 顺序检索算法顺序检索算法ASL =
5、 1*p1 +2* p2 + +n* pn = (1+2+n)/n (pi=1/n) = (n+1)/2=O(n) 优点是算法简单且适应面广，无论字典中元素是否有序均可使用。缺点是平均检索长度较大，特别是当n很大时，检索效率较低。6.4.2 6.4.2 算法的实现算法的实现6.4.3 有序顺序表与二分法检索 按照关键码大小排序的顺序表称为有序顺序表。 二分法检索又称折半检索。要求字典的元素在顺序表中按关键码排序（从小到大）。 05,10,18,25,27,32,41,51,68,73,99 05,10,18,25,27,32,41,51,68,73,99 05,10,18,25,27,32,4
6、1,51,68,73,99检索关键码2505,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,99检索关键码75l算法算法6.12 6.12 二分法检索算法二分法检索算法 条件：字典中的元素按关键码排序。 优点是比较次数少，检索速度快。缺点是要将字典按关键码排序，且只适用于顺序存储结构。算法算法6.12二分法检索算法二分法检索算法intbinarySearch(SeqDictionary*pdic,
7、KeyTypekey,int&position) /* 在字典中用二分法查找关键码为在字典中用二分法查找关键码为key的元素的元素 */intlow,mid,high;low=0;high=pdic-n-1;while(lowelementmid.key=key)/*检索成功检索成功*/position=mid;return(1);elseif(pdic-elementmid.keykey)high=mid-1;elselow=mid+1;/*要检索的元素在右半区要检索的元素在右半区*/position=low;return(0);/*检索失败检索失败*/折半查找的判定树l用一棵二叉树来用一棵
8、二叉树来描述折半描述折半查找过程：二叉树结点中查找过程：二叉树结点中的数值表示有序表记录中的数值表示有序表记录中的序号。的序号。虚黑线虚黑线表示查找表示查找2525比较过的记录，比较过的记录，虚红线虚红线表示查找表示查找7575经过的记录。经过的记录。记录在判定树上的层次恰记录在判定树上的层次恰为找到此记录时所需比较为找到此记录时所需比较的次数。的次数。l设每个记录查找概率相等，设每个记录查找概率相等，查找成功的平均查找长度：查找成功的平均查找长度：ASL（12233334+4+4+4)/11=33/11=3321868254173515992710 05,10,18,25,27,32,41,
9、51,68,73,996.5 6.5 字典的散列表示字典的散列表示 前面介绍的查找方法都是建立在前面介绍的查找方法都是建立在“比较比较”的基础的基础上，查找的效率依赖于查找过程中所进行比较的次数。上，查找的效率依赖于查找过程中所进行比较的次数。 理想的情况理想的情况是希望不进行任何比较，一次存取便能得是希望不进行任何比较，一次存取便能得到所查记录。这样就需要在关键码和记录的存储位置到所查记录。这样就需要在关键码和记录的存储位置之间建立一个确定的对应关系之间建立一个确定的对应关系. key 存储地址存储地址h 6.5.1 基本概念 6.5.2 散列函数 6.5.3 碰撞的处理 6.5.4 散列文
10、件散列函数散列函数： 使每个关键码都和结构中存储位置对应使每个关键码都和结构中存储位置对应,这样的一这样的一个对应关系称为个对应关系称为散列（哈希散列（哈希Hash）函数函数。 关键码关键码 存储地址存储地址碰撞碰撞：若：若key1 key2 ,h(key1)=h(key2). key1和和key2称为称为同义词同义词。h(key)的的值域所对应的值域所对应的地址空间称为地址空间称为基本区域基本区域。发生碰撞时，发生碰撞时，同义词可以存放在同义词可以存放在基本区域中未被占基本区域中未被占用的单元，也用的单元，也可以存放到另开的可以存放到另开的区域中。区域中。负载因子负载因子： 散列表中结点数散
11、列表中结点数 基本区域能容纳的结点数基本区域能容纳的结点数6.5.1 基本概念h = 关键码关键码经过经过散列函数散列函数得到一个随机地址，得到一个随机地址，以便使一组关键码的散列地址均匀地分布在以便使一组关键码的散列地址均匀地分布在逐个地址区间中，从而减少冲突。逐个地址区间中，从而减少冲突。 常用的散列函数有：常用的散列函数有：1 1 数字分析法数字分析法2 2 折叠法折叠法 3. 3. 中平方法中平方法 4. 4. 基数转换法基数转换法 5. 5. 除余法除余法6.5.2 散列函数1. 数字分析法数字分析法 假设关键码是以假设关键码是以r为基的数，并且哈希表中可为基的数，并且哈希表中可能现
12、的关键码都是事先知道的，则可取关键码的能现的关键码都是事先知道的，则可取关键码的若干数位组成散列地址。若干数位组成散列地址。 Key h(key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 3292. 折叠法折叠法 将关键码分割成几部分，然后取这几部分的叠加和将关键码分割成几部分，然后取这几部分的叠加和作为地址。作为地址。 key=582422241 58 | 2422 | 241 58 | 2422 | 241 8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4
13、2 2 1 1 0 6 4 2 7 2 13. 中平方法中平方法 先求出关键码的平方，然后取中间几位作为地址。先求出关键码的平方，然后取中间几位作为地址。 key=4731 (4731)2 = 22382361 h(key)=3824. 基数转换法基数转换法 把关键码看成基数为把关键码看成基数为r1的数，将它转换成基数为的数，将它转换成基数为r2的数，用数字分析法取中间几位作为散列地址。的数，用数字分析法取中间几位作为散列地址。r1和和r2最好互素。例如，最好互素。例如，key=236075, r1=13, r2=10, (236075)13=2*135+3*134+6*133+7*13+5
14、=(841547)10 h(key)=41545. 除余法除余法 取关键码被某个不大于散列表长度取关键码被某个不大于散列表长度m的数的数p除后所得余数为散列地址。数除后所得余数为散列地址。数p的选取：一般的选取：一般可选它为质数。可选它为质数。 h(key)=key % p; m=128, 256, 512, 1024 p=127, 251, 503, 1019实际工作中需视情况的不同而采用不同的散列函实际工作中需视情况的不同而采用不同的散列函数，通常需要考虑的因素有：数，通常需要考虑的因素有： A. 计算哈希函数所需时间计算哈希函数所需时间; B. 关键码的长度关键码的长度; C. 哈希表的
15、大小哈希表的大小; D. 关键码的分布情况关键码的分布情况; E. 记录的查找频率。记录的查找频率。总之，是总之，是“杂凑杂凑”出来的。出来的。 开地址法开地址法在在基本区域基本区域内形成一个内形成一个探查序列探查序列 Hi = (H(key) + di)MOD m, i = 1, 2, , k ( k m-1)其中：其中：m为表长，为表长，di为增量序列，可有多种取法：为增量序列，可有多种取法： A. di = 1, 2, 3, , m-1, 称称线性探查序列线性探查序列; B. di = i*h2(key), h2(key)是另一个是另一个散列函数，称散列函数，称 双散列探查序列双散列探查
16、序列; C. di = 12, -12, 22, -22, , k2, -k2 (k m/2)称为称为二次探查序列二次探查序列； D. di = 伪随机数序列，称伪随机数序列，称伪随机探查序列伪随机探查序列。 6.5.3 6.5.3 碰撞的处理碰撞的处理 当发生碰撞时，则沿探查序列进行查找，当发生碰撞时，则沿探查序列进行查找， 插入插入时，直到找到一个空单元；查找时，或查找到关时，直到找到一个空单元；查找时，或查找到关健码为健码为key的元素或查找到达一个空单元。例如：的元素或查找到达一个空单元。例如： K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25
17、5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h(key)=key%13; 1873100568992741513225 采用采用线性探测序列线性探测序列，容易出现，容易出现堆积堆积现象，即在处现象，即在处理同义词的过程中又添加了非同义词的冲突。理同义词的过程中又添加了非同义词的冲突。存储结构存储结构typedef int KeyTypetypedef int DataType;typedef struct KeyType key; DataType value;DicElement;typedef struct int m; DicElement *element;H
18、ashDictionary;typedef HashDictionary *PHashDictionary;（教材缺）（教材缺）算法算法6.13 6.13 创建空散列表创建空散列表PHashDictionaryPHashDictionary createEmptyDictionary(intcreateEmptyDictionary(int m) m) PHashDictionaryPHashDictionary phdphd = = new new HashDictionaryHashDictionary; ; if ( if (phdphd!=NULL)!=NULL) phdphd-ele
19、ment = -element = new new DicElementmDicElementm; if(phdif(phd-element)-element) phdphd-m = m;-m = m; for(for(intint i=0; im; i+) i=0; i-elementielementi.key.key = 0; = 0; return return phdphd; ; else else deletedelete phdphd; ; coutcout“Out of space!Out of space!”endlendl; ; return NULL; return NUL
20、L; 在散列表上进行查找和构造散列表的过程基本一在散列表上进行查找和构造散列表的过程基本一致。给定致。给定key值，根据散列函数求得散列地址，若表值，根据散列函数求得散列地址，若表中没有记录，则查找不成功；否则比较关键码，若和中没有记录，则查找不成功；否则比较关键码，若和给定值相等，则查找成功；否则根据造表时设定的冲给定值相等，则查找成功；否则根据造表时设定的冲突处理方法找突处理方法找“下一地址下一地址”，直到散列表某个位置为，直到散列表某个位置为空或表中所填记录的关键码等于给定值时为止。空或表中所填记录的关键码等于给定值时为止。 算法算法6.14 散列表的检索散列表的检索 算法算法6.15
21、散列表的插入散列表的插入散列表的查找散列表的查找算法算法6.14散列表的检索算法散列表的检索算法用线性探查法解决碰撞用线性探查法解决碰撞intlinearSearch(HashDictionary*phash,KeyTypekey,int*position)intd,inc;d=h(key); /*d为散列地址，散列函数为为散列地址，散列函数为h(key)*/for(inc=0;incm;inc+)if(phash-elementd.key=key)*position=d;return(1);/* 检索成功检索成功 */ elseif(phash-elementd.key=0)*positio
22、n=d;return(0);/检索失败，找到插检索失败，找到插入位置入位置d=(d+1)%phash-m;*position=-1;/*散列表溢出散列表溢出*/return(0);算法算法6.15散列表的插入算法散列表的插入算法用线性探查法解决碰撞用线性探查法解决碰撞intlinearInsert(HashDictionary*phash,DicElementele)intposition;if(linearSearch(phash,ele.key,&position)=1)/*散列表中已有关键码为散列表中已有关键码为key的结点的结点*/printf(“Findn”);elseif(posi
23、tion!=-1)phash-elementposition=ele;/*插入结点，忽略对插入结点，忽略对value字段的赋值字段的赋值*/elsereturn(0);/*散列表溢出散列表溢出*/return(1); K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h1(key)=key%13; h2(key)=key%11+1；187310 05689927 415132 25h1(25)=25%13=12;h1(25)+h2(25)=25%13+(25%11+1)=12+4=16
24、;h1(25)+2*h2(25)=25%13+2*(25%11+1)=12+8=20;双散列函数法双散列函数法 拉链法拉链法 设设基本区域基本区域长度为长度为m，建立建立m条条链表，将所有关链表，将所有关键字为同义词的记录存储在同一键字为同义词的记录存储在同一条条线性链表中。线性链表中。 K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h(key)=key%13; ，27，41，68， ，18，05, 32， ，73， 99， ，10， ，51，25 27 41 68 18 5 32
25、 73 99 10 51 25 图6.4 用拉链法解决碰撞 在外存上，同义词表可以采用顺序表或散列表。在外存上，同义词表可以采用顺序表或散列表。有时把存放同义词的表称为有时把存放同义词的表称为“桶桶”。 按按“桶桶”散列的文件由若干桶和一个桶目录构散列的文件由若干桶和一个桶目录构成成。6.5.4 散列文件 桶目录桶：由若干页块组成每个页块存放若干记录l作业：p. 198l复习题 2，3，4l算法题 3，4l网络课堂测试: 6 集合与字典 l上机实验5.2 5.3 5.67. 高级字典结构7.3 7.3 二叉排序树二叉排序树7.4 7.4 最佳二叉排序树最佳二叉排序树* *7.5 7.5 平衡二
26、叉排序树平衡二叉排序树 字典采用二叉排序树作为存储结构，既有较高的检索效率，又具有链式存储时元素插入、删除操作的灵活性。 二叉排序树二叉排序树定义定义 二叉排序树(Binary Sort Tree)或者是一棵空二叉树；或者具有下列性质的二叉树： A. 若它的左子树不空，则左子树上所有结点的 值均小于它的根结点的值； B. 若它的右子树不空，则右子树上所有结点 的值均大于它的根结点的值； C. 它的左右子树也分别为二叉排序树。7.3 二叉排序树二叉排序树实际上，折半查找法的判定树就是一棵二叉排序树。K= 18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251810
27、739968272541325105图7.5 二叉排序树示例structstruct BinSearchNodeBinSearchNode; ;typedeftypedef structstruct BinSearchNodeBinSearchNode * *PBinSearchNodePBinSearchNode; ; structstruct BinSearchNodeBinSearchNode KeyTypeKeyType key; key;/* /* 结点的关键码字段结点的关键码字段 * */ / PBinSearchNodePBinSearchNode llinkllink, , r
28、linkrlink; ; /* /* 二叉树的左、右指针二叉树的左、右指针 * */ / ; ; typedeftypedef structstruct BinSearchNodeBinSearchNode * *BinSearchTreeBinSearchTree; ;typedeftypedef BinSearchTreeBinSearchTree * *PBinSearchTreePBinSearchTree; ;二叉排序树的存储结构（llink_rlink)： L.keyT.keykey) 查左子树；查左子树； else 查右子树；查右子树； 算法7.1 二叉排序树的检索算法 TLR算
29、法算法7.1 7.1 二叉排序树的检索算法二叉排序树的检索算法intint search(PBinSearchTreesearch(PBinSearchTree ptreeptree, , KeyTypeKeyType key, key, PBinSearchNodePBinSearchNode *position) *position) PBinSearchNodePBinSearchNode p, q; p, q; p=* p=*ptreeptree; q=p; q=p; while(pwhile(p!=NULL) !=NULL) q=p; q=p; if(pif(p-key=-key=k
30、eykey) *position=p; return(1); ) *position=p; return(1); else else if(pif(p-key-keykeykey) p=p-) p=p-llinkllink; ; else p=p- else p=p-rlinkrlink; ; *position=q; return(0);*position=q; return(0); 当树中不存在关键字等于给定值的结点时，需要生成新结点并插入到二叉树中。而新插入的结点必定是一个叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。 算法： if ( 二叉排序树中查不到
31、该结点) 建立新结点； if (原二叉排序树是空树) 新结点作为根结点; else if (新结点key=key;p-llink=p-rlink=NULL;if(position=NULL)*ptree=p;elseif(keykey)position-llink=p;/插入插入的左子树的左子树elseposition-rlink=p;/*插入插入position的右子树的右子树*/return1; 若从空树出发，经过一系列插入操作后，可生成一棵二叉排序树。 例如，K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25187310056899274151322
32、5图7.7 二叉排序树 的生成过程示例 容易看出，中序遍历可以得到一个关键字的有序序列，这就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。 另外可以看到，每次插入的新结点都是树中一个叶子结点，因此在进行插入的时候不必移动其他结点，仅需改动某个结点的指针。由此可见： 二叉排序树既有折半查找的特性，又采用了链表作存储结构。因此是动态查找表的适宜结构。删除二叉排序树的某个指定结点后，仍然是二叉排序树。假设指针p指向要删除的结点, 指针parentp指向*p的父结点。 1. 若*p是叶子结点，由于删除叶子结点不破坏整棵树的结构，因此，只需要修改其双亲结点的指针。 2. 若*p只有左子
33、树PL或只有右子树PR，此时，只要令PL或PR的根结点直接代替*p即可.PR*p*parentpPl*p*parentp*parent *p PR*parent Pl *p二叉排序树结点的删除二叉排序树结点的删除3. 若*p的左右子树均不空，则从下图可知,在删除 *p 之前，中序遍历该二叉树得到的序列为L *p R 删除*p之后，为保持其它元素之间的相对位置不 变，可以有两种做法。rrLRr*pLRr第一种方法：令*p的左子树的根结点代替*p ，而*p的右子树为 的右子树; 在p的左子树中找出关键码最大的结点r，将r的右指针指向p的右子女，用p的左子女代替p结点。451873105992741
34、5132257.8 删除结点73的过程p为被删除的结点r为p的左子树中关键码最大的的结点 在p的左子树中找出关键码最大的结点r，将r的右指针指向p的右子女，用p的左子女代替p结点。4518731059927415132257.8 删除结点73的过程p为被删除的结点r为p的左子树中关键码最大的的结点 在p的左子树中找出关键码最大的结点r，将r的右指针指向p的右子女，用p的左子女代替p结点。181057.8 删除结点73的过程p为被删除的结点45992741513225r为p的左子树中关键码最大的的结点第二种方法： （a）按对称序周游p的左子树，找到关键码最大的 结点r，删除r（用r的左子女代替r
35、）； （b）用r结点代替被删除结点p。LRr*pLRrL r *p RL r R 删除r（用r的左子女代替r），用r结点代替被删除结点p 。4518731059927415132257.8 删除结点73的过程p为被删除的结点r为p的左子树中关键码最大的的结点 删除r（用r的左子女代替r），用r结点代替被删除结点p 。45185110599274132257.8 删除结点73的过程p为被删除的结点r为p的左子树中关键码最大的的结点 查找被删除结点*p； if(*p无左子女) 用*p的右子女代替*p； else 找*p的左子树中最右下结点*r； 用*r的右指针指向*p的右子女； 用*p的左子女代替
36、*p； 算法 7.4 从二叉排序树上删除一个结点算法算法7.4 7.4 二叉排序树的删除算法二叉排序树的删除算法intint delete(PBinSearchdelete(PBinSearch ptreeptree, , KeyTypeKeyType key) key) PBinSearchNodePBinSearchNode parentpparentp, p, r;, p, r; p=* p=*ptreeptree; ; parentpparentp=NULL;=NULL; while(pwhile(p!=NULL) !=NULL) if(pif(p-key=-key=keykey) b
37、reak; ) break; /* /* 找到了关键码为找到了关键码为keykey的结点的结点 * */ / parentpparentp=p;=p; if(pif(p-key-keykey)pkey)p=p-=p-llinkllink; ; /*/*进入左子树进入左子树 * */ / else p=p- else p=p-rlinkrlink; ; /*/*进入右子树进入右子树 * */ / if(pif(p=NULL) return 0;=NULL) return 0; /* /* 二叉排序树中无关键码为二叉排序树中无关键码为keykey的结点的结点 * */ /if(pif(p-llin
38、kllink=NULL) =NULL) /*/*结点结点* *p p无左子树无左子树* */ / if(parentpif(parentp=NULL) *=NULL) *ptreeptree=p-=p-rlinkrlink; ; /*/*被删除的结点是原二叉排序树的根结点被删除的结点是原二叉排序树的根结点* */ / else else if(parentpif(parentp-llinkllink=p) =p) parentpparentp-llinkllink=p-=p-rlinkrlink; ; /* /* 将将* *p p的右子树链到其父结点的左链上的右子树链到其父结点的左链上 * *
39、/ / else else parentpparentp-rlinkrlink=p-=p-rlinkrlink; ; /* /* 将将* *p p的右子树链到其父结点的右链上的右子树链到其父结点的右链上 * */ / else else /*/*结点结点* *p p有左子树有左子树* */ / r=p- r=p-llinkllink; ; while(rwhile(r-rlinkrlink!=NULL) r=r-!=NULL) r=r-rlinkrlink; ; /* /* 在在* *p p的左子树中找最右下结点的左子树中找最右下结点* *r */r */ r- r-rlinkrlink=p-
40、=p-rlinkrlink; ;/* /* 用用* *r r的右指针指向的右指针指向* *p p的右子女的右子女 * */ / if(parentpif(parentp=NULL) *=NULL) *ptreeptree=p-=p-llinkllink; ; else else if(parentpif(parentp-llinkllink=p)parentpp)parentp-llinkllink=p-=p-llinkllink; ; else else parentpparentp-rlinkrlink=p-=p-llinkllink; ; free(pfree(p););return 1
41、; return 1; /* /* 释放被删除结点释放被删除结点 * */ / 性能分析 在二叉排序树上查找关键字实际上是走了一条从根结点到某个结点的路径的过程，比较的次数等于路径长度加1。因此，比较的次数不超过树的深度+1。但是具有n个结点的二叉树可以有不同的形态，因此，对于不同形态的二叉排序树，其平均查找长度也是不同的。最坏的情况下蜕变为单支树，此时的平均查找长度为（n+1)/2。 在随机的情况下，平均性能为：P(n) = 2(1+1/n) ln n 由此可见，在随机情况下的平均查找长度和ln n是等数量级的，然而在某些情况下，还需进行“平衡化”处理。 n个结点按不同的次序插入到二叉排序树
42、中，有n!棵二叉排序树(其中有的形态相同) 。 图7.9 由同一组关键码构成的两棵形态不同的二叉排序树7.4 7.4 最佳二叉排序树最佳二叉排序树* *平衡二叉树定义 平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左右子树均为平衡二叉树，且左右子树的深度之差的绝对值不超过1。 若定义二叉树上结点的平衡因子BF(Balance Factor)为该结点的右子树的高度减去左子树的高度，在平衡二叉树上所有结点平衡因子只可能为-1, 0, 1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。 对于平衡二叉树来说，它的深度和logN是同数量级的，因此我们
43、希望任何初始序列构成的二叉排序树都是AVL树。 7.5 平衡二叉排序树7.5.1 基本概念-1-1-110001-1-200-1图7.14 平衡和不平衡二叉树示例最小不平衡子树: 指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树。27105118412500-1-112图 6.13 最小不平衡子树插入结点7.5.2 7.5.2 调整平衡的模式调整平衡的模式 设最小不平衡子树的根为A，调整的规律可归纳为下列四种： 1. LL型调整； 2. RR型调整； 3. LR型调整； 4. RL型调整； 上面的几种情况在经过平衡旋转处理后，以*b或*c为根的新子树为平衡二叉树，而且它的深度和插入之
44、前以*a为根的子树相同。因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行旋转处理即可。LL型调整操作示意图 (B)A()= ()B(A) 调整规则是将A的左子女B提升为新二叉树的根；原来的根A连同其右子树向右下旋转成为B的右子树；B的原右子树作为A的左子树。 27100-1BA27100-1BA05-2271000BA05051270-1BA100051800030-1-1-251270BA10005180030-10图6.15 LL型调整操作示例RR型调整操作示意图 ()A(B)= (A)B() 调整规则：将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下
45、旋转成为B的左子树；B的原左子树作为A的右子树。 275101BA275101BA732735100BA27051270 1BA1007341099730BA510274101000-1图6.17 RR型调整操作示例0990 1 12 LR型调整操作示意图 ()B(C)A()= (B)C(A) 调整规则设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；原C的父结点B连同其左子树向左下旋转成为新根C的左子树，原C的左子树成为B的右子树；原根A连同其右子树向右下旋转成为新根C的右子树，原C的右子树成为A的左子树。 51270-1BA100051800C51270CA1801016005
46、00 1B图6.19 LR型调整操作示例5127 1BA10005180-1C160-2 RL型调整操作示意图 ()A(C)B()= (A)C(B) 调整规则：设C为A的右子女的左子女，将A的孙子结点C提升为新二叉树的根，原来C的父结点B连同其右子树向右下旋转成为新根C的右子树，C的原右子树成为B的左子树；原来的根A连同其左子树向左下旋转成为新根C的左子树，原来C的左子树成为A的右子树。 51270 1BA1007341073510CA410B273001000 1图6.21 RL型调整操作示例000C51270 1BA1007341-103000-1 2C 设 在平衡二叉树上插入一个关键码为
47、key的结点,二叉树采用llink_rlink表示，结点中增加一个字段存储结点的平衡因子。算法中包括以下几个部分：6.5.2 6.5.2 插入元素的算法插入元素的算法（1）找最小不平衡子树。找插入位置时，令*A离插入位置最近，且平衡因子不为0的结点，若这样的结点不存在，则A指向根结点；若插入后使AVL树失去平衡，则*A是最小不平衡子树的根。（2）修改一些结点的平衡因子 路径： *A， ，新结点。插入前，仅*A的平衡因子不为0。插入后，从*A的子女开始，顺序扫描路径上的结点*P,若新结点插入*P的左子树中，则*P平衡因子变为1；否则变为-1。 (3)判别以*A为根的子树是否失去了平衡。 若*A的
48、平衡因子为0，则插入后不会； 若*A的平衡因子为1，且插入到*A的左子树，则失去平衡，进一步，若插入到*A的左子女的左子树，则采用LL型调整；若插入到*A的左子女的右子树，则采用LR型调整; 若*A的平衡因子为-1, 且插入到*A的右子树,则失去平衡，进一步,若插入到*A的右子女的右子树,则采用RR型调整;若插入到*A的右子女的左子树,则采用RL型调整;算法算法6.10 AVL树的检索和插入性能分析 含有n个结点的平衡二叉树的高度是h= O(log2n)。插入关键码为key的结点的时间耗费最大为树的深度O(log2n)。算法在查找插入结点的同时也找到最小不平衡子树。最小不平衡子树中平衡因子的调
49、整时间最大为最小不平衡子树的深度。而四种子树调整时间耗费为常数O( 1 ).因此， 整个算法的时间复杂度为 O(log2n). 最佳二叉排序树的检索效率是最好的，但是，当进行结点的插入或删除操作后，保持其最佳性的时间代价太大。平衡二叉排序树的检索效率与最佳二叉排序树的检索效率是同级的，因此，动态字典常采用平衡二叉排序树作为存储结构。 6.6 B6.6 B树和树和B B树树* *B树和B树用于外存文件的索引。 6.6.1 B树 6.6.2 B+树一、B树的定义 一棵m阶的B树，或为空树，或是满足下列特性的m叉树： （1）树中每个结点至多有m棵子树； （2） 除根之外的所有分支结点至少有m/2棵子
50、树； （3）若根结点不是叶子结点，则至少有两棵子树； （4） 有j个子女的非叶结点中恰好有j-1个关键码， 且 按递增顺 序排列，结点中包含的信息为 (p0, k1, p1, k2, , kj-1, pj)6.6 .1 B6.6 .1 B树树 其中ki(i=1,.,j-1)为关键码，且ki ki+1(i=1,j-2); pi(i=0,j-1)为指向子树根结点的指针，且pi-1所指子树中所有结点的关键码均小于ki(i=1,j-1), pj-1所指子树中所有结点的关键码均大于kj, j（ m/2 = j = m-1）为关键码的个数。 （ 5）所有叶子结点都在同一层上，实际上这些 结点不存在。 当m
51、=2时，m阶B树实际上就是二叉排序树。所以m阶B树是二叉排序树的推广。其查找过程和二叉排序树类似，它是一个沿指针查找结点和在结点的关键码中进行顺序查找交叉进行的过程。 实际应用中， m和内外存交换的单位有关，一般，m=1024 图6.22 一棵6阶的B树B树主要用于文件的索引 。结点类型可以如下说明：#define m3typedef struct BTNode int keyNum; /* 关键字个数 */ struct BTNode *parent; /* 指向父结点*/ KeyType keym+1; /* 关键字向量 */ struct BTNode *ptrm+1; /* 子树指针向
52、量 */ Record *recPtrm+1; /* 指向文件中的记录号 */ BTNode, *BTree;二. B树的运算 1. B树的检索 key ki ki+1 pi 首先在根结点的关键码集合中进行检索，若key= = ki ，则检索成功；否则， key一定在ki 和 ki+1 之间（存在某个i），沿pi继续查找，重复上述过程，直到检索成功，或pi为空，检索失败。性能分析 在B树是进行查找包含两种基本操作：（1）在B树中找结点；（2）在结点中找关键字。由于B树通常存储在磁盘上，因此前一操作是在磁盘上进行的，而后一操作是在内存中进行的，即在磁盘上找到指针p所指结点后，先将结点中信息读入内
53、存，然后查询。而在磁盘上进行操作比在内存中操作慢得多，因此在磁盘上进行查找的次数，即待查关键字所在结点在B树是的层次数，是决定B树查找效率的关键因素。 现在考虑最坏的情况：含n个关键字的m阶B树的最大深度为log m/2(n+1)/2 + 12. B树的插入 深度为h的m阶B树，新结点一般插入到h层，首先检索到第h层，确定插入结点位置。 （1）若被插入结点中关键码个数小于m-1，则插入。 （2）若被插入结点中关键码个数等于m-1，则引起 结点“分裂”。 可如下实现“分裂”： 假设*p结点中含有信息为：m,p0, (k1,p1), , (km, pm)将*p分裂为*p和*p两个结点，分别含有信息
54、为： *p ： m/21, p0, (k1,p1), (k m/21,pm/21) *p：(m- m/2, pm/2, (k m/2+1, p m/2+1), (km, pm)把关键字k m/2和指针*p一起插入到*p的双亲结点中。 375 400 045 112 236 375 400 560 631 670040 008110 050212 142135297 240237388 381378471 460435396 393553 502492629 626557图6.23 一棵6阶B树的插入示例3. B树的删除 在深度为h的m阶B树中删除一个关键码，首先检索到该关键码所在的结点,然后根
55、据不同情况进行删除。（1)若结点在第h层，且关键码数目大于m/2-1， 则只需从该结点中删去该关键码ki。（2）若结点在第h层，且关键码数目等于m/2-1， 该结点左兄弟（或右兄弟）结点中的关键码数目 大于m/21，则需调整被删除关键码的结点， 兄弟结点，以及父结点中的信息。方法：设父结 点 中的信息为：（p0, k1,p1,k2,p2,kxpx),由pi指向 被删除关键码的结点，其的信息为： （p 0, k 1,p 1,k 2,p 2,k y p y), 兄弟结点中的 信息为：（p 0, k 1 ,p 1 ,k 2 ,p 2 ,k z p z)。 则应将k(x+y)/2上移到父结点中，并将左
56、（或右） 兄第中大于（或小于） k(x+y)/2及父结点中的ki移 到被删除关键码的结点中。 (3) 若结点在h层，且关键码数目及其相邻的兄弟结 点中的关键码数目均等于m/21，则需合并结 点。假设该结点有右兄弟，且其右兄弟结点由双 亲结点中的指针pi所指，则在删去关键码之后， 它所在结点中剩余的关键码和指针，加上双亲结 点中的关键码ki一起，合并到pi所指兄弟结点中 （若没有右兄弟结点，则合并到左兄弟结点中）。(4) 若结点的层数小于h，设删除结点中第i个关键码 ki ，则用pi所指的子树中的最小关键码k与ki互换，然后再删除关键码ki 。 50 63 20 35 23 30 66 90 5
57、6 42 3 7 3035 （a) 一棵三阶B树 图6.24 (b) 从（a)中删除关键码66 （c) 从(b)中删除关键码42 50 63 20 3023 90 56 35 3 7 （d) 从 ( c ) 中删除关键码35图6.24 (e) 从（d)中删除关键码56 23 30 56 20 50 3 7 23 30 63 90 50 63 20 3023 90 56 35 3 7 （d) 从 ( c ) 中删除关键码35图6.24 (e) 从（d)中删除关键码56 23 30 56三. B树在索引文件中的应用 (B, ) (E, ) (C, ) (D, ) (F, ) (G, ) (A, )
58、 图6.25 用B树组织索引顺序文件B+树是B树的变形。一. B+树的定义： 一棵m阶的B树，或为空树，或是满足下列条件的m叉树： （1）树中每个结点至多有m棵子树； （2） 除根之外的所有分支结点至少有m/2棵子树； （3）若根结点不是叶子结点，则至少有两棵子树； （4） 有n棵子树的结点有n个关键码； （5）叶结点中存放数据文件中记录的关键码及指向该记录的指针（或存放数据文件分块后每块的最大关键码及指向该块的指针。叶结点按关键码值大小顺 序 链接。可以把每个叶结点看成一个基本索引块。 6.6 .2 B+6.6 .2 B+树树 (6) 所有分支结点可看成是索引的索引，使结点中仅包含它的各子结
59、点中最大（或最小）关键码及指向子结点的指针。一棵m阶的B树和B树的差异在于： （A）有n棵子树的结点中含有n个关键码； （B）所有的叶子结点中包含了全部关键码的信息，及指向含这些关键码记录的指针，且叶子结点的本身依关键码的大小从小到大顺序链接。 （C）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中最大（或最小）关键码。 通常在B树上有两个头指针，一个指向根结点，另一个指向关键码最小的叶子结点。 60 99 85 99 20 39 60 27 36 39 92 99 65 79 85 46 51 60 10 20图6.26 一棵三阶的B+树 二. B+树的运算 1. B+树的
60、检索 (1) 和B树的检索方式相似。从根结点开始进行随 机检索， key一定在ki 和 ki+1 之间（存在个i）， 沿pi继续查找，重复上述过程，直到检索到叶 结点，若key = = ki ，则检索成功；否则检索 失败。 （2） 从最小关键码开始沿叶结点链顺序检索。 2 . B+树的插入 和B树的插入相似，但总是在叶结点上进行，当 结点中原关键码个数等于m时，该结点分裂。 (3) B+树的删除 仅在叶结点中进行删除操作，在和兄第结点合并 时，父结点中作为分界的关键码不放入合并后的结 点中。三. B+树在索引顺序文件中的应用 主文件的每个页块作B+树的一个外部结点，并且 这些页块之间连成单链。
61、 B+树的树叶层是主文件的 稀疏索引，整个B+树构成多级索引。索引项就是B+ 树中一个关键码和它对应的指针所构成的二元组。 A D D E A B C 图6.27 用B+树组织索引顺序文件1. 静态字典（1）顺序表示 A. 顺序检索：简单，常用于未排序元素的检索， 但检索效率不高； B. 二分法检索：仅用于排序元素，检索效率较高当插入、删除运算时会引起大量数据的移动。（2）散列表示：检索操作达到近乎随机存取的速度 。但散列表示经常出现碰撞与堆积现象，增加 了检索长度。（3）二叉树表示二叉排序树：元素插入次序不同，会构成不同的二叉排序树。最佳二叉排序树 的平均检索长度为O(log2n) 。6.7
62、 字典的各种表示的比较2. 动态字典 平衡二叉排序树表示：维持较高的检索效率。3. 对于较大的必须存放在外存贮器上的字典，应 采用B树或B+树表示。B+树是B树的变种。B树 和B+树都能动态地调整，保持均衡，而使动态 字典保持较高的检索效率。小小 结结 字典是一种特殊的集合，其最主要的操作为字典中元素的检索。本章介绍了字典的各种存储表示及相应的检索方法，它们是字典的各种线性表示（例如：顺序表表示，链表表示和目录表表示等）、各种散列表示（例如：开地址法、拉链法和桶散列等）、各种二叉树表示（例如：一般的二叉排序树、最佳二叉排序树和平衡的二叉排序树等）以及各种多叉树表示（例如B树和B+树）。其中顺序表示的线性表、开地址法处理碰撞的散列表和最佳二叉排序树主要使用于静态或基本静态的字典；链表表示的线性表、拉链法处理碰撞的散列表、桶散列结构、平衡的二叉排序树、B树和B+树等较多地考虑到元素的动态处理，适合于组织各种动态的字典；其中B树、B+树和桶散列结构主要使用于外存的大型字典表示。 l作业：p.243 复习题 1、7、8 p.244 算法题 1l网络课堂测试：6 字典与高级字典l上机：实验5.4
