數(shù)據(jù)結(jié)構(gòu) 9查找B

1、1 基本概念基本概念 9.1 9.1 靜態(tài)查找表靜態(tài)查找表 9.2 9.2 動態(tài)查找表動態(tài)查找表 9.3 9.3 哈希查找表哈希查找表 教材第教材第8 8、1111和和1212章省略，因章省略，因操作系統(tǒng)操作系統(tǒng)課程會涉及。課程會涉及。 2 特點(diǎn)：特點(diǎn)： 一、一、二叉排序樹的定義二叉排序樹的定義 二、二、二叉排序樹的插入與刪除二叉排序樹的插入與刪除 三、二叉排序樹的查找分析三、二叉排序樹的查找分析 四、平衡二叉樹四、平衡二叉樹 五五、B-B-樹和樹和B+B+樹樹 9.2 9.2 動態(tài)查找表動態(tài)查找表 表結(jié)構(gòu)在查找過程中動態(tài)生成。表結(jié)構(gòu)在查找過程中動態(tài)生成。 要求：要求： 對于給定值對于給定值k

2、ey,key, 若表中存在其關(guān)鍵字等于若表中存在其關(guān)鍵字等于keykey的記錄，則查找成功返回；的記錄，則查找成功返回； 典型的動態(tài)表典型的動態(tài)表二叉排序樹二叉排序樹 3 平衡二叉樹又稱平衡二叉樹又稱AVL樹，它是具有如下性質(zhì)的樹，它是具有如下性質(zhì)的 二叉樹：二叉樹： 為了方便起見，給每個結(jié)點(diǎn)附加一個為了方便起見，給每個結(jié)點(diǎn)附加一個數(shù)字?jǐn)?shù)字，給，給 出出該結(jié)點(diǎn)左子樹與右子樹的高度差該結(jié)點(diǎn)左子樹與右子樹的高度差。這個數(shù)字。這個數(shù)字 稱為結(jié)點(diǎn)的稱為結(jié)點(diǎn)的平衡因子平衡因子balance。這樣，可以得到這樣，可以得到 AVL樹的其它性質(zhì)：樹的其它性質(zhì)： 即即| |左子樹深度左子樹深度- -右子樹深度右

3、子樹深度| 1| 1 左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹； 所有結(jié)點(diǎn)的左、右子樹深度之差的絕對值所有結(jié)點(diǎn)的左、右子樹深度之差的絕對值 1 4 (a) (a) 平衡樹平衡樹 (b) (b) 不平衡樹不平衡樹 例：判斷下列二叉樹是否例：判斷下列二叉樹是否AVL樹？樹？ v任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1、0 或或 1；如果；如果 樹中任意一個結(jié)點(diǎn)的平衡因子的絕對值大于樹中任意一個結(jié)點(diǎn)的平衡因子的絕對值大于1， 則這棵二叉樹就失去平衡，不再是則這棵二叉樹就失去平衡，不再是AVL樹；樹； v對于一棵有對于一棵有n個結(jié)點(diǎn)的個結(jié)點(diǎn)的AVL樹，其樹，其高度保持在高度保持在

4、 O(log2n)數(shù)量級，數(shù)量級，ASL也保持在也保持在O(log2n)量級。量級。 0 0 0 1 1 1 1-1 -1 0 0 0 1 -1 5 如果在一棵如果在一棵AVL樹中插入一個新結(jié)點(diǎn)，就有可能樹中插入一個新結(jié)點(diǎn)，就有可能 造成失衡，此時必須造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)重新調(diào)整樹的結(jié)構(gòu)，使之恢，使之恢 復(fù)平衡。我們稱調(diào)整平衡過程為復(fù)平衡。我們稱調(diào)整平衡過程為平衡處理平衡處理。 現(xiàn)分別介紹這四種平衡處理。現(xiàn)分別介紹這四種平衡處理。 平衡處理可以歸納為四類：平衡處理可以歸納為四類： v LL平衡處理平衡處理 v RR平衡處理平衡處理 v LR平衡處理平衡處理 v RL平衡處理平衡處

