大連海事計科9查找14-15周b

1、1 基本概念9.1 靜態(tài)查找表9.2 動態(tài)查找表9.3 哈希查找表第9章 查找教材第8、11和12章省略，因操作系統(tǒng)課程會涉及。2特點：一、二叉排序樹的定義二、二叉排序樹的插入與刪除三、二叉排序樹的查找分析四、平衡二叉樹五、B-樹和B+樹9.2 動態(tài)查找表表結(jié)構(gòu)在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key 的記錄。典型的動態(tài)表二叉排序樹3四、平衡二叉樹平衡二叉樹又稱AVL樹，它是具有如下性質(zhì)的二叉樹：為了方便起見，給每個結(jié)點附加一個數(shù)字，給出該結(jié)點左子樹與右子樹的高度差。這個數(shù)字稱為結(jié)點的平衡因子balance。這樣

2、，可以得到AVL樹的其它性質(zhì)：即|左子樹深度-右子樹深度| 1左、右子樹是平衡二叉樹；所有結(jié)點的左、右子樹深度之差的絕對值 14(a) 平衡樹 (b) 不平衡樹例：判斷下列二叉樹是否AVL樹？任一結(jié)點的平衡因子只能取：-1、0 或 1；如果樹中任意一個結(jié)點的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對于一棵有n個結(jié)點的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。00011-1-120001-15如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡處理?，F(xiàn)分別介紹這四種平

3、衡處理。平衡處理可以歸納為四類： LL平衡處理 RR平衡處理 LR平衡處理 RL平衡處理6013037024例：請將下面序列構(gòu)成一棵平衡二叉排序樹： （ 13，24，37，90，53）013037-113024-124-213需要RR平衡處理(繞B左旋,B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞B先右旋后左旋）037090053037090053 7若在A的左子樹的左子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要進行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要進行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）

4、2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：8若在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要先進行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要先進行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變91 Status InsertAVL(&T, e, &t) 5 if (!T) ;Tbf=EH; t=1; /當(dāng)前樹空9 else /當(dāng)前樹根就是要找的if (e.key = Tdat

5、a.key) t=0; return 0;12 if (e.key = Tdata.key) /進入左子樹13 if (!InsertAVL(Tlchild, e, t) return 0;14 if (t)16 LH: LeftBalance(T); t=0;else /進入右子樹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; 013037-113-213024-124In(13,

6、 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;prc10五、B-樹1定義2查找過程3插入操作4刪除操作5查找性能的分析111B-樹的定義B-樹是一種 平衡 的 多路 查找 樹：12平衡樹(BF=0)根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹；其余所有非葉結(jié)點均至少含有m/2棵子樹，至多含有 m 棵子樹；樹中所有葉子結(jié)點均不帶信息，且在樹中的同一層次上；13非終端結(jié)點包含(n,A0, K1, A

7、1, K2, A2, Kn, An )多個關(guān)鍵字均自小至大有序排列，即：K1 K2 keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的雙親 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功19在查找不成功之后，需進行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點，有下列幾種情況：3插入1）插入后，該結(jié)點的關(guān)鍵字個數(shù)nm，

8、 不修改指針; 例如202）插入后，該結(jié)點的關(guān)鍵字個數(shù) n=m， 則需進行“結(jié)點分裂”，令 s = m/2， 在原結(jié)點中保留 （A0，K1， ， Ks-1，As-1）； 建新結(jié)點 （As，Ks+1， ，Kn，An）； 將（Ks，p）插入雙親結(jié)點；例如3）若雙親為空，則建新的根結(jié)點。 例如21例如:下列為 3 階B-樹(子樹個數(shù)為2或3，故又稱2-3樹)50 20 40 80 插入關(guān)鍵字 = 60, 60 80 90,60809090 50 806030, 40 20 30 50 808030 5022被刪結(jié)點不是最下層結(jié)點，借被刪關(guān)鍵字的右子樹中的最小關(guān)鍵字；被刪結(jié)點為最下層結(jié)點，（1）它的關(guān)

9、鍵字個數(shù)不少，刪除該關(guān)鍵字即可；（2）它的關(guān)鍵字個數(shù)不能減少：要從其左(或右)兄弟結(jié)點“借”關(guān)鍵字，無關(guān)鍵字可借時就進行結(jié)點“合并”：（2.1）“有的借”左（右）兄弟結(jié)點中最大（最小）的關(guān)鍵字上移至雙親，雙親結(jié)點中大于（小于）上移關(guān)鍵字的關(guān)鍵字下移至被刪結(jié)點；（2.2）“沒的借合并”把被刪結(jié)點與其左（右）兄弟結(jié)點以及雙親結(jié)點中分割二者的關(guān)鍵字合并在一起。4刪除保證關(guān)鍵字的個數(shù)不能小于m/2-123 在B-樹中進行查找時，其查找時間主要花費在搜索結(jié)點（訪問外存）上，即主要取決于B-樹的深度。5查找性能的分析問：含 N 個關(guān)鍵字的 m 階 B-樹可能達到的最大深度 H 為多少？24第 2 層 2

10、個先推導(dǎo)每一層所含最少結(jié)點數(shù)：第 1 層 1 個第 H+1 層 2(m/2) H-1 個第 4 層 2(m/2)2 個第 3 層 2m/2 個反過來問： 深度為H的B-樹中， 至少含有多少個結(jié)點？ 25 假設(shè) m 階 B-樹的深度為 H+1，由于第 H+1 層為葉子結(jié)點，而當(dāng)前樹中含有 N 個關(guān)鍵字，則葉子結(jié)點必為 N+1 個， N+12(m/2)H-1 H-1logm/2(N+1)/2) Hlogm/2(N+1)/2)+1由此可推得下列結(jié)果：26 在含 N 個關(guān)鍵字的 B-樹上進行一次查找，需訪問的結(jié)點個數(shù)不超過 logm/2(N+1)/2)+1結(jié)論：27是B-樹的一種變型四、B+樹281B+樹的結(jié)構(gòu)特點： 每個葉子結(jié)點中含有 n 個關(guān)鍵字和 n 個指向記錄的指針；并且，所有葉子結(jié)點彼此相鏈接構(gòu)成一個有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點；29 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot 每個非葉結(jié)點中的關(guān)鍵字 Ki 即為其相應(yīng)指針 Ai 所指子樹中關(guān)鍵字的最大值； 所有葉子結(jié)點都處在同一層次上，每個葉子結(jié)點中關(guān)鍵字的個數(shù)