數(shù)據(jù)結(jié)構(gòu)-查表找課件

1、第九章 查找表1何謂查找表 ？ 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。 由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。2對(duì)查找表經(jīng)常進(jìn)行的操作:查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一個(gè)數(shù)據(jù)元素；從查找表中刪去某個(gè)數(shù)據(jù)元素。3僅作 前兩種即查詢和檢索操作的查找表。即檢索的前后不會(huì)改變查找表的內(nèi)容。靜態(tài)查找表在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素,此類表為動(dòng)態(tài)查找表。即檢索過程中可能會(huì)改變數(shù)據(jù)元素的存儲(chǔ)位置。動(dòng)態(tài)查找表查找表可分為兩類:4 檢索是確定數(shù)

2、據(jù)元素集合中是否存在數(shù)據(jù)元素等于特定元素或是否存在元素滿足某種給定特征的過程。 要進(jìn)行檢索，必須知道待檢索對(duì)象的特征，也就是要知道待檢索數(shù)據(jù)元素的關(guān)鍵字。 我們將能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其它關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。5是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。關(guān)鍵字 若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字”。 若此關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)鍵字”。6 根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄） 查找 若查找表中存在這樣一個(gè)記錄，則稱“查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，

3、或指示該記錄在查找表中的位置； 否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”。79.1 靜 態(tài) 查 找 表10數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。 數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable /P21611 Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作 P：next ADT StaticSearchTable12按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()

4、失敗，則操作失敗。Traverse(ST, Visit();初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)；16typedef struct / 數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí) / 按實(shí)際長度分配，0號(hào)單元留空 int length; / 表的長度 SSTable;假設(shè)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)為ElemType *elem;17數(shù)據(jù)元素類型的定義為:typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemType ; , TElemType ;18一、順序查找表二、有序查找表三、索引順序表19i0 1 2 3 4 5 6 7 8 9

5、 10 11 5 13 19 21 37 56 64 75 80 88 92找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素： 1查找第n-1個(gè)元素：2.查找第1個(gè)元素： n查找第i個(gè)元素： n+1-i查找失?。?n+1查找過程：從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。例如：21ST.elemiST.elemi60ikey=64key=60i6422int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key =

6、 key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時(shí)，i為0 / Search_Seq23 定義： 查找算法的平均查找長度 (Average Search Length) 也就是為確定某一結(jié)點(diǎn)在數(shù)據(jù)集合中的位置，給定值與集合中的結(jié)點(diǎn)關(guān)鍵字所需進(jìn)行的比較次數(shù)。其中: n 為表長，Pi 為查找表中第i個(gè)記錄的概率， 且 Ci為找到該記錄時(shí)，曾和給定值 比較過的關(guān)鍵字的個(gè)數(shù)分析順序查找的時(shí)間性能。24在等概率查找的情況下， 順序表查找的平均查找長度為：對(duì)順序表而言，Ci = n-i+1ASL =

7、 nP1 +(n-1)P2 + +2Pn-1+Pn25 若查找概率無法事先測定，則查找過程采取的改進(jìn)辦法是，可以在記錄中附設(shè)一個(gè)訪問頻度域，使查找概率大的記錄在查找過程中不斷后移，以便在以后的查找過程中減少比較次數(shù)在不等概率查找的情況下，ASLss 在 PnPn-1P2P1時(shí)取極小值A(chǔ)SL = nP1 +(n-1)P2 + +2Pn-1+Pn26 上述順序查找表的查找算法簡單， 但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表 若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。271.設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給

8、定值。2.初始時(shí)，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k=rmid.key，查找成功若krmid.key，則low=mid+13.重復(fù)上述操作，直至lowhigh時(shí)，查找失敗。折半查找算法實(shí)現(xiàn)28ST.elemST.length例如: key=64 的查找過程如下lowhighmidlow mid high midlow 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。29int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.leng

