動(dòng)態(tài)查找表.ppt

1、數(shù)據(jù)結(jié)構(gòu)與算法,9.2 動(dòng)態(tài)查找表,什么是動(dòng)態(tài)查找表？ 查找表中的數(shù)據(jù)隨著查找的結(jié)果而發(fā)生改變。,查找,成功：刪除該數(shù)據(jù)元素,失?。翰迦朐摂?shù)據(jù)元素,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,定義 二叉排序樹（BST）：或者是一棵空的二叉樹，或者是： 非空左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 非空右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 它的左右子樹也都是二叉排序樹。,數(shù)據(jù)結(jié)構(gòu)與算法,性質(zhì) 中序遍歷是 有序序列 存儲(chǔ)結(jié)構(gòu) 采用二叉鏈表,9.2.1 二叉排序樹,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,查找算法 若二叉排序樹為空，則查找不成功；否則 1）若給定值k等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； 2）

2、若k小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上查找； 3）若k大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上查找。,查35,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,int SearchBST ( T, k) / 在樹T中查找關(guān)鍵字為k的元素 if (T=Null) return False; / 查找不成功 else if ( k =T-data.key) return Treu; / 查找成功 else if ( kdata.key) / 在左子樹中繼續(xù)查找 SearchBST (T-lchild, k ); else / 在右子樹中繼續(xù)查找 SearchBST (T-rchild, k); ,改進(jìn)：為方便

