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

1、第九章第九章查查 找找何謂查找表何謂查找表 ？ 查找表是由同一類型同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合集合。 由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應用靈便的結(jié)構(gòu)。對查找表經(jīng)常進行的對查找表經(jīng)常進行的操作操作: 1）查詢查詢某個“特定的”數(shù)據(jù)元素是否在查找表中； 2）檢索檢索某個“特定的”數(shù)據(jù)元素的各種屬性； 3）在查找表中插入插入一個數(shù)據(jù)元素； 4）從查找表中刪去刪去某個數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表靜態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素

2、。動態(tài)查找表動態(tài)查找表查找表可分為兩類查找表可分為兩類:是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項數(shù)據(jù)項的值，用以標識標識（識別）一個數(shù)據(jù)元素（或記錄）。關(guān)鍵字關(guān)鍵字 若此關(guān)鍵字可以識別唯一的唯一的一個記錄，則稱之謂“主關(guān)鍵字主關(guān)鍵字”。 若此關(guān)鍵字能識別若干若干記錄，則稱之謂“次關(guān)鍵字次關(guān)鍵字”。 根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。 查找查找 若查找表中存在這樣一個記錄，則稱“查找成功查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置； 否則稱“查找不成功查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。 由于查找表中的數(shù)據(jù)元素之間不存在明顯

3、的組織規(guī)律，因此不便于查找。 為了提高查找的效率， 需要在查找表中的元素之間人為地 附加某種確定的關(guān)系，換句話說， 用另外一種結(jié)構(gòu)來表示查找表用另外一種結(jié)構(gòu)來表示查找表。如何進行查找？如何進行查找？查找的方法取決于查找表的結(jié)構(gòu)。查找的方法取決于查找表的結(jié)構(gòu)。9.1 靜態(tài)查找表靜態(tài)查找表9.2 動態(tài)查找樹表動態(tài)查找樹表(二叉排序樹二叉排序樹)9.3 哈希表哈希表9.1 靜靜 態(tài)態(tài) 查查 找找 表表數(shù)據(jù)對象數(shù)據(jù)對象D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)每個數(shù)據(jù)元素含有類型相同的據(jù)元素含有類型相同的關(guān)鍵字關(guān)鍵字，可唯一標識數(shù)據(jù)元素。 數(shù)據(jù)元素同屬一個集合。ADT Stati

4、cSearchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P： ADT StaticSearchTable構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。 Create(&ST, n);操作結(jié)果：銷毀表ST。Destroy(&ST);初始條件：操作結(jié)果：靜態(tài)查找表ST存在；若 ST 中存在其關(guān)鍵字等于 key 的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。 Search(ST, key);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，key 為和

5、查找表中元素的關(guān)鍵字類型相同的給定值；按某種次序?qū)T的每個元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。Traverse(ST, Visit();初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對元素操作的應用函數(shù)；typedef struct / 數(shù)據(jù)元素存儲空間基址，建表時 / 按實際長度分配，0號單元留空 int length; / 表的長度 SSTable;假設靜態(tài)查找表靜態(tài)查找表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)為ElemType *elem;數(shù)據(jù)元素類型的定義為數(shù)據(jù)元素類型的定義為:typedef struct keyType key; / 關(guān)鍵字域 /