9、th; / 置區(qū)間初值 while (low 50時(shí)，可得近似結(jié)果 一般情況下，表長為 n 的折半查找的判定樹的深度和含有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同。因此具有n個(gè)結(jié)點(diǎn)的判定樹的深度為 +1。為了方便起見，以滿二叉樹為例，樹中層次為1的結(jié)點(diǎn)有1個(gè)，層次為2的結(jié)點(diǎn)有2個(gè)，層次為h的結(jié)點(diǎn)有2h1個(gè).32在 n50 時(shí)，可得近似結(jié)果 可見，折半查找的效率比順序查找高。折半查找只能適用于有序表，并且以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。33順序表和有序表的比較34三、索引順序表以索引順序表表示靜態(tài)查找表，search操作可用分塊查找來實(shí)現(xiàn)。分塊查找又稱索引順序查找，這是順序查找的一種改進(jìn)方法。在此查找方法中，除表

10、本身以外，尚需建立一個(gè)“索引表”。35例如 表中含有18個(gè)元素，可分成三個(gè)子表。對(duì)每個(gè)子表（或稱塊）建立一個(gè)索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)（其值為該子表內(nèi)的最大關(guān)鍵字）和項(xiàng)指針（指示該子表的第一個(gè)元素在表中位置）。 索 引 表最大關(guān)鍵字起始地址36 索引表按關(guān)鍵字有序，故表或者有序，或者分塊有序。所謂“分塊有序” 是指一個(gè)子表中所有元素的關(guān)鍵字均大于前一個(gè)子表的最大關(guān)鍵字。 37索引順序表的查找過程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。注意：索引可以根據(jù)查找表的特點(diǎn)來構(gòu)造?？梢姡?索引順序查找的過程也是一個(gè)“縮小區(qū)間”的查找過程。381 2 3 4 5 6 7 8

11、 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例如39索引順序查找的平均查找長度 = 查找“索引”的平均查找長度 + 查找“順序表”的平均查找長度40分塊查找方法評(píng)價(jià)當(dāng) 時(shí)，ASL取最小值 +1 41查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或線性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或線性鏈表順序查找折半查找 分塊查找429.2 動(dòng) 態(tài) 查 找 表43動(dòng)態(tài)查找表的特點(diǎn):表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成。

12、若表中存在其關(guān)鍵字等于給定值key的記錄,表明查找成功；否則插入關(guān)鍵字等于key的記錄。44ADT DynamicSearchTable 抽象數(shù)據(jù)類型動(dòng)態(tài)查找表的定義如下：數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R： 數(shù)據(jù)元素同屬一個(gè)集合。D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字， 可唯一標(biāo)識(shí)數(shù)據(jù)元素。45InitDSTable(&DT)/構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。DestroyDSTable(&DT)/銷毀動(dòng)態(tài)查找表DT。SearchDSTable(DT, key);/查找 DT 中與關(guān)鍵字key等值的元素。InsertDSTable(&DT, e);/若 DT 中不存在其關(guān)鍵字等于

