CHAP9查找[修复的]

1、121. 查找表和查找查找表和查找（1）查找表）查找表是由是由同一类型同一类型的数据的数据元素元素(或记录或记录)构成的构成的集合集合。 由于由于“集合集合”中的数据元素之间中的数据元素之间存在着松散的关系，因此查找表是存在着松散的关系，因此查找表是一种应用灵便的结构。一种应用灵便的结构。查找的基本概念查找的基本概念 3关键字：关键字：是数据元素（或记录）中某是数据元素（或记录）中某个个数据项数据项的值，用以的值，用以标识标识（识别）一（识别）一个数据元素（或记录）。个数据元素（或记录）。（2）关键字）关键字 若此关键字可以识别若此关键字可以识别唯一的唯一的一个记一个记录，则称之为录，则称之为

2、“主关键字主关键字”。4 根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一个确定一个其关键字等于给定值的数据元素或其关键字等于给定值的数据元素或(记录记录).（3）查找）查找 若查找表中存在这样一个记录，则称若查找表中存在这样一个记录，则称“查找成功查找成功”，查找结果：，查找结果：给出整个记录给出整个记录的信息，或指示该记录在查找表中的位置的信息，或指示该记录在查找表中的位置； 否则称否则称“查找不成功查找不成功”，查找结果：，查找结果：给给出出“空记录空记录”或或“空指针空指针”。5 由于查找表中的数据元素之间不存在明由于查找表中的数据元素之间不存在明显的组织规律，因此不便于

3、查找。显的组织规律，因此不便于查找。 为了提高查找的效率，需要在查找表中为了提高查找的效率，需要在查找表中的元素之间人为地的元素之间人为地 附加某种确定的关系，附加某种确定的关系，换句话说，换句话说，用另外一种结构来表示查找表用另外一种结构来表示查找表。（4）如何进行查找）如何进行查找查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。6（5）查找的操作）查找的操作1）查询查询某个某个“特定的特定的”数据元素是否数据元素是否在查找表中；在查找表中；2）检索检索某个某个“特定的特定的”数据元素的各数据元素的各种属性；种属性；3）在查找表中）在查找表中插入插入一个数据元素；一个数据元素；4

4、）从查找表中）从查找表中删去删去某个数据元素。某个数据元素。7仅作仅作查询查询和和检索检索操作的查找表。操作的查找表。静态静态查找查找有时在查询之后，还需要将有时在查询之后，还需要将“查询查询”结结果为果为“不在查找表中不在查找表中”的数据元素的数据元素插入插入到到查找表中；或者，从查找表中查找表中；或者，从查找表中删除删除其其“查询查询”结果为结果为“在查找表中在查找表中”的数据的数据元素。元素。动态动态查找查找2.2.查找的查找的类型类型8 定义：定义：(Average Search Length) 3.3.平均查找长度平均查找长度niiiCPASL1iP为查找第i个记录的概率iC查找到第

5、i个记录时，已比较的次数99.1 静态静态查找查找9.2 动态动态查找查找9.3 哈哈希查找希查找109.1 静静 态态 查查 找找 11typedef struct ElemType *elem; int length; / 表的长度表的长度 SSTable;假设静态查找表静态查找表的顺序存储结构顺序存储结构：数据元素类型的定义为数据元素类型的定义为: :typedef struct keyType key; / 关键字域关键字域 / 其它属性域其它属性域 ElemType , TElemType ;129.1.1 顺序顺序查找查找9.1.2 有序有序查找查找9.1.3 索引索引顺序顺序13

6、 以线性表的顺序存储以线性表的顺序存储结构表示静态查找表。结构表示静态查找表。链表与之类似。链表与之类似。9.1.1 顺序顺序查找查找141. 顺序查找的基本思想顺序查找的基本思想 从表的一端开始，从表的一端开始，顺序扫描线性顺序扫描线性表，依次将扫描到的结点关键宇和给表，依次将扫描到的结点关键宇和给定值定值K相比较。相比较。若当前扫描到的结点若当前扫描到的结点关键字与关键字与K相等，则查找成功；若扫相等，则查找成功；若扫描结束后，仍未找到关键字等于描结束后，仍未找到关键字等于K的的结点，则查找失败。结点，则查找失败。1521 37 88 19 92 05 64 56 80 75 13 0 1

