【正文】 4 52 6 3 0 3 7 5 03 1 2 6 1 7 0 1 0 02 4 。前后兩部分成為兩個結點，中間的一個結點將其插入到父結點中。 添加關鍵字分兩種情況： 1．若添加后， 結點上關鍵字個數(shù)小于等于 m1(對應每個結點至多有 m棵子樹的限定條件 )，則插入結束； 4 53 7 5 03 1 2 6 1 7 0 1 0 02 4 5 3 9 0abec d fght一 棵 2 3 樹4 53 0 3 7 5 03 1 2 6 1 7 0 1 0 02 4 5 3 9 0abec d fght插 入 3 0 之 后數(shù)據(jù)結構 第 9章 查找 2．若添加后， 該結點上關鍵字個數(shù)為 m個 ，因而使該結點的子樹 超過 了m棵，這與 B樹定義不符，所以要進行調(diào)整，即 結點的 “ 分裂 ” 。若 m 階 B－樹有 n個關鍵字 ，則葉子結點即查找不成功的結點為 n+1(即 n個有序關鍵字形成的 n+1個中間區(qū)域 ) ； 由此可得 ? ? 1k)2m/(*21n ??? ? ? 1)2 1n(lo gk 2m/ ???即 ：在含有 n個關鍵字的 B樹上進行查找時，從根結點到關鍵字所在結點的路徑上涉及的結點數(shù)不超過 ? ? 12/1)(nlo g 2m/ ??數(shù)據(jù)結構 第 9章 查找 （ 4） B樹的插入： B樹的生成也是從 空樹 起，逐個插入關鍵字而得。 由 B樹定義： 第一層至少有 1個結點； 第二層至少有 2個結點； 由于除根結點外的每個非終端結點 至少有 ?m/2?棵子樹 ，則第三層至少有 2(?m/2?)個結點； … 依此類推，第 k+1層至少有 2(?m/2?)k1個結點。 因為 在磁盤上讀取結點信息 比 在內(nèi)存中進行關鍵字查找 耗時多，所以，在磁盤上讀取結點信息的次數(shù)，即B樹的層次樹 是決定 B樹查找效率的 首要因素 。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹 ， 深 度 為 4abcd efgh it例如：查找關鍵字 41 數(shù)據(jù)結構 第 9章 查找 （ 3） B樹的查找分析： B樹的查找是由 兩個基本操作 交叉進行的過程，即： ⑴在 B樹上找結點； ⑵在結點中找關鍵字。 若查找某個關鍵字，則在到達某個結點時，先在結點（ 有序表）中查找，若找到，則 查找成功 ；否則，到按照對應的指針信息指向的子樹中去查找，當?shù)竭_葉子結點時，則說明樹中沒有對應的關鍵字，查找失敗 。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹 ， 深 度 為 4abcd efgh it數(shù)據(jù)結構 第 9章 查找 ⑤ 所有的葉子結點 都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空）。 Ai (i=0,1,…,n) 為指向子樹根結點的指針，且指針 Ai1 (i=1,2, …n 1)所指子樹中所有結點的關鍵字 均大于 Ki，小于 Ki+1 ， A0所指子樹中所有結點的關鍵字 均小于 K1， An所指子樹中所有結點的關鍵字 均大于 Kn。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹 ， 深 度 為 4abcd efgh it數(shù)據(jù)結構 第 9章 查找 （ 1） B樹的定義： 一棵 m階 的 B樹，或者為空樹，或為滿足下列特性的 m叉樹： ① 樹中 每個結點 至多有 m棵 子樹； ② 若 根結點 不是葉子結點，則至少有 兩棵 子樹； ③ 除根結點之外的所有 非終端結點至少 有 ?m/2? 棵子樹； 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹 ， 深 度 為 4abcd efgh it數(shù)據(jù)結構 第 9章 查找 ④ 所有的非終端結點 中包含以下信息數(shù)據(jù)： (n, A0, K1, A1, K2, …, K n， An)。 } } 數(shù)據(jù)結構 第 9章 查找 例：按下述次序輸入關鍵字： e, i, p, k, m, l, b，試畫出AVL樹的構造與調(diào)整過程。 R_Rotate(Tlchild)。 break。 case 1: Tbf =1。 case 0: Tbf=lcbf=0。 lcbf=1。 case 1: rd=lclchild。 L_Rotate(T)。 lc=Trchild。 數(shù)據(jù)結構 第 9章 查找 0 0 1 在 A的右子樹的左子樹上增 加一個結點 2 1 1 順時針旋轉 逆時針旋轉 1 0 0 數(shù)據(jù)結構 第 9章 查找 void LeftBalance(BSTree amp。結點 A的 平衡因子 變?yōu)?2，發(fā)生了不平衡； 2) 從結點 A起沿插入路徑選取 3個結點 A、 C和 D，它們位于一條形如 “ ?” 的折線上，需要進行先順時針旋轉再逆時針旋轉的操作； 3) 首先以 結點 D為旋轉軸 ，將 結點 C順時針 旋轉 ，以 D代替原來 C的位置。 R_Rotate(T)。} rdbf=0。 lcbf=1。 break。 break。 switch(rdbf){ case 1: Tbf=1。 break。 switch(lcbf){ case 1: Tbf = lcbf = 0。T){//左平衡化的算法 BSTree lc, rd。 3) 首先以 結點 E為旋轉軸 ，將 結點 B逆時針 旋轉 ，以 E代替原來 B的位置 。結點 A的平衡因子變?yōu)?+2，發(fā)生了不平衡 。 p=lc。 prchild=lclchild。p){ //RR型旋轉的算法， p對應示例中 A結點 BSTree lc。 2) 為使樹恢復平衡，從 A沿插入路徑 連續(xù)取 3個結點 A、 C和 E，它們處于一條方向為“ \”的直線上，以結點 C為旋轉軸，將結點 A逆時針旋轉 。 p=lc。 plchild=lcrchild。p){ //LL型旋轉的算法， p對應示例中 A結點 BSTree lc。 2) 為使樹恢復平衡，從 A沿插入路徑 連續(xù)取 3個結點 A、 B和 D，它們處于一條方向為“ /”的直線上，以結點 B為旋轉軸，將結點 A順時針旋轉 。 如果在某一結點發(fā)現(xiàn)高度不平衡，停止回溯。此時必須調(diào)整樹的結構，使之 平衡化 。 平衡二叉樹的深度為 O(log N)(其中 N為結點個數(shù) )，它的平均查找長度也是 O(log N) 1100 110 10 10( a )2 100 100 20 10( b )10注意 ：完全二叉樹必為平衡樹，平衡樹不一定是完全二叉樹。 與折半查找的判定樹比較： ?查找長度都不超過樹的深度； ?折半查找的判定樹唯一，而二叉排序樹是動態(tài)生成的，不唯一； 二叉排序樹的形態(tài)與關鍵字的初始序列有關， 例如：關鍵字序列 {45， 24， 53， 12， 37， 93} 與關鍵字序列 {12， 24， 37， 45， 53， 93} 構造的二叉排序樹如圖所示： 9 34 52 45 31 23 7數(shù)據(jù)結構 第 9章 查找 9 34 52 4 5 31 2 3 79 34 52 45 31 23 7在 等概率 的前提下，下面兩棵二叉排序樹的平均查找長度為： 6/146/)3*32*21(61?????? ii iCP 6/216/)654321(61????????? ii iCP 因此，在二叉排序樹中進行查找的平均查找長度和二叉樹的形態(tài)有關， 最壞情況 : （ n+1)/2（單支樹） 最好情況 ： log2n（與二分查找的判定樹相似） 數(shù)據(jù)結構 第 9章 查找