13、 e.key 的 數(shù)據(jù)元素，則插入 e 到 DT。DeleteDSTable(&T, key);/刪除DT中關(guān)鍵字等于key的數(shù)據(jù)元素。TraverseDSTable(DT, Visit();/按某種次序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit() 一次且至多一次?；静僮鳎簄extADT DynamicSearchTable46一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B - 樹四、B+樹47一、二叉排序樹（二叉查找樹）1定義2查找算法3插入算法4刪除算法5查找性能的分析48（1）若它的左子樹不空，則左子樹上 所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1定義： 二叉排序樹或者是一棵空樹；或者是具有如下特

14、性的二叉樹：（3）它的左、右子樹也都分別是二叉 排序樹。（2）若它的右子樹不空，則右子樹上 所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；49503080209010854035252388例如:是二叉排序樹66不50 通常，取二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;TElemType data;512二叉排序樹的查找算法：1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3）若給定值大于根

15、結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。否則若二叉排序樹為空，則查找不成功；5250308020908540358832例如:二叉排序樹查找關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 53從上述查找過程可見，在查找過程中，生成了一條查找路徑: 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。 查找成功 查找不成功54BiTree SearchBST( BiTree T, KeyType key) /在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字 /等于Key的數(shù)據(jù)元素，若查

16、找成功，則返回指向 /該數(shù)據(jù)元素的指針，否則返回空指針 if (!T)| EQ(key, T-data.key) return (T);/查找結(jié)束 else if LT(key, T-data.key) return(SearchBST(T-lchild, key) else return (SearchBST(T-rchild, key); /SearchBST55二叉排序樹是一種動(dòng)態(tài)樹表，其特點(diǎn)是，樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩

17、子結(jié)點(diǎn)。為此將二叉樹的查找算法改為如下算法56算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針 T 所指二叉排序樹中遞歸地查找其 / 關(guān)鍵字等于 key 的數(shù)據(jù)元素，若查找成功， / 則返回指針 p 指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回 / 函數(shù)值為 TRUE; / SearchBST 否則表明查找不成功，返回 / 指針 p 指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為FALSE, 指針 f 指向當(dāng)前訪問 / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULL5730201040352523fT設(shè) ke

18、y = 48fTfT22pfTfTTTTfffp58if (!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 ); / 在左子樹中繼續(xù)查找SearchBST (T-rchild, key, T, p ); / 在右子樹中繼續(xù)查找Status SearchBST (BiTree T, KeyType key, BiTree f, Bi

19、Tree &p ) / SearchBST59根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行;3二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過程得到。60對(duì)于輸入實(shí)例（30，20，40，10，25，45），創(chuàng)建二叉排序樹的過程如下：（a）空樹30（b）插入303020（c）插入20302040（d）插入4030204010（e）插入10 3020401025（f）插入25 302040102545（g）插入45 按照（30，20，10，25，40，45）或（30，40，45，20，10，25）的輸入次序同樣

20、可生成圖（g）所示的二叉排序樹。 但若按照（10，20，25，30，40，45）或（45，40，30，25，20，10）的次序輸入，將分別生成只具有單個(gè)右分支和單個(gè)左分支的兩棵二叉排序樹。 61結(jié)論：二叉排序樹的形態(tài)與數(shù)據(jù)的輸入次序相關(guān)；62Status Insert BST(BiTree &T, ElemType e ) if (!SearchBST ( T, e.key, NULL, p ) s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn) 分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p )

21、T = s; / 插入 s 為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子else p-rchild = s; / 插入 *s 為 *p 的右孩子return TRUE; / 插入成功 else return FALSE; / Insert BST63（1）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。4二叉排序樹的刪除算法可分三種情況討論： 和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特

22、性。6450308020908540358832（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)例如:被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”6550308020908540358832（2）被刪的結(jié)點(diǎn)只有左子樹或只有右子樹 其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為 “指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。被刪關(guān)鍵字 = 40806650308020908540358832（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹4040按中序遍歷寫出序列， 以被刪結(jié)點(diǎn)其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字 = 506768Status DeleteBST (BiTree &T, KeyType key

23、 ) / 若二叉排序樹 T 中存在其關(guān)鍵字等于 key 的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回 / 函數(shù)值 TRUE，否則返回函數(shù)值 FALSE if (!T) return FALSE; else / DeleteBST算法描述如下：(p230) 69if ( EQ (key, T-data.key) ) / 找到關(guān)鍵字等于key的數(shù)據(jù)元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 繼續(xù)在左子樹中進(jìn)行查找DeleteBST ( T-rchil

24、d, key ); / 繼續(xù)在右子樹中進(jìn)行查找70void Delete ( BiTree &p ) / 從二叉排序樹中刪除結(jié)點(diǎn) p， / 并重接它的左子樹或右子樹 if (!p-rchild) else if (!p-lchild) else / Delete其中刪除操作過程如下所描述： 71 / 右子樹為空樹則只需重接它的左子樹q = p; p = p-lchild; free(q); pq72/ 左子樹為空樹只需重接它的右子樹q = p; p = p-rchild; free(q);pq73q = p; s = p-lchild;while (s-rchild) q = s; s = s

25、-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)/ 左右子樹均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子樹free(s);745查找性能的分析 對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的 ASL 值，顯然，由值相同的 n 個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長 度的值不同，甚至可能差別很大。75由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹，例如：2134535412ASL

26、 =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 因此，在二叉排序樹上進(jìn)行檢索的效率與樹的形狀有密切的聯(lián)系。 76 在最壞的情況下，含有n個(gè)結(jié)點(diǎn)的二叉排序樹退化成一棵深度為n的單支樹（類似于單鏈表），它的平均查找長度與單鏈表上的順序檢索相同，即ASL=（n+1）/2。30404650556065707580（a） （b）圖中兩棵具有不同檢索效率的二叉排序樹 6040703050658046557577 例如，對(duì)于上圖中的兩棵二叉排序樹，其深度分別是4和10，在檢索失敗的情況下，在這兩棵樹上的最大比較次數(shù)分別是4和10；在檢索成功的情況下，若檢索每個(gè)結(jié)點(diǎn)