6、 其它屬性域 ElemType ; , TElemType ;一、順序查找表一、順序查找表二、有序查找表二、有序查找表三、靜態(tài)查找樹表（不講）三、靜態(tài)查找樹表（不講）四、索引順序表四、索引順序表 以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表順序查找表21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem回顧順序表的查找過程：回顧順序表的查找過程：假設給定值 e=64,要求 ST.elemk = e, 問: k = ?kkint location( SqList L, ElemType& e

7、, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & !(*compare)(*p+,e) k+; if ( k= L.length) return k; else return 0; /location21 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.Len

8、gthST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時，i為0 / Search_Seq 定義：定義： 查找算法的平均查找長度平均查找長度 (Average Search Length) 為確定記錄在查找表中的位

9、置，需和給定值 進行比較的關(guān)鍵字個數(shù)的期望值 其中: n 為表長，Pi 為查找表中第i個記錄的概率， 且 ， Ci為找到該記錄時，曾和給定值比較過的關(guān)鍵字的個數(shù)。分析順序查找的時間性能niiiCPASL111niiP在等概率查找的情況下， 順序表查找的平均查找長度為：對順序表順序表而言，Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+Pn 若查找概率無法事先測定，則查找過程采取的改進辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss 在 PnPn-1P2P1時取極小值 上述順

10、序查找表的查找算法簡單， 但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示靜態(tài)查找表，則查找過程可以基于“折半折半”進行。05 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 指示查找區(qū)間的下界high 指示查找區(qū)間的上界mid = (low+high)/2int Search_Bin ( SSTable ST, KeyType key ) low

11、 = 1; high = ST.length; / 置區(qū)間初值 while (low 50時，可得近似結(jié)果 一般情況下，表長為 n 的折半查找的判定樹的深度和含有 n 個結(jié)點的完全二叉樹的深度相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs關(guān)鍵字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3三、靜態(tài)查找樹表三、靜態(tài)查找樹表 在不等概率查找不等概率查找的情況下，折半查找折半查找不是不是有序表最好的查找方法。ASL:平均查找長度例如例如:此時 ASL=20.2+30.3+10.05+20

12、.3+30.15=2.4若改變Ci的值 2 1 3 2 3則 ASL=20.2+10.3+30.05+20.3+30.15=1.9 使 達最小的判定樹稱為最優(yōu)二叉樹，其中: 111niiCiqniiCipASL1111niiniiqp定義定義:為計算方便，令 wi = pi選擇二叉樹的根結(jié)點，使 達最小 111ijjhijjiwwP11)(iilhiswswswswP介紹一種次優(yōu)二叉樹的構(gòu)造方法：為便于計算，引入累計權(quán)值和 并設 wl-1 = 0 和 swl-1 = 0，則推導可得ijjiwsw1j01234567wj02153435swjpjkeyA B C D E F G023811 15

13、 18 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG3013ECGABDF所得次優(yōu)二叉樹如下所示所得次優(yōu)二叉樹如下所示: 查找比較查找比較“總次數(shù)總次數(shù)” = 3 2+4 1+2 5+3 3 +1 4+3 3+2 5 = 52 查找比較查找比較“總次數(shù)總次數(shù)” = 3 2+2 1+3 5+1 3 +3 4+2 3+3 5 = 59和折半查找相比較和折半查找相比較DBACFEGStatus SecondOptimal(BiTree &T, ElemType R, float sw, int low, int high) / 由有序表Rlow.high及

14、其累計權(quán)值表sw / 遞歸構(gòu)造次優(yōu)查找樹T。 選擇最小的選擇最小的Pi值值 if (!(T = (BiTree)malloc(sizeof(BiTNode) return ERROR; T-data = Ri; / 生成結(jié)點構(gòu)造次優(yōu)二叉樹的算法if (i=low) T-lchild = NULL; / 左子樹空else SecondOptimal(T-lchild, R, sw, low, i-1); / 構(gòu)造左子樹 if (i=high) T-rchild = NULL; / 右子樹空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 構(gòu)造右

15、子樹 return OK; / SecondOptimal次優(yōu)查找樹采用二叉鏈表的存儲結(jié)構(gòu)Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序表 ST 構(gòu)造一棵次優(yōu)查找樹 T / ST 的數(shù)據(jù)元素含有權(quán)域 weight if (ST.length = 0) T = NULL; else FindSW(sw, ST); / 按照有序表 ST 中各數(shù)據(jù)元素 / 的 weight 值求累計權(quán)值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree索引順序表的

16、查找過程：索引順序表的查找過程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個區(qū)間內(nèi)進行查找。注意：索引可以根據(jù)查找表的特點來構(gòu)造?？梢姡?索引順序查找索引順序查找的過程也是一個“縮小區(qū)間縮小區(qū)間”的查找過程。索引順序查找的平均查找長度索引順序查找的平均查找長度 = 查找查找“索引索引”的平均查找長度的平均查找長度 + 查找查找“順序表順序表”的平均查找長度的平均查找長度ADT DynamicSearchTable 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型動態(tài)查找表動態(tài)查找表的定義如下：的定義如下：數(shù)據(jù)對象數(shù)據(jù)對象D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 數(shù)據(jù)元素同屬一個集合。D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含

17、有類型相同的關(guān)鍵字， 可唯一標識數(shù)據(jù)元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();ADT DynamicSearchTable操作結(jié)果：操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。InitDSTable(&DT);銷毀動態(tài)查找表DT。DestroyDSTable(&DT);初始條件： 操作結(jié)果：動態(tài)查找表DT存在；

18、若DT中存在其關(guān)鍵字等于 key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。SearchDSTable(DT, key);初始條件：操作結(jié)果：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；動態(tài)查找表DT存在， e 為待插入的數(shù)據(jù)元素；InsertDSTable(&DT, e);初始條件：操作結(jié)果：若DT中不存在其關(guān)鍵字等于 e.key 的 數(shù)據(jù)元素，則插入 e 到DT。動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；DeleteDSTable(&T, key);初始條件：操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。動態(tài)查找表DT

19、存在，Visit是對結(jié)點操作的應用函數(shù)；TraverseDSTable(DT, Visit();初始條件：操作結(jié)果：按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù) Visit() 一次且至多一次。一旦 Visit() 失敗，則操作失敗。9.2 動動 態(tài)態(tài) 查查 找找 樹樹 表表(n) (1)(n) (1)(nlogn)綜合上一節(jié)討論的幾種查找表的特性：綜合上一節(jié)討論的幾種查找表的特性：查找 插入 刪除無序順序表 無序線性鏈表有序順序表 有序線性鏈表 靜態(tài)查找樹表(n)(n) (logn)(n) (logn)(1) (1)(n) (1)(nlogn)1）從查找性能看，最好情況能達 (logn)，此時要求表有

20、序；2）從插入和刪除的性能看，最好 情況能達 (1)，此時要求存儲 結(jié)構(gòu)是鏈表?？傻萌缦陆Y(jié)論：可得如下結(jié)論：一、二叉排序樹（二叉查找樹）一、二叉排序樹（二叉查找樹）二、二叉平衡樹二、二叉平衡樹三、三、B - 樹樹四、四、B+樹樹五、鍵五、鍵 樹樹一、二叉排序樹一、二叉排序樹（二叉查找樹）（二叉查找樹）1定義定義2查找算法查找算法3插入算法插入算法4刪除算法刪除算法5查找性能的分析查找性能的分析（1）若它的左子樹不空，則左子樹上 所有結(jié)點的值均小于根結(jié)點的值；1定義：定義： 二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉 排序樹。（2）若它的右子樹不空，

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

22、于大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找繼續(xù)在右子樹上進行查找。否則，若二叉排序樹為空為空，則查找不成功查找不成功；50308020908540358832例如例如:二叉排序樹二叉排序樹查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 ,從上述查找過程可見，從上述查找過程可見，在查找過程中，生成了一條查找路徑查找路徑： 從根結(jié)點出發(fā)，沿著左分支或右分支從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者 從根結(jié)點出發(fā)，沿著左分支或右分支從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹

23、為止。逐層向下直至指針指向空樹為止。 查找成功查找成功 查找不成功查找不成功算法描述如下：算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹中遞歸地查找其所指二叉排序樹中遞歸地查找其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若的數(shù)據(jù)元素，若查找成功查找成功， / 則返回指針則返回指針 p 指向該數(shù)據(jù)元素的結(jié)點，并返回指向該數(shù)據(jù)元素的結(jié)點，并返回 / 函數(shù)值為函數(shù)值為 TRUE; / SearchBST 否則表明否則表明查找不成功查找不成功，返回，返回

24、/ 指針指針 p 指向查找路徑上訪問的最后一個結(jié)點，指向查找路徑上訪問的最后一個結(jié)點， / 并返回函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當前訪問指向當前訪問 / 的結(jié)點的雙親，其初始調(diào)用值為的結(jié)點的雙親，其初始調(diào)用值為NULLif (!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ù)查找Sea

25、rchBST (T-rchild, key, T, p ); / 在右子樹中繼續(xù)查找30201040352523fT設 key = 48fTfT22pfTfTTTTfffp 根據(jù)動態(tài)查找表的定義，“插入插入”操作在操作在查找不成功查找不成功時才進行時才進行；3二叉排序樹的插入算法二叉排序樹的插入算法 若二叉排序樹為空樹空樹，則新插入的結(jié)點為新的根結(jié)點新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點新的葉子結(jié)點，其插入位置插入位置由查找過程得到。Status Insert BST(BiTree &T, ElemType e ) / 當二叉排序樹中不存在關(guān)鍵字等于當二叉排序樹中不存在關(guān)鍵

26、字等于 e.key 的的 / 數(shù)據(jù)元素時，插入元素值為數(shù)據(jù)元素時，插入元素值為 e 的結(jié)點，并返的結(jié)點，并返 / 回回 TRUE; 否則，不進行插入并返回否則，不進行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新的根結(jié)點else if ( LT(e.key

27、, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子else p-rchild = s; / 插入 *s 為 *p 的右孩子return TRUE; / 插入成功 （1）被刪除的結(jié)點是葉子； （2）被刪除的結(jié)點只有左子樹或者只有右子樹； （3）被刪除的結(jié)點既有左子樹，也有右子樹。4二叉排序樹的刪除算法二叉排序樹的刪除算法可分三種情況討論： 和插入相反，刪除在查找成功查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍仍然保持二叉排序樹的特性然保持二叉排序樹的特性。 上述算法描述太復雜 給出我的算法描述 算法描述： 1. 如果被刪除的是葉子節(jié)點，

28、直接刪除； 2. 如果不是葉子節(jié)點，則刪除該節(jié)點后，以該節(jié)點的左子樹的根節(jié)點替換該節(jié)點的位置；根據(jù)左子樹情況，處理右子樹： A. 若左子樹為空，則以右子樹的根節(jié)點替換被刪除節(jié)點； B. 若左子樹不為空，則右子樹的根節(jié)點成為該左子樹最右端的節(jié)點（可能為葉子或非葉子節(jié)點）的右孩子。50308020908540358832（1）被刪除的結(jié)點是葉子結(jié)點葉子結(jié)點例如例如:被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點中相應指針域的值改為其雙親結(jié)點中相應指針域的值改為“空空”50308020908540358832（2）被刪除的結(jié)點只有左子樹只有左子樹或者只有右子樹只有右子樹 其雙親結(jié)點的相應指針域的值改為

29、其雙親結(jié)點的相應指針域的值改為 “指向被刪除結(jié)點的左子樹或右子樹指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字被刪關(guān)鍵字 = 408050308020908540358832（3）被刪除的結(jié)點既有左子樹，也有右子樹既有左子樹，也有右子樹4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點被刪關(guān)鍵字被刪關(guān)鍵字 = 50Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹若二叉排序樹 T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點，并返回數(shù)據(jù)元素，則刪除該

30、數(shù)據(jù)元素結(jié)點，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返回函數(shù)值，否則返回函數(shù)值 FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于key的數(shù)據(jù)元素 else / DeleteBST算法描述如下：算法描述如下： if ( 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ù)在左子樹中進行查找DeleteBST ( T-rchild, key ); /

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

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

33、1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 下面討論平均情況下面討論平均情況: 不失一般性，假設長度為 n 的序列中有 k 個關(guān)鍵字小于小于第一個關(guān)鍵字，則必有 n-k-1 個關(guān)鍵字大于大于第一個關(guān)鍵字,由它構(gòu)造的二叉排序樹：n-k-1k的平均查找長度是 n 和 k 的函數(shù)P(n, k) ( 0 k n-1 )。 假設 n 個關(guān)鍵字可能出現(xiàn)的 n! 種排列的可能性相同，則含 n 個關(guān)鍵字的二叉排序樹的平均查找長度：10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在等概率查找等概率查找的情況下，RiLirootniiCCCn

34、CnknP11),(1)1)1()(1()1)(11knPknkPkn)1()1()(11knPknkPkn由此可類似于解差分方程，此遞歸方程有解：CnnnnPlog12)(10) 1() 1()(111)(nkknPknkPknnnP112)(21nkkPkn二、二叉平衡樹二、二叉平衡樹 何謂何謂“二叉平衡樹二叉平衡樹”？ 二叉平衡樹的查找性能分析二叉平衡樹的查找性能分析 如何構(gòu)造如何構(gòu)造“二叉平衡樹二叉平衡樹” 二叉平衡樹二叉平衡樹是二叉查找樹的另一種形式，其特點為： 樹中每個結(jié)點的樹中每個結(jié)點的左、右子樹深度左、右子樹深度之差的絕對值不大于之差的絕對值不大于1 。例如例如:1RLhh54

35、8254821是平衡樹是平衡樹不是平衡樹不是平衡樹 構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字 9 在平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關(guān)鍵字的個數(shù)進行比較的關(guān)鍵字的個數(shù)不超過平衡 樹的深度。平衡樹的查找性能分析：平衡樹的查找性能分析： 問：含 n 個關(guān)鍵字的二叉平衡樹可能達到的最大深度最大深度是多少？n = 0空樹空樹最大深度為最大深度為

36、 0n = 1最大深度為最大深度為 1n = 2最大深度為最大深度為 2n = 4最大深度為最大深度為 3n = 7最大深度為最大深度為 4先看幾個具體情況:反過來問，深度為深度為 h 的二叉平衡樹平衡樹中所含結(jié)點的最小值含結(jié)點的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情況下一般情況下N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用歸納法可證得利用歸納法可證得Nh = Fh+2 - 1 因此，在二叉平衡樹二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關(guān)鍵字進行比較的關(guān)鍵字的個數(shù)和的個數(shù)和 log(n) 相當。 由此推得

37、，深度為深度為 h 的二叉平衡樹二叉平衡樹中所含結(jié)點的最小值含結(jié)點的最小值 Nh = h+2/5 - 1。 反之，含有含有 n 個結(jié)點的二叉平衡樹能個結(jié)點的二叉平衡樹能達到的最大深度達到的最大深度 hn = log ( 5 (n+1) - 2。 三、三、 B - 樹樹1定義定義2查找過程查找過程3插入操作插入操作4刪除操作刪除操作5查找性能的分析查找性能的分析1B-樹的定義樹的定義B-樹是一種 平衡平衡 的 多路多路 查找查找 樹： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 在 m 階的B-樹上，每個非終端結(jié)點可能含有： n 個關(guān)鍵字關(guān)鍵字 Ki

38、（1 in） nm n 個指向記錄的指針指向記錄的指針 Di（1in） n+1 個指向子樹的指針指向子樹的指針 Ai（0in）多叉樹的特性typedef struct BTNode int keynum; / 結(jié)點中關(guān)鍵字個數(shù)，結(jié)點大小 struct BTNode *parent; / 指向雙親結(jié)點的指針 KeyType keym+1; / 關(guān)鍵字（0號單元不用） struct BTNode *ptrm+1; / 子樹指針向量 Record *recptrm+1; / 記錄指針向量 BTNode, *BTree; / B樹結(jié)點和B樹的類型B-樹結(jié)構(gòu)的樹結(jié)構(gòu)的C語言描述如下語言描述如下: : 非

39、葉結(jié)點中的多個關(guān)鍵字多個關(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); / 查找不成功在查找不成功之后，需進行插入。顯然，關(guān)鍵字插入插入的位置位置必定在最下最下層的非葉結(jié)點層的非葉結(jié)點，有下列幾種情況：3插入插入1）插入后，該

40、結(jié)點的關(guān)鍵字個數(shù)nsymbol 其中: p 指向雙鏈樹中某個結(jié)點， 0 i K.num-1初始狀態(tài): p=T-first; i = 0;若 ( p & p-symbol = K.chi & ifirst; i+;若 ( p & p-symbol != K.chi )則繼續(xù)在鍵樹的同一層上進行查找 p=p-next;若 ( p & p-symbol=K.chi & i=K.num-1)則 查找成功，返回指向相應記錄的指針 p-infoptr 若 ( p = NULL)則表明查找不成功，返回“空指針”;3. Trie樹樹 以多重鏈表作存儲結(jié)構(gòu)實現(xiàn)的鍵樹結(jié)點結(jié)

41、構(gòu)結(jié)點結(jié)構(gòu):分支結(jié)點分支結(jié)點葉子結(jié)點葉子結(jié)點指向記錄的指針0 1 2 3 4 5 24 25 26關(guān)鍵字關(guān)鍵字指向下層結(jié)點的指針每個域?qū)粋€“字母”0 1(A) 3 4 5(E) 9(I) 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHAS HAVE HEHERHEREHIGHHIS葉子結(jié)點葉子結(jié)點分支結(jié)點分支結(jié)點指向記錄指向記錄的指針的指針typedef struct TrieNode NodeKind kind; / 結(jié)點類型 union struct KeyType K; Record *infoptr lf; / 葉子結(jié)點(關(guān)鍵字和

42、指向記錄的指針) struct TrieNode *ptr27; int num bh; / 分支結(jié)點(27個指向下一層結(jié)點的指針) TrieNode, *TrieTree; / 鍵樹類型結(jié)點結(jié)構(gòu)的結(jié)點結(jié)構(gòu)的 C 語言描述語言描述:在在 Trie 樹中查找記錄的過程樹中查找記錄的過程:假設假設: T 為指向 Trie 樹根結(jié)點的指針， K.ch0.K.num-1 為待查關(guān)鍵字(給定值)。則則查找過程中的基本操作為： 搜索和對應字母相應的指針搜索和對應字母相應的指針:若若 p 不空，且 p 所指為分支結(jié)點，則則 p = p-bh.Ptrord(K.Chi) ; ( 其中: 0 i K.num-1

43、 )初始狀態(tài)初始狀態(tài): p=T; i = 0;若若 ( p & p-kind = BRANCH & ibh.ptrord(K.chi); i+;其中，ord 為求字符在字母表中序號的函數(shù)若若 ( p & p-kind=LEAF & p-lf.K=K)則則 查找成功查找成功，返回返回指向相應記錄的指針 ptr 反之，反之，即 ( !p | p-kind=LEAF & p-lf.K!=K )則則表明查找不成功查找不成功，返回返回“空指針”; 一、一、哈希表是什么？哈希表是什么？二、哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法處理

44、沖突的方法 四、哈希表的查找哈希表的查找 五、哈希表的刪除操作哈希表的刪除操作 六、對靜態(tài)查找表，對靜態(tài)查找表，9.3 哈哈 希希 表表 以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)結(jié)構(gòu)的共同特點特點：記錄在表中的位置位置和它的關(guān)關(guān)鍵字鍵字之間不存在不存在一個確定的關(guān)系，一、哈希表是什么？哈希表是什么？ 查找的過程查找的過程為給定值給定值依次和關(guān)鍵字集合中各個關(guān)鍵字關(guān)鍵字進行比較比較， 查找的效率查找的效率取決于和給定值進行比較進行比較的關(guān)鍵字個數(shù)個數(shù)。 用這類方法表示的查找表，其平均查找長度都不為零。 不同的表示方法，其差別僅在于：差別僅在于：關(guān)鍵字和給定值進行比較的順序不同。 只有一個辦法：預先知道

45、所查關(guān)鍵字在表中的位置， 對于頻繁使用的查找表，希望 ASL = 0。 即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。若以下標為以下標為000 999 的順序表的順序表表示之。例如：為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵字為學號，其值的范圍為 xx000 xx999 (前兩位為年份)。則查找過程可以簡單進行：取給定值（學號）的后三位，不需要經(jīng)過比較不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。但是，對于動態(tài)查找表動態(tài)查找表而言，因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關(guān)系，以 f(key) 作為關(guān)鍵字為 key 的記錄在表中的位置，通常稱這

46、個函數(shù) f(key) 為哈希函數(shù)。1) 表長不確定；2) 在設計查找表時，只知道關(guān)鍵字所 屬范圍，而不知道確切的關(guān)鍵字。Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：對于如下 9 個關(guān)鍵字設設 哈希函數(shù)哈希函數(shù) f(key) = (Ord(第一個字母第一個字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3ChenZhaoQianSunLiWuHanYeDei問題問題: 若添加關(guān)鍵字 Zhou , 怎么辦？怎么辦？能否找到能否找到另一個哈希函數(shù)？1) 哈希函數(shù)是一個映象映象，即： 將關(guān)鍵字的集合

47、映射到某個地址集合上，將關(guān)鍵字的集合映射到某個地址集合上， 它的設置很靈活靈活，只要這個地址集地址集合的 大小不超出允許范圍不超出允許范圍即可；從這個例子可見：從這個例子可見：2) 由于哈希函數(shù)是一個壓縮映象壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突沖突”現(xiàn)象，即： key1 key2，而 f(key1) = f(key2)。3) 很難很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的“查找表” 時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突” 的方法。哈希表的定義： 根據(jù)設定的哈希函

48、數(shù)哈希函數(shù) H(key) 和所選中的處理沖突的方法處理沖突的方法，將一組關(guān)鍵字映象映象到到一個有限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關(guān)鍵字在地址集中的“象”作為相應記錄在表中的存儲位置存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表哈希表”。二、構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法 對數(shù)字數(shù)字的關(guān)鍵字可有下列構(gòu)造方法： 若是非數(shù)字關(guān)鍵字非數(shù)字關(guān)鍵字，則需先需先對其進行進行數(shù)字化處理數(shù)字化處理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余數(shù)法除留余數(shù)法4. 折疊法折疊法6. 隨機數(shù)法隨機數(shù)法2. 數(shù)字分析法數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者

49、 H(key) = a key + b1. 直接定址法直接定址法此法僅適合于：此法僅適合于：地址集合的大小地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小此方法僅適合于：此方法僅適合于： 能預先估計出預先估計出全體關(guān)鍵字的每一位上每一位上各種數(shù)字出現(xiàn)的頻度數(shù)字出現(xiàn)的頻度。2. 數(shù)字分析法數(shù)字分析法 假設關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。 以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值” 的目的是“擴大差別” ，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響

50、。3. 平方取中法平方取中法 此方法適合于此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復出現(xiàn)頻度很高的現(xiàn)象。 將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加移位疊加和間界疊加間界疊加。4. 折疊法折疊法 此方法適合于此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。5. 除留余數(shù)法除留余數(shù)法 設定哈希函數(shù)為設定哈希函數(shù)為: H(key) = key MOD p 其中其中， pm ( (表長表長) ) 并且并且 p 應為不大于應為不大于 m 的素數(shù)的素數(shù) 或是或是 不含不含 20 以下的質(zhì)因子以下的質(zhì)因子給定一組關(guān)鍵字為：12, 39, 18, 24, 33, 21

51、，若取 p=9, 則他們對應的哈希函數(shù)值將為： 3, 3, 0, 6, 6, 3例如：例如：為什么要對 p 加限制？ 可見，若 p 中含質(zhì)因子 3， 則所有含質(zhì)則所有含質(zhì)因子因子 3 的關(guān)鍵字均映射到的關(guān)鍵字均映射到“3 的倍數(shù)的倍數(shù)”的的地址上地址上，從而增加了“沖突”的可能。6.隨機數(shù)法隨機數(shù)法設定哈希函數(shù)為設定哈希函數(shù)為: H(key) = Random(key)其中，其中，Random 為偽隨機函數(shù)為偽隨機函數(shù) 通常，此方法用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。 實際造表時，采用何種采用何種構(gòu)造哈希函數(shù)的方法方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突

52、的可能性降到的原則是使產(chǎn)生沖突的可能性降到盡可能地小盡可能地小。三、處理沖突的方法處理沖突的方法 “處理沖突處理沖突” 的實際含義是：為產(chǎn)生沖突的地址尋找下一個尋找下一個哈希地址。1. 開放定址法開放定址法2. 鏈地址法鏈地址法 為產(chǎn)生沖突的地址 H(key) 求得一個地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s1. 開放定址法開放定址法對增量 di 有三種取法： 1) 線性探測再散列線性探測再散列 di = c i 最簡單的情況 c=1 2) 平方探測再散列平方

53、探測再散列 di = 12, -12, 22, -22, , , 3) 隨機探測再散列隨機探測再散列 di 是一組偽隨機數(shù)列偽隨機數(shù)列 或者 di=iH2(key) (又稱雙散列函數(shù)探測又稱雙散列函數(shù)探測)即：產(chǎn)生的 Hi 均不相同，且所產(chǎn)生的 s(m-1)個個 Hi 值能覆蓋覆蓋哈希表中所有 地址。則要求： 注意：注意：增量增量 di 應具有應具有“完備性完備性” 隨機探測時的 m 和 di 沒有公因子。 平方探測時的表長 m 必為形如 4j+3 的素數(shù)（如: 7, 11, 19, 23, 等）；例如例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 設

54、定設定哈希函數(shù) H(key) = key MOD 11 ( 表長=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10190123 145568190123 1468若采用線性探測再散列線性探測再散列處理沖突若采用二次探測再散列二次探測再散列處理沖突11 8236551182361 1 2 1 3 6 2 5 1 H2(key) 是另設定的一個哈希函數(shù)，它的函數(shù)值應和 m 互為素數(shù)。若 m 為素數(shù)，則 H2(key) 可以是 1 至 m-1 之間的任意數(shù)任意數(shù)； 若 m 為 2 的冪次，則 H2(key) 應是 1 至 m-1 之間的任意奇數(shù)任意奇數(shù)。例如，當 m=11時， 可設 H2(key)=(3 key) MOD 10+1 0 1 2 3 4 5 6 7 8 9 101901231455681182362 1 1 1 2 1 2 1 3將所有哈希地址相同的記錄都鏈接在同一鏈表中。 2. 鏈地址法鏈地址法0123456140136198223116855 ASL=(61+22+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為 H(key)=key MOD 7 查找過程和造表過程一致。假設采用開放定址處理沖突，則查找過程查找過程為： 四、哈希表的查找哈希表的查找 對于給定值 K， 計算哈希地址 i = H(K)若若 ri