7、 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem例如：例如：假设给定值假设给定值 e=64,要求要求 ST.elemk = e, 问问: k = ?kk16int location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & !(*compare)(*p+,e) k+; if ( k=1;i-) for(i=ST.length;i=1;i-) if ( ST.elemi.key=keyST.

8、elemi.key=key) return i; return 0; 2.经典顺序查找算法经典顺序查找算法1821 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64改进改进(加哨兵加哨兵)19int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 /

9、 key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq,不需要每次和长度比较不需要每次和长度比较3.改进顺序查找算法改进顺序查找算法20在在等概率等概率查找的情况下，查找的情况下， 顺序表查找的平均查找长度顺序表查找的平均查找长度为：为：对对顺序表顺序表而言，而言，Ci = n-i+1(i=1n)nPi121111n)i(nnASLnissASL = nP

10、1 +(n-1)P2 + +2Pn-1+Pn4.算法分析算法分析niiiCPASL121 若查找概率无法事先测定，则查若查找概率无法事先测定，则查找过程采取的改进办法是，找过程采取的改进办法是，在每次查找在每次查找之后，将刚刚查找到的记录直接移至表之后，将刚刚查找到的记录直接移至表尾的位置上。尾的位置上。在在不等概率查找不等概率查找的情况下的情况下，ASLss 在在 PnPn-1P2P1时时取极小值。取极小值。22（1 1）优点）优点 算法简单，算法简单，且对表的结构无任何且对表的结构无任何要求，无论是用顺序还是用链表来存放要求，无论是用顺序还是用链表来存放结点，也无论结点之间是否按关键字有结

11、点，也无论结点之间是否按关键字有序，它都同样适用。序，它都同样适用。（2 2）缺点）缺点查找效率低，查找效率低，因此，当因此，当n n较大时不较大时不宜采用顺序查找。宜采用顺序查找。5.顺序查找的优缺点顺序查找的优缺点23 二分查找要求：二分查找要求：线性表是有序表，线性表是有序表，即表中结点按关键字有序，并且要用即表中结点按关键字有序，并且要用顺序存储结构。顺序存储结构。9.1.2 有序有序查找查找 若以若以有序表有序表表示静态查找表，则查表示静态查找表，则查找过程可以基于找过程可以基于“折半折半”进行。称为进行。称为二分查找或折半查找。二分查找或折半查找。241.二分查找的基本思想二分查找

12、的基本思想设设Rlow.highRlow.high是当前的查找区间是当前的查找区间 （1 1）首先确定该区间的中点位置；）首先确定该区间的中点位置；mid=(low+high)/2mid=(low+high)/2 （2 2）然后将待查的）然后将待查的K K值与值与Rmid.keyRmid.key比较：比较：若相等，则查找成功并返回此位置，否则若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。须确定新的查找区间，继续二分查找。 25若若Rmid.keyKRmid.keyK，则由表的有序性可知则由表的有序性可知Rmid.n.keysRmid.n.keys均大于均大于K K，因此

13、若表中存在关键，因此若表中存在关键字等于字等于K K的结点，的结点，则该结点必定是在位置则该结点必定是在位置midmid左左边的子表边的子表R1.mid-1R1.mid-1中中，故新的查找区间是左，故新的查找区间是左子表子表R1.mid-1R1.mid-1。类似地，类似地，若若Rmid.keyKRmid.keyK，则要查找的则要查找的K K必在必在midmid的右子表的右子表Rmid+1.nRmid+1.n中，中，即新的查找区间即新的查找区间是右子表是右子表Rmid+1.nRmid+1.n。下一次查找是针对新的。下一次查找是针对新的查找区间进行的。查找区间进行的。二分查找的基本思想二分查找的基

14、本思想2605 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找过程如下lowhighmidlow mid high midlow 指示查找区间的下界指示查找区间的下界; ;high 指示查找区间的上界指示查找区间的上界; ;mid = (low+high)/2。27int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid =

15、 (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; /继续在后半区间进行查找return 0; / 顺序表中不存在待查元素 / Search_Bin2.二分查找的算法二分查找的算法28先看一个具体的情况，假设：先看一个具体的情况，假设：n=113.二分查找判定树二分查找判定树63914-11-22-33-44-55-66-77-8

16、8-99-1010-1111-25781011i123456789 10 11Ci1223333444429（1 1）二分查找判定树的组成及其查找）二分查找判定树的组成及其查找圆结点即树中的内部结点。圆结点即树中的内部结点。树中圆结点内的数树中圆结点内的数字表示该结点在有序表中的位置。字表示该结点在有序表中的位置。外部结点：圆结点中的所有空指针均用一个虚外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。拟的方形结点来取代，即外部结点。树中某结点树中某结点i i与其左与其左( (右右) )孩子连接的左孩子连接的左( (右右) )分分支上的标记支上的标记“ ”表示：表示：当待

17、查关键字当待查关键字KRi.keyKRi.key ）时，应走左）时，应走左( (右右) )分支到达分支到达i i的左的左( (右右) )孩子，将该孩子的关键字进一步和孩子，将该孩子的关键字进一步和K K比较。比较。若相等，则查找过程结束返回，否则继续将若相等，则查找过程结束返回，否则继续将K K与树中与树中更下一层的结点比较。更下一层的结点比较。3063914-11-22-33-44-55-66-77-88-99-1010-1111-25781011所经过的内部结点为所经过的内部结点为6 6、9 9、1010，最后到达方形结，最后到达方形结点点9-109-10，其比较次数为，其比较次数为3 3

18、。例如：查找例如：查找k85，31假设假设 n=2h-1 并且查找概率相等并且查找概率相等则则 在在n50时，可得近似结果时，可得近似结果 （2）二分查找的平均查找长度）二分查找的平均查找长度 一般情况下，表长为一般情况下，表长为 n 的折半查找的的折半查找的判定树的深度和含有判定树的深度和含有 n 个结点的完全二叉个结点的完全二叉树的深度树的深度h相同。相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs324.二分查找的优点和缺点二分查找的优点和缺点虽然虽然二分查找的效率高二分查找的效率高，但是要将表按关但是要将表按关键字排序。键字排序。

19、而排序本身是一种很费时的运算。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费既使采用高效率的排序方法也要花费O(nlgn)的的时间。时间。二分查找只适用顺序存储结构。二分查找只适用顺序存储结构。为保持表为保持表的有序性，在顺序结构里插入和删除都必须移的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，动大量的结点。因此，二分查找特别适用于那二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的种一经建立就很少改动、而又经常需要查找的线性表。线性表。339.1.3索引查找索引查找(分块查找分块查找)1.分块分块查找查找分块有序的线性表分块有序的线性表+索引表索引表两

20、部分组成。两部分组成。012345678910 11 12 1317 08 21 19 14 31 33 22 25 40 52 61 78 4621 040 578 10顺序表顺序表索引表索引表索引顺序表的特点：索引顺序表的特点：块内无序块内无序，块间有序。块间有序。342.索引查找的思想索引查找的思想（1）由索引确定记录所在区间）由索引确定记录所在区间索引表是有序表，可采用索引表是有序表，可采用二分查找二分查找或或顺序查找顺序查找，以确定待查的结点在哪一，以确定待查的结点在哪一块。块。（2）在确定的区间内进行查找）在确定的区间内进行查找由于块内无序，只能用顺序查找。由于块内无序，只能用顺序

21、查找。 351 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表索引表查查38例如：例如：查查7036索引顺序查找的平均查找长度索引顺序查找的平均查找长度 = 查找查找“索引索引”的平均查找长度的平均查找长度 + 查找查找“顺序表顺序表”的平均查找长度的平均查找长度3.3.算法分析算法分析37ASLbs =Lb+Lw 其中：其中：Lb索引查找长度，索引查找长度，Lw块中查找长度，块中查找长度，每块含每块含s个记录，个记录，B

22、=n/s 1s)sn(2121s21bjs1jb1ASLs1ib1jbs2) 1(log2ssnASLbs（2）用折半查找确定所在的块）用折半查找确定所在的块（1）用顺序查找确定所在的块）用顺序查找确定所在的块38【例例】若表中有若表中有1000010000个结点，则应把它分成个结点，则应把它分成100100个块，每块中含个块，每块中含100100个结点。分别计算顺序个结点。分别计算顺序查找、二分查找和索引查找的平均查找长度。查找、二分查找和索引查找的平均查找长度。（2）二分查找）二分查找（1）顺序查找）顺序查找ASL=(n+1)/2=5001ASL=log2(n+1)-1=14（3）索引查找

23、）索引查找ASL2=log2(n/s+1)+s/2=57ASL1=(n/s+s)/2+1=10139查找方法比较查找方法比较ASL最大最大最小最小两者之间两者之间表结构表结构有序表有序表.无序表无序表 有序表有序表分块有序表分块有序表存储结构存储结构顺序结构顺序结构线性链表线性链表顺序结构顺序结构顺序结构顺序结构线性链表线性链表顺序查找顺序查找折半查找折半查找 分块查找分块查找409.2 动动 态态 查查 找找 419.2.1 二叉排序树（二叉查找树）二叉排序树（二叉查找树）9.2.2 平衡二叉树平衡二叉树429.2.1 二叉排序树二叉排序树（二叉查找树）（二叉查找树）1定义定义4查找算法查找

24、算法5插入算法插入算法6删除算法删除算法7查找性能的分析查找性能的分析2特点特点3存储结构存储结构43（1）若它的左子树不空，则）若它的左子树不空，则左子树上左子树上 所有所有结点的值结点的值均小于均小于根结点的值；根结点的值；1 1定义定义 二叉排序树二叉排序树或者是一棵空树；或者或者是一棵空树；或者是具有如下特性的二叉树：是具有如下特性的二叉树：（3）它的左、右子树）它的左、右子树也都也都分别分别是二叉是二叉 排序树排序树。（2）若它的右子树不空，则）若它的右子树不空，则右子树上右子树上 所有所有结点的值结点的值均大于均大于根结点的值；根结点的值；445030802090108540352

25、52388例如例如:是二叉排序树。是二叉排序树。66不不452 2、二叉排序树的特点、二叉排序树的特点（1 1） 二叉排序树中任一结点二叉排序树中任一结点x x，其左，其左( (右右) )子树子树中任一结点中任一结点y(y(若存在若存在) )的关键字必小的关键字必小( (大大) )于于x x的关的关键字。键字。（2 2） 二叉排序树中，各结点关键字是惟一的。二叉排序树中，各结点关键字是惟一的。（3 3） 按中序遍历该树所得到的按中序遍历该树所得到的中序序列是一个中序序列是一个递增有序序列递增有序序列。503080209010854035252388463.3.二叉排序树的存储结构二叉排序树的存

26、储结构typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;474二叉排序树的查找算法二叉排序树的查找算法1）若给定值）若给定值等于等于根结点的关键字，则查根结点的关键字，则查找成功；找成功；2）若给定值）若给定值小于小于根结点的关键字，则继根结点的关键字，则继续在左子树上进行查找；续在左子树上进行查找；3）若给定值）若给定值大于大于根结点的关键字，则继根结点的关键字，则继续在右子树上进行查找。续在右子树上进行查找。否则否则若二叉排

27、序树若二叉排序树为空为空，则查找不成功；，则查找不成功；4850308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 49从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条在查找过程中，生成了一条查找路径查找路径: 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;或者或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为

28、止。 查找成功查找成功 查找不成功查找不成功50Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指针在根指针 T 所指二叉排序树中递归地查找其所指二叉排序树中递归地查找其 / 关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功， / 则返回指针则返回指针 p 指向该数据元素的结点，并返回指向该数据元素的结点，并返回 / 函数值为函数值为 TRUE; / SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向

29、查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初始调用值为的结点的双亲，其初始调用值为NULL递归算法描述如下：递归算法描述如下：51if (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功查找不成功 p = T; return TRUE; / 查找成功SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找Search

30、BST (T-rchild, key, T, p ); / 在右子树中继续查找5230201040352523fT设设 key = 48fTfT22pfTfTTTTfffp53非递归算法描述如下：非递归算法描述如下：Status Search_BST (BiTree T, KeyType key, BiTree &p ) / 在根指针在根指针 T 所指二叉排序树中查找其所指二叉排序树中查找其 / 关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功， / 则返回指针则返回指针 p 指向该数据元素的结点，并返回指向该数据元素的结点，并返回 / 函数值为函数值为 TR

31、UE; / Search_BST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE54P=T;While( p) if ( EQ(key, p-data.key) ) return TRUE; / 查找成功查找成功else if ( LT(key, p-data.key) ) p=p-lchild; / 在左子树中继续查找在左子树中继续查找 else p=p-rchild; / 在右子树中继续查找在右子树中继续查找/end whilereturn FALSE; /

32、查找不成功查找不成功55 根据动态查找表的定义，根据动态查找表的定义，“插入插入”操作在查找不成功时才进行操作在查找不成功时才进行; ;5 5二叉排序树的插入算法二叉排序树的插入算法 若二叉排序树为空树，则新插入的若二叉排序树为空树，则新插入的结点为新的根结点；否则，结点为新的根结点；否则，新插入新插入的结点必为一个新的叶子结点，的结点必为一个新的叶子结点，其其插入位置由查找过程得到。插入位置由查找过程得到。56Status Insert BST(BiTree &T, ElemType e ) / 当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 / 数据

33、元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 / 回回 TRUE; 否则，不进行插入并返回否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 57s = new BiTNode; / 为新结点分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 为新的根结点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s

34、 为 *p 的左孩子else p-rchild = s; / 插入 *s 为 *p 的右孩子return TRUE; / 插入成功58(1)被删除的结点被删除的结点是叶子是叶子；(2)被删除的结点被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树；(3)被删除的结点被删除的结点既有左子树，也有右子树既有左子树，也有右子树。6二叉排序树的删除算法二叉排序树的删除算法可分可分三种情况三种情况讨论：讨论：和插入相反，删除在查找成功之后进行，和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。后，仍然保持二

35、叉排序树的特性。5950308020908540358832（1）被删除的结点是）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”6050308020908540358832（2）被删除的结点被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 40806150308020908540358832（3）被删除的结点）被删除的结点既有左子树，也有右

36、子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点被删结点前驱结点前驱结点被删关键字被删关键字 = 5062Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树若二叉排序树 T 中存在其关键字等于中存在其关键字等于 key 的的 / 数据元素，则删除该数据元素结点，并返回数据元素，则删除该数据元素结点，并返回 / 函数值函数值 TRUE，否则返回函数值，否则返回函数值 FALSE if (!T) return FALSE; / 不存在关键字等于key的数据元素 else /

37、 DeleteBST算法描述如下：算法描述如下： 63if ( EQ (key, T-data.key) ) / 找到关键字等于key的数据元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找64void Delete ( BiTree &p ) / 从二叉排序树中删除结点 p， / 并重接它的左子树或右子树 if (!p-rchild) el

38、se if (!p-lchild) else / Delete其中删除操作删除操作过程如下所描述： 65 / 右子树为空树则只需重接它的左子树右子树为空树则只需重接它的左子树q = p; p = p-lchild; delete(q);pp66/ 左子树为空树只需重接它的右子树左子树为空树只需重接它的右子树q = p; p = p-rchild; delete(q);pp67q = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱/ 左右子树均不空左右子树均不空p-data = s-data;if (q !=

39、 p ) q-rchild = s-lchild; /s有右子树else q-lchild = s-lchild;/s无右子树 / 重接*q的左子树delete(s);pqs687查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它均可按照平均查找长度的定义来求它的的 ASL 值，显然，由值相同的值，显然，由值相同的 n 个关个关键字，构造所得的不同形态的各棵二键字，构造所得的不同形态的各棵二叉排序树的平均查找长叉排序树的平均查找长 度的值不同，度的值不同，甚至可能差别很大。甚至可能差别很大。69由关键字序列由关键字序列 3，1

40、，2，5，4构造而得的二叉排序树构造而得的二叉排序树由关键字序列由关键字序列 1，2，3，4，5构造而得的二叉排序树，构造而得的二叉排序树，例如：例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.270 下面讨论平均情况下面讨论平均情况: 不失一般性，假设长度为不失一般性，假设长度为 n 的序列中有的序列中有 k 个关键字个关键字小于小于第一个关键字，则必有第一个关键字，则必有 n-k-1 个关键字个关键字大于大于第一个关键字第一个关键字,由它构造的二由它构造的二叉排序树叉排序树n-k-1k的平均查找长度是的平均查找长度是

41、n 和和 k 的函数的函数P(n, k) ( 0 k n-1 )71 假设假设 n 个关键字可能出现的个关键字可能出现的 n! 种排列种排列的可能性相同，则含的可能性相同，则含 n 个关键字的二叉个关键字的二叉排序树的平均查找长度排序树的平均查找长度10),(1)(nkknPnnPASL在在等概率等概率查找的情况下，查找的情况下，CnnnnPlog12)(729.2.2平衡二叉树平衡二叉树1. “平衡二叉树平衡二叉树”2. 失衡的类型及调整方法失衡的类型及调整方法3. “平衡二叉树平衡二叉树”的插入的插入4. “平衡二叉树平衡二叉树”查找性能分析查找性能分析731.平衡二叉树平衡二叉树(AVL

42、树树)定义：平衡二叉树又称定义：平衡二叉树又称AVL树，是二叉排序树，是二叉排序树的另一种形式。它或者是一棵空树，或者树的另一种形式。它或者是一棵空树，或者是具有下列性质的二叉树：是具有下列性质的二叉树：它的左子树和右它的左子树和右子树都是平衡二叉树，且左子树和右子树的子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过深度之差的绝对值不超过1。1RLhh结点的平衡因子：结点的平衡因子： 该结点的左子树高度减去它的右子树高度。即：该结点的左子树高度减去它的右子树高度。即：74例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树失去平衡的最小子树失去平衡的最小子树75平衡二叉

43、树存储结构平衡二叉树存储结构Typedef struct BSTNodeElemTypedata;intbf; /平衡因子平衡因子 struct BSTNode *lchild,*rchild;BSTNode,*BSTree;762.失衡的类型及调整方法失衡的类型及调整方法 （1）失衡的类型）失衡的类型54242586774265894258678LL型型：定义失去平衡的最小子树根节点定义失去平衡的最小子树根节点为为a，则该类不平衡可归纳为，在，则该类不平衡可归纳为，在a的左子的左子树根节点的左子树上插入导致的不平衡可树根节点的左子树上插入导致的不平衡可使用单向右旋平衡处理，可以记为使用单向右

44、旋平衡处理，可以记为左左左左-右右。（2 2）失衡的类型及调整方法）失衡的类型及调整方法5410543102543000右旋右旋79可归纳为可归纳为LLLL型型- -右旋右旋2ABBLBRh-1h1ARh-10h-1ABBLBRh-1hAR0在单向右旋平衡处理后在单向右旋平衡处理后BF(B)BF(B)由由1 1变变为为0 0，BF(A)BF(A)由由2 2变为变为0 0。80RR型型：在在a的右子树根节点的右子树上的右子树根节点的右子树上插入导致的不平衡可使用单向左旋平衡处插入导致的不平衡可使用单向左旋平衡处理，可以记为理，可以记为右右右右-左左。左旋左旋43580-10-1435819000

45、0-143581900-1-2-281可归纳为可归纳为RRRR型型- -左旋左旋在单向左旋平衡处理后在单向左旋平衡处理后BF(B)BF(B)由由-1-1变为变为0 0，BF(A)BF(A)由由-2-2变为变为0 0。ABBRBLh-1h-1-2ALh-1ABBRALh-1h0BLh-1082LR型型：在在3的左子树根节点的左子树根节点1的右子树上的右子树上插入节点插入节点2导致不平衡，可使用双向旋转：导致不平衡，可使用双向旋转：先使其子树左旋再整棵树右旋，可记为左先使其子树左旋再整棵树右旋，可记为左右右-左右。左右。先左旋先左旋458190003211-12045819000321211045

46、8190003002010后右旋后右旋83可归纳为可归纳为LRLR型型在双向旋转平衡处理后在双向旋转平衡处理后BF(A)BF(A)由由2 2变为变为-1-1，BF(B)BF(B)由由-1-1变为变为0 0，BF(C)BF(C)由由1 1变为变为0 0。CACLARh-1h-12CRh-21BBL-1h-1BLh-1CLh-1B0C0CRh-2AARh-1-184RL型：型：在在19的右子树根节的右子树根节点点25的左子树上插入节点的左子树上插入节点23导致不平衡，导致不平衡，可使用双向旋可使用双向旋转：先使其子树右旋再整棵转：先使其子树右旋再整棵树左旋，可记为右左树左旋，可记为右左-右左。右左

47、。先右旋先右旋后左旋后左旋45819-2-2030-2201025231045819-2-2030-220102325-10458230-1030201025190085可归纳为可归纳为RLRL型型在双向旋转平衡处理后在双向旋转平衡处理后BF(A)BF(A)由由-2-2变为变为0 0，BF(B)BF(B)由由1 1变为变为-1,BF(C)-1,BF(C)由由1 1变为变为0 0。ABRh-1-2CCLh-1CRh-21BAL1h-1ALh-1CLh-1A0C0CRh-2BBR-186旋转操作特点旋转操作特点(1)(1)对不平衡的最小子树操作。对不平衡的最小子树操作。(2)(2)旋转后子树根节点

48、平衡因子为旋转后子树根节点平衡因子为0 0。(3)(3)旋转后子树深度不变故不影响全旋转后子树深度不变故不影响全树，也不影响插入路径上所有祖先结树，也不影响插入路径上所有祖先结点的平衡度。点的平衡度。87例如例如:依次插入的关键字为依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转向右旋转一次一次先向右旋转先向右旋转再向左旋转再向左旋转88426589642895向左旋转一次向左旋转一次继续插入关键字继续插入关键字 9893.3.平衡二叉树插入算法思想平衡二叉树插入算法思想(1)(1)若是空树，插入节点作为根节点，树若是空树，插入节点作为根节点，树深度加深度加

49、1 1。(2)(2)插入节点插入节点keykey值等于根节点值等于根节点keykey值，则值，则不插入。不插入。(3)(3)插入节点插入节点keykey值小于根节点值小于根节点keykey值，插值，插入在左子树上，左子树深加入在左子树上，左子树深加1 1并且：并且：90插入在左子树上情况插入在左子树上情况1 1左子树深度左子树深度 右子树深度右子树深度LLLL型型插入前若根节点平衡因子为插入前若根节点平衡因子为1,1,插入后其插入后其左子树的平衡因子为左子树的平衡因子为1 1（左左），则单（左左），则单向右旋，旋转后根节点和右子树的平衡向右旋，旋转后根节点和右子树的平衡因子改为因子改为0 0，

50、树深不变。，树深不变。ABBLBRh-1h12ARh-1ABBLBRh-1h0ARh-1093插入在左子树上的情况插入在左子树上的情况4 4左子树深度左子树深度 右子树深度右子树深度LRLR型型插入前若根节点平衡因子为插入前若根节点平衡因子为1,1,插入后左子树的插入后左子树的平衡因子为平衡因子为-1-1（左右），则先左旋再右旋，旋（左右），则先左旋再右旋，旋转后根节点和其左子树的平衡因子改为转后根节点和其左子树的平衡因子改为0 0，右，右子树的平衡因子改为子树的平衡因子改为-1,-1,树深不变。树深不变。CACLARh-1h-12CRh-21BBL-1h-1BLh-1CLh-1B0C0CRh

51、-2AARh-1-194(4)(4)插入节点插入节点keykey值大于根节点值大于根节点keykey值，值，插入在右子树上，方法类似第插入在右子树上，方法类似第3 3步。步。95 在平衡树上进行查找的过程和二叉在平衡树上进行查找的过程和二叉排序树相同，因此，排序树相同，因此，查找过程中和给定查找过程中和给定值进行比较的关键字的个数不超过平衡值进行比较的关键字的个数不超过平衡 树的深度。树的深度。.平衡二叉树的查找性能分析平衡二叉树的查找性能分析 问：含问：含 n 个关键字的二叉平衡树个关键字的二叉平衡树可能达到的最大深度是多少？可能达到的最大深度是多少？96n = 0空树空树最大深度为最大深度

52、为 0n = 1最大深度为最大深度为 1n = 2最大深度为最大深度为 2n = 4最大深度为最大深度为 3n = 7最大深度为最大深度为 4先看几个具体情况:97反过来问，深度为深度为 h 的二叉平衡树平衡树中所含结点的最小值含结点的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情况下，一般情况下，N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用归纳法可证得，利用归纳法可证得， Nh = Fh+2 - 1Fh+2 h/ 5 其中：其中： = (1+ 5 )/298 因此，在二叉平衡树上进行查找时，因此，在二叉平衡树上进行查找时，

53、查找过程中和给定值进行比较的关键字查找过程中和给定值进行比较的关键字的个数和的个数和 log(n) 相当相当。 由此推得，深度为由此推得，深度为 h 的二叉平衡树的二叉平衡树中所含结点的最小值中所含结点的最小值 Nh = h+2/5 - 1 反之，含有反之，含有 n 个结点的二叉平衡树能个结点的二叉平衡树能达到的最大深度达到的最大深度 hn = log ( 5 (n+1) - 2 999.2.3、 B - 树树1定义定义2查找查找3插入插入4删除删除5查找性能的分析查找性能的分析100(1)树中每个结点至多有树中每个结点至多有m棵子树；棵子树；(2)若根结点不是叶结点，则至少有两棵子若根结点不

54、是叶结点，则至少有两棵子树；树；(3)除根之外的所有非终端结点至少有除根之外的所有非终端结点至少有 m/2 棵子树；棵子树；m m阶阶B-B-树或为空树树或为空树, ,或为满足下列特性或为满足下列特性m m叉树叉树1B-树的定义树的定义101(4)(4)所有非终端结点中包含下列信息：所有非终端结点中包含下列信息：(n,A0,K1,A1,K2,A2,(n,A0,K1,A1,K2,A2,Kn,An),Kn,An)其中：其中：KiKi为关键字，且均自小至大有序排为关键字，且均自小至大有序排列，即：列，即：K1 K2 K1 K2 Kn Kn ； Ai Ai为指向子树根结点的指针，且指针为指向子树根结点

55、的指针，且指针Ai-1Ai-1所指子树上所有关键字均小于所指子树上所有关键字均小于Ki Ki ； An An 所指子树上所有关键字均大于所指子树上所有关键字均大于Kn Kn ；（5 5）树中所有叶子结点均不带信息，且在）树中所有叶子结点均不带信息，且在树中的同一层次上。树中的同一层次上。102例如：例如：4阶阶B-树树 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96103 从根结点出发，从根结点出发，沿指针搜索结点沿指针搜索结点和和在在结点内进行顺序（或折半）查找结点内进行顺序（或折半）查找 两个过程两个过程交叉进行。交叉进行。2.查找查找 若若查找成

56、功查找成功，则返回指向被查关键字所，则返回指向被查关键字所在在结点的指针结点的指针和和关键字在结点中的位置关键字在结点中的位置；若若查找不成功查找不成功，则返回插入位置，则返回插入位置。104例如：查找例如：查找78，26，60 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96105在查找不成功之后，需进行插入。在查找不成功之后，需进行插入。显然，显然，关键字插入的位置必定在最下关键字插入的位置必定在最下层的非叶结点层的非叶结点，有下列几种情况：，有下列几种情况：3插入插入(1)插入后，该结点的关键字个数插入后，该结点的关键字个数nm， 不修改指针不修改

57、指针; ; 例如例如106(2)插入后，该结点的关键字个数插入后，该结点的关键字个数 n=m， 则则需进行需进行“结点分裂结点分裂”，令，令 s = m/2 ， 在原结点中保留在原结点中保留 （A0，K1，。，。， Ks-1，As-1）；）； 建新结点建新结点 （As，Ks+1，。，。 ，Kn，An）；）； 将（将（Ks，p）插入双亲结点）插入双亲结点；例如例如(3)若双亲为空，则若双亲为空，则建新的根结点建新的根结点。 例如例如107例如例如:下列为下列为 3 阶阶B-树树50 20 40 80 插入关键字插入关键字 = 60, 60 80 90, 60 80 90 90 50 80 60

58、30 40 20 30 50 808030 50108节点分裂的一般规律：节点分裂的一般规律：假设假设p p节点中已有节点中已有m-1m-1个关键字，当插入一个关键字，当插入一个关键字之后，节点中信息为：个关键字之后，节点中信息为： m,Am,A0 0,(K,(K1 1,A,A1 1),(K),(K2 2,A,A2 2),),(K,(Km m,A,Am m) )其中其中K Ki i K Ki+1i+1 ，1 1imim。 以中间关键字为界以中间关键字为界, ,把结点一分为二把结点一分为二为两个结点，并把中间的关键字向上插入为两个结点，并把中间的关键字向上插入到父结点上，若父结点已满，用通样的方

59、到父结点上，若父结点已满，用通样的方法继续分裂结点。法继续分裂结点。109 和插入的考虑相反，首先必须找到待删和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结关键字所在结点，并且要求删除之后，结点中点中关键字的个数不能小于关键字的个数不能小于 m/2 -1，否则，否则，要从其左要从其左(或右或右)兄弟结点兄弟结点“借调借调”关键字，关键字，若其左和右兄弟结点均无关键字可借若其左和右兄弟结点均无关键字可借(结结点中只有最少量的关键字点中只有最少量的关键字),则必须进行结则必须进行结点的点的“合并合并”。4删除删除110如在如在3 3阶阶B-B-树中依次删除关键字树中依次删除

60、关键字12,5012,50，5353，3737，分为三种情况，分为三种情况45abt24b53 90e3 12c37d50f61 70g100h3阶阶B-树树11145abt24b53 90e3 c37d50f61 70g100h(1)(1)被删关键字被删关键字(12)(12)所在节点所在节点(c)(c)中的关键中的关键字数目不小于字数目不小于 m/2m/2 -1-1，则只须从该节点，则只须从该节点(c)(c)中删去该关键字中删去该关键字(12)(12)和相应指针，和相应指针，树的其他部分不变。树的其他部分不变。删除关键字删除关键字121212112（2 2）被删关键字）被删关键字(50)(50)所在节点所在节点(f)(f)中的关键字数中的关键