27、的概率相等，則對(duì)于圖（a）所示的二叉排序樹其平均查找長度為：ASLa= =對(duì)于圖（b）所示的二叉排序樹其平均查找長度為：ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.578二、二叉平衡樹何謂“二叉平衡樹”？如何構(gòu)造“二叉平衡樹”79是平衡二叉樹，不是完全二叉樹不是平衡二叉樹80 二叉平衡樹是二叉查找樹的另一種形式，其特點(diǎn)為：樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差（平衡因子BF）的絕對(duì)值不大于1 例如:548254821是平衡樹不是平衡樹平衡二叉樹BF值011001220失去平衡的最小子樹81 構(gòu)造二叉平衡（查找）樹的方法：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5

28、, 4, 3, 8, 19,1,2，25，2354543BF值10102（1）由于插入節(jié)點(diǎn)3使得樹不再平衡，而3是插入在失去平衡的最小子樹根節(jié)點(diǎn)5的左子樹根節(jié)點(diǎn)4的左子樹上。定義失去平衡的最小子樹根節(jié)點(diǎn)為a，則該類不平衡可歸納為，在a的左子樹根節(jié)點(diǎn)的左子樹上插入導(dǎo)致的不平衡可使用單向右旋平衡處理，可以記為左左-右。54300082435843584358190-10-100-1-2-24358190000-1（2）由于插入節(jié)點(diǎn)19使得樹不再平衡，而19是插入在失去平衡的最小子樹根節(jié)點(diǎn)5的右子樹根節(jié)點(diǎn)8的右子樹上。該類不平衡可歸納為，在a的右子樹根節(jié)點(diǎn)的右子樹上插入導(dǎo)致的不平衡可使用單向左旋平衡

29、處理，可以記為右右-左。83458190003211-120458190003212110458190003002010先向左旋再向右旋（3）在3的左子樹根節(jié)點(diǎn)1的右子樹上插入節(jié)點(diǎn)2導(dǎo)致不平衡，可使用雙向旋轉(zhuǎn)：先使其子樹左旋再整棵樹右旋，可記為左右-左右。8445819-2-2030-2201025231045819-2-2030-220102325-10先向右旋458230-1030-12010251900再向左旋（4）在19的右子樹根節(jié)點(diǎn)25的左子樹上插入節(jié)點(diǎn)23導(dǎo)致不平衡，可使用雙向旋轉(zhuǎn)：先使其子樹右旋再整棵樹左旋，可記為右左-右左。85 構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采

30、用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)86426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字 987單向右旋轉(zhuǎn)（1）LL型平衡旋轉(zhuǎn)：由于在A的左孩子的左子樹上插入新結(jié)點(diǎn)，使A的平衡度由1增至2，致使以A為根的子樹失去平衡，如圖(a)所示。此時(shí)應(yīng)進(jìn)行一次順時(shí)針旋轉(zhuǎn)，“提升”B（即A的左孩子）為新子樹的根結(jié)點(diǎn)，A下降為B的右孩子，同時(shí)將B原來的右子樹Br調(diào)整為A的左子樹。A2B1BLBrArhhhLL型A0B0BLBrArhhh圖 (a)旋轉(zhuǎn)后保證中序序列不變88（2）RR型平衡旋轉(zhuǎn)：由于在A的右孩子的右子

31、樹上插入新結(jié)點(diǎn)，使A的平衡度由-1變?yōu)?2，致使以A為根的子樹失去平衡，如圖（b）所示。此時(shí)應(yīng)進(jìn)行一次逆時(shí)針旋轉(zhuǎn)，“提升”B（即A的右孩子）為新子樹的根結(jié)點(diǎn)，A下降為B的左孩子，同時(shí)將B原來的左子樹BL調(diào)整為A的右子樹。圖 (b)A-2B-1BrBLALhhhRR型A0B0BrALBLhhh旋轉(zhuǎn)后保證中序序列不變單向左旋轉(zhuǎn)89雙向旋轉(zhuǎn)，先左后右（3）LR型平衡旋轉(zhuǎn)：由于在A的左孩子的右子樹上插入新結(jié)點(diǎn)，使A的平衡度由1變成2，致使以A為根的子樹失去平衡，如圖（c）所示。此時(shí)應(yīng)進(jìn)行兩次旋轉(zhuǎn)操作（先逆時(shí)針，后順時(shí)針），即“提升”C（即A的左孩子的右孩子）為新子樹的根結(jié)點(diǎn)；A下降為C的右孩子；B變?yōu)?/p>