5、理 6 0 0 1 13 3 0 0 3737 0 0 2424 例：例：請將下面序列構(gòu)成一棵請將下面序列構(gòu)成一棵平衡二叉排序樹平衡二叉排序樹： （ 13，24，37，90，53） 0 0 1313 0 0 3737 -1-1 1313 0 0 2424 -1-1 2424 1313 需要需要RR平衡處理平衡處理 (繞繞B左旋左旋,B為根）為根） 0 0 9090 -1-1 2424 -1-1 3737 0 0 5353 1 1 9090 3737 需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) (繞繞B先右旋后左旋）先右旋后左旋） 0 0 3737 0 0 9090 0 0 5353 0 0 3737 0 0

6、 9 90 0 0 0 5353 7 若在若在A的的左子樹的左子樹上插入左子樹的左子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至 2，需要進(jìn)行一次，需要進(jìn)行一次順時針旋轉(zhuǎn)順時針旋轉(zhuǎn)。 (以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 若在若在A的的右子樹的右子樹上插入右子樹的右子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從-1增加增加 至至-2，需要進(jìn)行一次，需要進(jìn)行一次逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)。 (以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 8 若在若在A的的右右子樹的子樹的左左子樹上插入子樹上插入結(jié)結(jié) 點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從-1增加至增加至-2， 需要需要先進(jìn)行先進(jìn)行順順時針旋轉(zhuǎn)，再

7、時針旋轉(zhuǎn)，再逆逆時時 針旋轉(zhuǎn)針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 若在若在A的的左左子樹的子樹的右右子樹上插入子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至 2，需要，需要先進(jìn)行先進(jìn)行逆逆時針旋轉(zhuǎn)，再時針旋轉(zhuǎn)，再 順順時針旋轉(zhuǎn)。時針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變 9 1 Status InsertAVL(Tbf=EH; t=1; /當(dāng)前樹空 9 else /當(dāng)前樹根就是要找的 if (e.key = Tdata.key) t=0; return

8、 0; 12 if (e.key = Tdata.key) /進(jìn)入左子樹 13 if (!InsertAVL(Tlchild, e, t) return 0; 14 if (t) 16 LH: LeftBalance(T); t=0; else /進(jìn)入右子樹 25 if (!InsertAVL(Trchild, e, t) return 0; 26 if (t) 28 LH: Tbf=EH; t=0; 30 EH: Tbf=RH; t=1; 32 RH: RightBalance(T); t=0; 37 return 1; 0 0 1313 0 0 3737 -1-1 13131313 0 0

9、 2424 -1-1 2424 In(13, 37, 0) 25 In(24, 37, 0); 26/32 RightBalance(13); t=1; 37 return 1; In(24, 37, 0) 25 In(Null, 37, 0); 26/30 T=24;RH; t=1; 37 return 1; 10 五、五、B-樹樹 1定義定義 2查找過程查找過程 3插入操作插入操作 4刪除操作刪除操作 5查找性能的分析查找性能的分析 11 1B-樹的定義樹的定義 B-樹是一種 平衡平衡 的 多路多路 查找查找 樹： 12 平衡樹(BF=0) 根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵 子樹； 其余

10、所有非葉結(jié)點(diǎn)均至少含有m/2棵子 樹，至多含有 m 棵子樹； 樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹 中的同一層次上； 13 非終端結(jié)點(diǎn)包含(n,A0, K1, A1, K2, A2, Kn, An ) 多個關(guān)鍵字多個關(guān)鍵字均自小至大自小至大有序排列，即：K1 K2 keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， p-keyi=Kkeyi+1 if (i0 else q=p; p=p-ptri; / q 指示 p 的雙親 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功 19

11、 在查找不成功之后，需進(jìn)行插入。 顯然，關(guān)鍵字插入插入的位置位置必定在最下最下 層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況： 3插入插入 1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個數(shù)nm， 不修改指針; 例如 20 2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個數(shù) n=m， 則需進(jìn)行“結(jié)點(diǎn)分裂”，令 s = m/2， 在原結(jié)點(diǎn)中保留 （A0，K1， ， Ks-1，As-1）； 建新結(jié)點(diǎn) （As，Ks+1， ，Kn，An）； 將（Ks，p）插入雙親結(jié)點(diǎn)；例如 3）若雙親為空，則建新的根結(jié)點(diǎn)。 例如 21 例如:下列為 3 階B-樹(子樹個數(shù)為2或3， 故又稱2-3樹) 50 20 40 80 插入關(guān)鍵字 = 60, 60 80

12、90, 60 80 90 90 50 80 60 30, 40 20 30 50 80 80 30 50 22 被刪結(jié)點(diǎn)不是最下層結(jié)點(diǎn)，借被刪關(guān)鍵字的右子樹中的 最小關(guān)鍵字； 被刪結(jié)點(diǎn)為最下層結(jié)點(diǎn)，（1）它的關(guān)鍵字個數(shù)不少， 刪除該關(guān)鍵字即可；（2）它的關(guān)鍵字個數(shù)不能減少： 要從其左(或右)兄弟結(jié)點(diǎn)“借”關(guān)鍵字，無關(guān)鍵字可借 時就進(jìn)行結(jié)點(diǎn)“合并”： （2.1）“有的借”左（右）兄弟結(jié)點(diǎn)中最大（最?。?的關(guān)鍵字上移至雙親，雙親結(jié)點(diǎn)中大于（小于）上 移關(guān)鍵字的關(guān)鍵字下移至被刪結(jié)點(diǎn)； （2.2）“沒的借合并”把被刪結(jié)點(diǎn)與其左（右）兄弟 結(jié)點(diǎn)以及雙親結(jié)點(diǎn)中分割二者的關(guān)鍵字合并在一起。 4刪除刪除保證關(guān)

13、鍵字的個數(shù)不能小于m/2-1 23 在B-樹中進(jìn)行查找時，其查找時間 主要花費(fèi)在搜索結(jié)點(diǎn)（訪問外存）上， 即主要取決于B-樹的深度樹的深度。 5查找性能的分析查找性能的分析 問：含 N 個關(guān)鍵字的 m 階 B-樹可 能達(dá)到的最大深度 H 為多少？ 24 第第 2 層層 2 個個 先推導(dǎo)每一層所含最少結(jié)點(diǎn)數(shù)： 第第 1 層層 1 個個 第第 H+1 層層 2 ( m/2 ) H-1 個個 第第 4 層層 2 ( m/2 )2 個個 第第 3 層層 2m/2 個個 反過來問： 深度為H的B-樹中， 至少含有多少個結(jié)點(diǎn)？ 25 假設(shè) m 階 B-樹的深度為 H+1，由于 第 H+1 層為葉子葉子結(jié)點(diǎn)

14、，而當(dāng)前樹中含有 N 個關(guān)鍵字，則葉子結(jié)點(diǎn)必為 N+1 個， N+12( m/2 )H-1 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1 由此可推得下列結(jié)果： 26 在含在含 N 個關(guān)鍵字的個關(guān)鍵字的 B-樹上樹上 進(jìn)行一次查找，需訪問的結(jié)點(diǎn)進(jìn)行一次查找，需訪問的結(jié)點(diǎn) 個數(shù)不超過個數(shù)不超過 log m/2 (N+1)/2)+1 結(jié)論：結(jié)論： 27 是是B-樹的一種變型樹的一種變型 四、四、B+樹樹 28 1B+樹的結(jié)構(gòu)特點(diǎn)：樹的結(jié)構(gòu)特點(diǎn)： 每個葉子結(jié)點(diǎn)中含有 n 個關(guān)鍵字和 n 個指向記錄的指針；并且，所有葉子葉子 結(jié)點(diǎn)彼此相鏈接鏈接構(gòu)成一個有序鏈表，其 頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)； 29 50 96 15 50 62 78 96 71 788 4 8 9 96 56 6220 26 43 50 3 8 15 sq root 每個非葉結(jié)點(diǎn)中的關(guān)鍵字 Ki 即為其相應(yīng)指針 Ai 所指子 樹中關(guān)鍵字的最大值； 所有葉子結(jié)點(diǎn)都處在同一層次 上，