3、插入與刪除，查找結(jié)束時(shí)記住k的雙親位置,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,int SearchBST ( T, k , ,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,插入算法 在查找不成功的情況下，尚需插入關(guān)鍵字等于給定值k的元素： 算法： 若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為根結(jié)點(diǎn)； 否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子，其插入位置由查找過程中得到。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,插入算法 在BST中插入值為k的結(jié)點(diǎn)，步驟如下：, 若樹為空，則生成值為k的根結(jié)點(diǎn)； 若k小于根，在根的左子樹中插入； 若k大于根，在根的右子樹中插入； 若k等于根結(jié)點(diǎn)的值，表明二叉排序樹中已有此關(guān)鍵字，

4、則無須插入。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,int Insert-BST(T , k) /在T中插入值為k的結(jié)點(diǎn) if (T=NULL) T=(BiNode*)malloc(sizeof(BiNode); /插入為根 T-key=k; T-lchild=T-rchild=NULL; return Ok; else if (kkey) /插入到左子樹 Insert-BST(T-lchild, k); else if (kT-key) /插入到右子樹 Insert-BST(T-rchild, k); else return False; ,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,int

5、Insert-BST(BiTree / 樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入 ,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,建立二叉排序樹 在一棵空樹上不斷地插入結(jié)點(diǎn),Bitree Creat-BST(int a , int n) /將a中的n個(gè)數(shù)據(jù)插入BST Bitree root; root = NULL; for (i = 0; i n; i+) Insert-BST (root, ai); /調(diào)用插入函數(shù) return root ,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,例：設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 試畫出二叉排序樹。,數(shù)據(jù)結(jié)

6、構(gòu)與算法,9.2.1 二叉排序樹,刪除算法 在二叉排序樹上刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。 思想：分三種情況討論 被刪除的結(jié)點(diǎn)是葉子； 被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹； 被刪除的結(jié)點(diǎn)左右子樹均非空。,葉子,只有左子樹,左右子樹非空,只有右子樹,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,刪除算法 被刪結(jié)點(diǎn)是葉子的情形：將雙親的相應(yīng)孩子指針置“空”,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,刪除算法 刪除單支結(jié)點(diǎn)的情形 將雙親結(jié)點(diǎn)的相應(yīng)指針指向被刪除結(jié)點(diǎn)的子樹。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,刪除算法 刪除雙支結(jié)點(diǎn)的情形： 方法1：以其前驅(qū)（左子樹中的最大值）替代之，然后再

7、刪除該前驅(qū)結(jié)點(diǎn)。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,刪除算法 刪除雙支結(jié)點(diǎn)的情形： 方法2：將其右子樹作為左子樹最右邊的子樹，然后將其左子樹作為雙親的子樹，。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.1 二叉排序樹,性能分析 對(duì)不同形態(tài)的二叉排序樹，其平均查找長(zhǎng)度差別較大。 例：輸入相同的數(shù)據(jù)，輸入順序不同，得到不同形態(tài)的二叉排序樹。,輸入：3，12，5，4，91，11,輸入：3，4，5，11，12，91,ASL=(1+2*2+3*3)/62.33,ASL=(1+2+3+4+5+6)/6 =3.5,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,定義 具有下列性質(zhì)的二叉排序樹： 根結(jié)點(diǎn)的左子樹和右子樹的深度最多

8、相差1; 子樹也都是平衡二叉樹（AVL)。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,平衡因子 結(jié)點(diǎn)的左子樹的深度與右子樹的深度之差。 由平衡二叉樹定義可知，平衡二叉樹所有結(jié)點(diǎn)的平衡因子只能取1，0，1三個(gè)值之一。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,平衡二叉樹的建立 每輸入一個(gè)結(jié)點(diǎn)時(shí)，若發(fā)現(xiàn)不平衡，則在滿足二叉排序樹的前提下，旋轉(zhuǎn)為平衡的。 例：輸入3，5，7，2，90 建立AVL,此時(shí)，失去平衡， 如何旋轉(zhuǎn)？,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,（1）LL型的平衡旋轉(zhuǎn),數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,（1）LR型的平衡旋轉(zhuǎn),數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,（1）RL型

9、的平衡旋轉(zhuǎn),數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,（1）RR型的平衡旋轉(zhuǎn),數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,例：輸入 4，5，7，2，1，3，6，建立平衡的二叉排序樹（AVL）,RR型,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,LL型,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,LR型,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.2 平衡二叉樹,RL型,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.3 B樹與B+樹,B樹 B樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.3 B樹與B+樹,B樹 一棵m階的B樹，或者為空樹，或?yàn)闈M足下列特性的m叉樹： 每個(gè)結(jié)點(diǎn)至多有m棵子樹。 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2

10、棵子樹。 除根結(jié)點(diǎn)之外的所有非葉結(jié)點(diǎn)至少有m/2 棵子樹。 非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大有序排列，即：K1 K2 Kn;且Ai-1所指子樹上所有關(guān)鍵字均小于Ki;Ai所指子樹上所有關(guān)鍵字均大于Ki;,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.3 B樹與B+樹,B樹 B樹主要用于外部查找（即，該查找表存儲(chǔ)在外存） B樹是一種動(dòng)態(tài)查找樹 B樹的查找類似于二叉排序樹 B樹中插入一個(gè)元素時(shí)，為限制結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，可能會(huì)“分裂”結(jié)點(diǎn)。 B樹中刪除一個(gè)元素時(shí)，可能會(huì)“合并”結(jié)點(diǎn)。,數(shù)據(jù)結(jié)構(gòu)與算法,9.2.3 B樹與B+樹,B+樹 應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B樹的變形樹。,數(shù)據(jù)結(jié)構(gòu)與算法,9.3 hash表,引入 前

11、面討論的查找方法，查找時(shí)需要進(jìn)行一系列對(duì)關(guān)鍵字的“比較” 。 將關(guān)鍵字與存儲(chǔ)位置之間建立一種對(duì)應(yīng)關(guān)系，理想的情況下，不需要比較即可進(jìn)行查找。,數(shù)據(jù)結(jié)構(gòu)與算法,9.3 hash表,什么是hash表？ 以數(shù)據(jù)元素的關(guān)鍵字K為自變量，通過一個(gè)確定的函數(shù)關(guān)系，計(jì)算出對(duì)應(yīng)的函數(shù)值f(K)，把這個(gè)值作為其的存儲(chǔ)位置。查找時(shí)，根據(jù)這個(gè)函數(shù)計(jì)算其存儲(chǔ)位置。 Hash表便是存儲(chǔ)數(shù)據(jù)元素的查找表,數(shù)據(jù)結(jié)構(gòu)與算法,9.3 hash表,Hash表實(shí)例,數(shù)據(jù)結(jié)構(gòu)與算法,9.3 hash表,若對(duì)于不相等的關(guān)鍵字計(jì)算出了相同的hash地址，則稱該現(xiàn)象為hash沖突，發(fā)生沖突的兩個(gè)關(guān)鍵字為該Hash函數(shù)的同義詞。在實(shí)際應(yīng)用中

12、，不產(chǎn)生沖突的Hash函數(shù)極少存在。,【例】 假設(shè)一組記錄的關(guān)鍵字分別為17，27，1，20，22，6，10，13，41，15，25。選取關(guān)鍵字與記錄位置間的函數(shù)為f(key)=key %11。,17， 6,數(shù)據(jù)結(jié)構(gòu)與算法,9.3 hash表,兩個(gè)主要問題 如何設(shè)計(jì)hash函數(shù)？ 沖突怎么解決？,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,要點(diǎn) 如果hash表有m個(gè)地址，則hash函數(shù)值域必須為0-m; Hash函數(shù)計(jì)算出來的地址應(yīng)能“均勻”的分布在整個(gè)地址空間； Hash函數(shù)應(yīng)是簡(jiǎn)單的，能在短時(shí)間內(nèi)計(jì)算出來。,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,直接定址法 此類函數(shù)取

13、關(guān)鍵碼的某個(gè)線性函數(shù)值作為散列地址： Hash( key )a * key +b a, b為常數(shù) 這類散列函數(shù)是一對(duì)一的映射，一般不會(huì)產(chǎn)生沖突。但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同。,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,示例：有一組關(guān)鍵碼如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函數(shù)為 Hash (key) = key - 940000 則有 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527

14、Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按計(jì)算出的地址存放記錄。,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,數(shù)字分析法 設(shè)有 n 個(gè) d 位數(shù)，每一位可能有 r 種不同的符號(hào)。這 r 種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，選取其中各種符號(hào)分布均勻的若干位作為散列地址。,9 4 2 1 4 8 9 4 1 2 6 9 9 4 0 5 2 7 9 4 1 6 3 0 9 4 1 8 0 5 9 4 1 5 5 8 9

15、4 2 0 4 7 9 4 0 0 0 1 ,選位,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,除留余數(shù)法,設(shè)hash表的長(zhǎng)度 m，hash函數(shù)為： hash ( key ) = key % p p m 其中, “%”是整數(shù)除法取余的運(yùn)算，p為質(zhì)數(shù)。 示例：有一個(gè)關(guān)鍵碼 key = 962148，散列表大小 m = 25，取質(zhì)數(shù) p= 23。則hash地址為:,hash ( 962148 ) = 962148 % 23 = 12。,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,平方取中法,此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方，然后按照散列表的大小

16、取中間的若干位作為散列地址。,標(biāo)識(shí)符 內(nèi)碼 內(nèi)碼的平方 散列地址 A 01 01 001 A1 0134 20420 042 AMAX 01150130 135423617100 236,例,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.2 Hash函數(shù)的構(gòu)造方法,折疊法,把關(guān)鍵碼等分成幾部分，把這些部分的數(shù)據(jù)疊加起來作為hash地址。,例 key = 23938587841 ，關(guān)鍵碼可劃分為 4段： 239 385 878 41,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.3 處理沖突的方法,什么是沖突？ 對(duì)于不同的關(guān)鍵字可能得到同一哈希地址，即key1key2，但h(key1)=h(key2)，這種現(xiàn)象叫沖突。 具有相同函數(shù)值的兩

17、個(gè)關(guān)鍵字對(duì)該哈希函數(shù)來說稱做“同義詞”。 在一般情況下，沖突只能盡可能地少，而不能完全避免,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.3 處理沖突的方法,開放定址法,當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開放的地址）。即 Hi=(H(key)+di) MOD m，i=1,2,k (km-1),其中：H(key)哈希函數(shù)，m哈希表表長(zhǎng)，di增量序列,di有下列三種取法,線性探測(cè)再散列：di=1,2,3,m-1,二次探測(cè)再散列：di=1,-1,2,-2,k (km/2),偽隨機(jī)探測(cè)再散列：di=偽隨機(jī)數(shù)序列,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.3 處理沖突的方法,例： 有關(guān)鍵字序列為 36，

18、7，40，11，16，81，22，8，14 ，Hash表表長(zhǎng)m =11，用線性探測(cè)法處理沖突，建立Hash表： H(key)=key % 7,沖突時(shí)：Hi=(H(key)+di) % m， di=1,2,3,m-1,沖突次數(shù),0 0 2 0 2 6 8,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.3 處理沖突的方法,鏈地址法 將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中,Hash(key)=key % 11,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.4 hash表的查找及性能,Hash表的查找 查找過程和造表過程一致。假設(shè)采用開放定址處理沖突，則查找過程為:,1. 對(duì)于給定值K, 計(jì)算哈希地址 i = H(K) 2. if (r

19、i 為空) 查找失?。?else if ( ri.key = K ) 查找成功; else 求下一地址i = Hi; 3. 重復(fù)2.,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.4 hash表的查找及性能,typedef struct ElemType *elem; /hash表 int count; /表中元素個(gè)數(shù) HashTable;,14,1,68,27,55,19,20,84,79,23,11,10,Hash表結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)與算法,9.3.4 hash表的查找及性能,查找（開放定址解決沖突）,SearchHash(HashTable H, k, int /失敗 ,數(shù)據(jù)結(jié)構(gòu)與算法,9.3.4 hash表的查

20、找及性能,插入一個(gè)元素,InsertHash(HashTable /失敗 ,數(shù)據(jù)結(jié)構(gòu)與算法,例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)， 哈希函數(shù)為：H(key)=key MOD 13, 哈希表長(zhǎng)為m=16，用線性探測(cè)再散列處理沖突,H(55)=3 沖突，H1=(3+1)MOD16=4 沖突，H2=(3+2)MOD16=5,H(79)=1 沖突，H1=(1+1)MOD16=2 沖突，H2=(1+2)MOD16=3 沖突，H3=(1+3)MOD16=4 沖突，H4=(1+4)MOD16=5 沖突，H5=(1+5)MOD16=6 沖突，H6=(1+6)MOD16=7 沖突，H7=(1+7)MOD16=8 沖突，H8=(1+8)MOD16=9,H(19)=6,H(14)=1,H(23)=10,H(1)=1 沖突，H1=(1+1) MOD16=2,H(68)=3,H(2