32、C的左孩子；C原來的左子樹CL調(diào)整為B現(xiàn)在的右子樹；C原來的右子樹Cr調(diào)整為A現(xiàn)在的左子樹A2B-1ArhBLhLR型CCLh-1Crh-11A-1B0ArhBLhCLh-1Crh-1C0圖(c)90雙向旋轉(zhuǎn)，先右后左（4）RL型平衡旋轉(zhuǎn)：由于在A的右孩子的左子樹上插入新結(jié)點(diǎn)，使A的平衡度由-1變成-2，致使以A為根的子樹失去平衡，如圖（d）所示。此時(shí)應(yīng)進(jìn)行兩旋轉(zhuǎn)操作（先順時(shí)針，后逆時(shí)針），即“提升”C（即A的右孩子的左孩子）為新子樹的根結(jié)點(diǎn)；A下降C的左孩子；B變?yōu)镃的右孩子；C原來的左子樹CL調(diào)整為A現(xiàn)在的右子樹；C原來的右子樹Cr調(diào)整為B現(xiàn)在的左子樹。 B-1A0BrhALhCLh-1C

33、rh-1C0A-2B1BrhALhRL型CLh-1Crh-1C1圖(d)91結(jié)點(diǎn)序列（120，80，30，90，45，60）逐個(gè)插入一棵空的AVL樹的過程如下：1200120180012028013001200800300120180-1300900120180030-1900450120180030-290045-1600120180030090045060092三、 B - 樹1定義2查找過程3插入操作4刪除操作93B-樹：一種平衡的多路查找樹,一棵m階的B-樹或?yàn)榭諛洌驗(yàn)闈M足下列特性的m叉樹：樹中每個(gè)節(jié)點(diǎn)至多有m棵子樹若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至

34、少有m/2 棵子樹所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,Kn,An) 其中Ki(i=1,n)為關(guān)鍵字，且KiKi+1,(i=1,n-1); Aj（0jn）為指向子樹根結(jié)點(diǎn)的指針，且Aj（0jn） 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小kj+1; An所指子樹中 所有結(jié)點(diǎn)的關(guān)鍵字均大于kn; n（m/2-1nm-1）為關(guān)鍵字的個(gè)數(shù)；n+1為子樹個(gè)數(shù)。941351182437811112713934753641994階B-樹，每個(gè)節(jié)點(diǎn)最多4棵子樹，3個(gè)關(guān)鍵字。一棵m階B-樹每個(gè)節(jié)點(diǎn)最多有m棵子樹m-1個(gè)關(guān)鍵字,最少有m/2棵子樹m/2-1個(gè)關(guān)鍵字95非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均

35、自小至大有序排列，即：K1 K2 key1.keynum中查找 i ，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); / 查找不成功 Search (Btree P , KeyType K) for (int i=0; iPkeynum &P keyi+1=k; i+); return i;1033插入1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm， 不修改指針;

36、例如在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況：1042）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(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)。 例如105例如:下列為 3 階B-樹50 20 40 80 插入關(guān)鍵字 = 60, 60 80 90,60809090 50 806030, 40 20 30 50 808030 50106 和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在

37、結(jié)點(diǎn)，并且要求刪除之，若該結(jié)點(diǎn)為最下層的非終端結(jié)點(diǎn)，且其中的關(guān)鍵字?jǐn)?shù)目不小于m/2 ，則刪除完成，否則要進(jìn)行“合并”操作.4刪除10745abt24b53 90e3 12c37d50f61 70g100h下面我們只需討論刪除最小層非終端結(jié)點(diǎn)中的關(guān)鍵字情形，分3種情況討論：1081）被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于m/2，則只需要從該結(jié)點(diǎn)中刪去關(guān)鍵字ki和相應(yīng)的指針pi，樹的其它部分不變。 例：9084028150 20085 120508090 11584028150 20085 1205060 80刪除60與1151092）被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于m/2-1，而與該結(jié)點(diǎn)相鄰

38、的右兄弟結(jié)點(diǎn)（或左兄弟結(jié)點(diǎn)）中的關(guān)鍵字?jǐn)?shù)目大于m/2-1，則需要將其右兄弟的最小關(guān)鍵字（或其左兄弟的最大關(guān)鍵字）移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在的結(jié)點(diǎn)中。例如從圖中刪除關(guān)鍵字90，結(jié)果如圖所示。1208402820085 15050809084028150 20085 1205080刪除901103）被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于m/2-1，則第（2）種情況中采用的移動(dòng)方法將不奏效，此時(shí)須將被刪關(guān)鍵字所有結(jié)點(diǎn)與其左或右兄弟合并。不妨設(shè)該結(jié)點(diǎn)有右兄弟，但其右兄弟地址由雙親結(jié)點(diǎn)指針pi所指，則在刪除關(guān)鍵字之后

39、，它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針加上雙親結(jié)點(diǎn)中的關(guān)鍵字ki一起合并到pi所指兄弟結(jié)點(diǎn)中（若沒有右兄弟，則合并至左兄弟結(jié)點(diǎn)中）。 1208402820085 1505080刪除12084028150 200855080111如在3階B-樹中依次刪除關(guān)鍵字12,50，53，37，分為三種情況45abt24b53 90e3 12c37d50f61 70g100h3階B-樹11245abt24b53 90e3 c37d50f61 70g100h(1)被刪關(guān)鍵字(12)所在節(jié)點(diǎn)(c)中的關(guān)鍵字?jǐn)?shù)目不小于m/2則只須從該節(jié)點(diǎn)(c)中刪去該關(guān)鍵字(12)和相應(yīng)指針，樹的其他部分不變。刪除關(guān)鍵字1211345

40、abt24b53 90e3c37d50f61 70g100h（2）被刪關(guān)鍵字(50)所在節(jié)點(diǎn)(f)中的關(guān)鍵字?jǐn)?shù)目等于m/2-1,其相鄰的某個(gè)兄弟結(jié)點(diǎn)(g)（左兄弟或右兄弟）中的關(guān)鍵字?jǐn)?shù)目大于m/2-1，則將其兄弟結(jié)點(diǎn)(g)中的最?。ɑ蜃畲螅╆P(guān)鍵字(61)上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字(61)的關(guān)鍵字(53)下移至被刪關(guān)鍵字(50)所在節(jié)點(diǎn)(f)中。45abt24b61 90e3c37d53f70g100h刪除關(guān)鍵字50114（3）被刪關(guān)鍵字(53)所在節(jié)點(diǎn)(f)和其相鄰的兄弟結(jié)點(diǎn)(g)中的關(guān)鍵字?jǐn)?shù)目均等于m/2-1(1), 假設(shè)該節(jié)點(diǎn)有右兄弟(g),在刪去關(guān)鍵

41、字(53)后，他所在結(jié)點(diǎn)(f)中剩余的關(guān)鍵字和指針加上雙親結(jié)點(diǎn)(e)中的關(guān)鍵字(61)一起合并到右兄弟結(jié)點(diǎn)(g)中。45abt24b90e3c37d61 70g100h45abt24b61 90e3c37d53f70g100h刪除關(guān)鍵字53115刪除關(guān)鍵字37bt45 90e3 24c61 70g100h45abt24b90e3c37d61 70g100h45abtb90e3 24c61 70g100h如果刪除后使雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目小于m/2-1，則依此類推層層向上合并。116用依次輸入的關(guān)鍵字23、30、51、29、2 7、15、11、17和16建一棵3階B-樹，畫出建該樹的變化過程示意

42、圖（每插入一個(gè)結(jié)點(diǎn)至少有一張圖）。117是B-樹的一種變型四、B+樹118B+樹B+樹是B-樹的變型，m階的B+樹和m階的B-樹的區(qū)別是：關(guān)鍵字個(gè)數(shù)和子樹個(gè)數(shù)一樣多所有葉子結(jié)點(diǎn)中包含全部關(guān)鍵字信息及指向含這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。所有非終端結(jié)點(diǎn)可看成索引，節(jié)點(diǎn)中僅含有其子樹中的最大（或最?。╆P(guān)鍵字。11959 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt3階B+樹1201B+樹的結(jié)構(gòu)特點(diǎn)： 每個(gè)葉子結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字和 n 個(gè)指向記錄的指針；并且，所有葉子結(jié)點(diǎn)彼此相鏈接

43、構(gòu)成一個(gè)有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)；121 每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字 Ki 即為其相應(yīng)指針 Ai 所指子樹中關(guān)鍵字的最大值（或最小值）； 所有葉子結(jié)點(diǎn)都處在同一層次上，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于 m/2和 m 之間。12259 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt3階B+樹1232查找過程 在 B+ 樹上，既可以進(jìn)行縮小范圍的查 找，也可以進(jìn)行順序查找； 在進(jìn)行縮小范圍的查找時(shí)，不管成功 與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束； 若在結(jié)點(diǎn)內(nèi)查找時(shí)，給定值Ki， 則 應(yīng)繼續(xù)在 Ai 所指子樹中進(jìn)行查

44、找；1243插入和刪除的操作類似于B-樹進(jìn)行，即必要時(shí)，也需要進(jìn)行結(jié)點(diǎn)的“分裂”或“歸并”。1259.3 哈 希 表哈希表的相關(guān)定義哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找哈希表的插入哈希查找分析126 散列存儲(chǔ)的基本思想是以關(guān)鍵碼的值為自變量，通過一定的函數(shù)關(guān)系（稱為散列函數(shù)，或稱Hash函數(shù)），計(jì)算出對(duì)應(yīng)的函數(shù)值來，以這個(gè)值作為結(jié)點(diǎn)的存儲(chǔ)地址，將結(jié)點(diǎn)存入計(jì)算得到的存儲(chǔ)單元里去。 散列存儲(chǔ) 127USk1k2k3k5k40H(k1)H(k5)H(k2)=H(k4)H(k3)H(km-1)圖9.22 散列過程示例 128哈希查找基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)

45、系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象。哈希表的相關(guān)定義關(guān)鍵字集合存儲(chǔ)地址集合hash129散列存儲(chǔ)中經(jīng)常會(huì)出現(xiàn)對(duì)于兩個(gè)不同關(guān)鍵字xi，xj，卻有H（xi）=H（xj），即對(duì)于不同的關(guān)鍵字具有相同的存放地址，這種現(xiàn)象稱為沖突或碰撞。綜上所述，對(duì)于Hash方法，需要研究下面兩個(gè)主要問題：（1）選擇一個(gè)計(jì)算簡單，并且產(chǎn)生沖突的機(jī)會(huì)盡可能少的Hash函數(shù)；（2）確定解決沖突的方法。130Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye

46、, Dei 例如：對(duì)于如下 9 個(gè)關(guān)鍵字設(shè) 哈希函數(shù) H(key) = (Ord(第一個(gè)字母) -Ord(A)+1)/2ChenZhaoQianSunLiWuHanYeDei問題: 若添加關(guān)鍵字 Zhou , 怎么辦？能否找到另一個(gè)哈希函數(shù)？1311) 哈希函數(shù)是一個(gè)映象，即： 將關(guān)鍵字的集合映射到某個(gè)地址集合上， 它的設(shè)置很靈活，只要這個(gè)地址集合的 大小不超出允許范圍即可;從這個(gè)例子可見，2) 由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即： key1 key2，而 f(key1) = f(key2)。1323) 很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能

47、選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的“查找表” 時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外;還需要找到一種“處理沖突” 的方法。133哈希表的定義: 根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之為“哈希表”。134二、構(gòu)造哈希函數(shù)的方法 對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法: 若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。1. 直接定址法3. 平方取中法5. 除留余數(shù)法4. 折疊法6. 隨機(jī)數(shù)法2

48、. 數(shù)字分析法135哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b1. 直接定址法此法僅適合于：地址集合的大小 = = 關(guān)鍵字集合的大小1362. 數(shù)字分析法構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址;例 有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1

49、只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位 與另兩位的疊加作哈希地址1373.平方取中法構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址4. 折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址種類移位疊加：將分割后的幾部分低位對(duì)齊相加間界疊加：從一端沿分割界來回折送，然后對(duì)齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例 關(guān)鍵字為 ：0442205864，哈希地址位數(shù)為45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加1

50、385. 除留余數(shù)法 設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中， pm (表長) 并且 p 應(yīng)為不大于 m 的素?cái)?shù) 139 給定一組關(guān)鍵字為: 12, 39, 18, 24, 33, 21，若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3例如：為什么要對(duì) p 加限制？ 可見，若 p 中含質(zhì)因子 3, 則所有含質(zhì)因子 3 的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，從而增加了“沖突”的可能。1406.隨機(jī)數(shù)法設(shè)定哈希函數(shù)為: H(key) = Random(key)其中，Random 為偽隨機(jī)函數(shù) 通常，此方法用于對(duì)長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。141 實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地