數(shù)據(jù)結構 二叉排序樹.ppt

1、(1) 若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；,1定義：,二叉排序樹(二叉搜索樹或二叉查找樹) 或者是一棵空樹；或者是具有如下特性的二叉樹,(3) 它的左、右子樹也都分別是二叉排序樹。,(2) 若它的右子樹不空，則右子樹上所有結點 的值均大于等于根結點的值；,9.4 二叉排序樹,例如:,是二叉排序樹。,不,對二叉排序樹進行中序遍歷，得到一個有序序列,1）若給定值等于根結點的關鍵字，則查找成功； 2）若給定值小于根結點的關鍵字，則繼續(xù)在左子樹上進行查找； 3）若給定值大于根結點的關鍵字，則繼續(xù)在右子樹上進行查找。,否則,若二叉排序樹為空，則查找不成功；,2. 二叉排序樹的查找

2、算法：,例如:,二叉排序樹,查找關鍵字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,二叉鏈表類型定義： typedef struct BiTNode KeyType key； /其它成員 struct BiTNode *lchild； struct BiTNode *rchild； BiTNode，*BiTree；,二叉排序樹的查找： BiTree bstsrch(BiTree bt，KeyType k) /二叉排序樹的存儲結構為二叉鏈表，函數(shù)返回結點的/關鍵字為k的指針，若查找不成功，返回空指針 if (t=NULL）return NULL

3、； else if（btkey=k） return(bt) else if(btkey k ) return（bstsrch(btrchild，k)） else return（bstsrch(btlchild，k)）； ,3. 二叉排序樹的構造 特點：樹結構在查找的過程中動態(tài)生成。 每次插入的結點只能成為新的葉子結點 例：關鍵字序列為 45，24，53，12，14，90 ,45,中序遍歷:12,14,24,45,53,90,(1) 插入算法： status ins_bstree(BiTree &bt，BiTree s) / 將指針s所指的結點插入到根指針為bt的二叉排序樹中 if （bt=NU

4、LL） bt = s ； / 若bt為空樹，則s為根 else if (skey btkey) ins_bstree( btlchild ，s )； else ins_bstree( btrchild ，s)； ,(2) 生成二叉排序樹的算法： BiTree crt_bstree(BiTree / crt_bstree,(1) 被刪除的結點是葉子； (2) 被刪除的結點只有左子樹或者只有右子樹； (3) 被刪除的結點既有左子樹，也有右子樹。,4. 二叉排序樹的刪除算法,可分三種情況討論：,刪除一個結點后，仍是二叉排序樹。,(1) 被刪除的結點是葉子結點,例如:,被刪關鍵字 = 20,88,其雙

5、親結點中相應指針域的值改為“空”,(2) 被刪除結點只有左子樹或者只有右子樹,p只有左子樹 ：f rchild = p lchild； p只有右子樹 ： f rchild = p rchild；,被刪關鍵字 = 40,80,40,40,以其前驅(qū)替代之，然后再刪除該前驅(qū)結點,被刪結點,前驅(qū)結點,被刪關鍵字 = 50,某結點的前驅(qū)一定在它的左子樹的最右下方,(3) 被刪除的結點既有左子樹，也有右子樹,5. 二叉排序樹的查找分析,比較次數(shù) = 被查結點所在的層次數(shù)。 二叉排序樹的性能取決于樹的形態(tài)，而二叉樹的形態(tài)取決于插入結點的順序。,關鍵字序列：(45，24，53，12，37，90),ASL =

6、(1 + 2 * 2 + 3 * 3)/6 =14/6,例：關鍵字序列：(12, 24, 37, 45, 53, 90)。 其二叉排序樹為：,ASL = (1 + 2 + 3 + 4 + 5 + 6)/6 = 21/6,12,二叉排序樹的性能取決于樹的形態(tài)，而二叉樹的形態(tài)取決于插入結點的順序。,構造一棵接近理想平衡樹的二叉排序樹？,平衡二叉樹(AVL樹)：對于每個結點， | 左子樹的深度 - 右子樹的深度| 1 結點的平衡因子=左子樹的深度 - 右子樹的深度 AVL樹中所有結點的平衡因子只有三種值： -1，0，1,是平衡樹,問：平衡樹是理想平衡樹嗎？,不是平衡樹,9.5 平衡二叉樹,如何檢測二

7、叉樹是否失去平衡？ 當插入一個新結點時，重新計算從新插入的結點到根結點的路徑上所包含結點的平衡因子（bf），如果某一結點的 bf 的絕對值超過1，則二叉樹失去平衡。,0,1,-2,失去平衡,如何使失去平衡的二叉樹達到平衡？ 需進行調(diào)整：,四種調(diào)整類型： 設x為插入結點，A結點為離插入結點x最近的一個失衡結點：,X,BLBBRAAR,X,ALABLBBR,X,X,BLBCLC CR AAR,X,X,ALACLC CR BBR,例：按下列關鍵字的次序生成一棵AVL樹。 13，24，37，90，53，28，98,13,13,插入點 插入后結果 失衡原因 調(diào)整,24,37,53,90,28,98,哈希

8、表的基本思想: “一次”查找成功。,ASL的T(n)=O(1)。,通常設定一個一維數(shù)組空間存儲記錄集合，則H(key)指示數(shù)組中的下標。 稱這個一維數(shù)組為哈希(Hash)表或散列表。 稱映射函數(shù) H 為哈希函數(shù)。 H(key)為哈希地址,9.6.1 什么是哈希表,9.6 哈希表,例1：已知一個含100個記錄的文件，其關鍵字均由兩位十進制數(shù)字組成，則可將此文件存儲在如下說明的哈希表中。 rectype hashtable100 ； 其中，hashtablei存放關鍵字為i的記錄。 構造這個哈希表的哈希函數(shù)為： Hash 1(key)= key,Zhao, Qian, Sun, Li, Wu, C

9、hen, Han, Yan, Dai,例2：對于如下 9 個關鍵字,設 哈希函數(shù)： f(key) = (字符串中首字母 - A+1) / 2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Yan,Dai,問題: 若添加關鍵字 Zhou , 怎么辦？,能否找到另一個哈希函數(shù)？,例：假定一個線性表為： A = (18，75，60，43，54，90，46) 假定選取的哈希函數(shù)為 hash3(key) = key % 13 若根據(jù)哈希函數(shù)把元素存儲到哈希表H13 中，則存儲映象為：,18,75,60,43,54,90,46,哈希表的查找 同插入元素一樣。如從表中查找關鍵字為60的元素時，只

10、要利用上面的函數(shù)計算出地址 H(60) = 60 % 13 = 8 查找不成功： 查找61： H(61)= 61%13= 9,如果 key1 key2， 但 H(key1) = H(key2) 這種現(xiàn)象稱為“沖突”，稱 key1 和 key2 為同義詞。 在實際應用中，應盡量選擇均勻的哈希函數(shù)來減少沖突。 沖突不能避免時，選定一個解決沖突的方法。,(1)裝填因子(load factor): = (負載因子) m為hash表的長度，n為填入的記錄數(shù)。,越大，沖突的可能性越大。 越小，沖突的可能性會減小，但空間的利用率變低。,為兼顧兩者， 在 0.6，0.9范圍內(nèi)為宜。,(2) 與采用的散列函數(shù)有

11、關。 (3) 與解決沖突的方法有關。 方法選擇的好壞也將減少或增加發(fā)生沖突的可能性。,發(fā)生沖突與下列三個因素有關：,9.6.2 哈希函數(shù)的構造方法,構造哈希函數(shù)的目標： 哈希地址盡可能均勻分布在表空間上均勻性好； 哈希地址計算盡量簡單。 考慮因素： 函數(shù)的復雜度； 關鍵字長度與表長的關系； 關鍵字分布情況； 元素的查找頻率。,例：1949年后出生的人口調(diào)查表，關鍵字是年份 年份 1949 1950 1951 人數(shù) H(key) = key + (-1948),此法僅適合于： 地址集合的大小 = = 關鍵字集合的大小,一、直接地址法 取關鍵字或關鍵字的某個線性函數(shù)值為哈希地址 即： H(key)

12、 = key 或： H(key) = a* key + b 其中，a， b為常數(shù)。,常用的構造哈希(散列)函數(shù)的方法：,二、數(shù)字分析法,例如：有若干記錄，關鍵字為 8 位十進制數(shù)，假設哈希表的表長為100, 對關鍵字進行分析，取隨機性較好的兩位十進制數(shù)作為哈希地址。,假設關鍵字集合中的每個關鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。,此方法僅適合于： 能預先估計出全體關鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。,三、平方取中法 將k平方后的中間幾位取為哈希地址。位數(shù)由表長決定,例1：時間 8:40:02。m=840

13、02, (m)2=705633604. 例2：四位字母標識符的hash地址，地址空間為0 999 用兩位數(shù)字01 26表示對應的26個字母， 如：AABB的內(nèi)部代碼：01010202,關鍵字 內(nèi)部代碼 (內(nèi)部代碼)2 H(key) KEYA 11052501 122157778355001 778 KEYB 11052502 122157800460004 800 AKEY 01110525 001233265775625 265 BKEY 02110525 004454315775625 315,四 、折疊法 將關鍵字分割成位數(shù)相同的幾部分，然后將這幾部分疊加，舍去進位作為哈希地址。 適用于

14、關鍵字位數(shù)很多，而且關鍵字中每一位上數(shù)字分布大致均勻的情況。 移位疊加：將分割之后的每一部分的最低位對齊，然后相加。 間界疊加：從一端向令一端沿分割界來回折疊，然后相加。,此方法適合于: 關鍵字的數(shù)字位數(shù)特別多。,例如：有一國際標準編號 0 - 4 4 2 2 0 5 8 6 - 4,五、 除留余數(shù)法 當關鍵字k為整數(shù)時，用關鍵字除以一個整數(shù)p 所得余數(shù)作為哈希的地址。 H(key) = key % p,p的選擇很重要，若選得不好容易產(chǎn)生沖突。 例如：p=10k ，(k=1,2,）或p為偶數(shù)等 由經(jīng)驗可知： 取p為素數(shù)。 p為不超過散列表的長度m的最大素數(shù)。,例如：可以讓 p = m, 并取m

15、為素數(shù)。 由于 的取值最好在 0.6， 0.9， 0.6 0.9, m ,1.1*n m 1.7*n,例：若 n = 100，則 m 最好取113, 127, 139, 143等素數(shù)。,設定哈希函數(shù)為: H(key) = Random(key) 其中，Random 為偽隨機函數(shù),六、 隨機數(shù)法,通常，此方法用于對長度不等的關鍵字構造哈希函數(shù)。,9.6.3 處理沖突的方法,設hash表的長度為m，沖突是指 j=H(K) 的位置已有記錄，(0jm-1) “處理沖突” 既為K另找一個“空”的地址。 方法1: 線性探測再散列 哈希表的存儲結構： typedef struct KeyType key；

16、/關鍵字成員 ； /其它成員 elemtype typedef elemtype hashtablem ；,哈希函數(shù)如下： H(key) = key % p 利用下面的公式求“下一個”地址。 Hi = (H(key) + di ) % m, di = 1，2，3， ，m-1 例如：已知長度為13的哈希表，現(xiàn)有四個記錄，其關鍵字分別為（19，70，33，18）。, 70 19 33 ,例如：已知長度為13的哈希表，現(xiàn)有四個記錄，其關鍵字分別為（19，70，33，18）。 哈希函數(shù)為 H(key) = key % 13, 則 H(19)=6， H(70)=5， H(33)=7， H(18)=5,用

17、線性探測再散列方法解決沖突： H1=(H(key)+d1 ) % 13= (5+1) % 13=6 H2=(5+2) % 13=7 , H3 =(5+3) % 13 = 8,18,例如: 關鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,設定哈希函數(shù) ：H(key) = key % 11 (表長=11),19 1,01 1,23 2,14 1,55 1,68 3,若采用線性探測再散列處理沖突,11 6,82 2,36 5,在查找概率相同的情況下， 查找成功時的ASL ASLsucc =(1*4+2*2+3+5+6)/9 =22/9,若采用線性探測再散列處理沖突

18、,平均查找長度ASL：,線性探測再散列的優(yōu)點： 只要哈希表未滿，總能找到一個空地址。 缺點：會產(chǎn)生二次聚集。,下一個hash地址為5、6、7、8時， 將爭奪地址為9的空間,三、 鏈地址法 將哈希表的每一個單元存放一個指針，將所有的同義詞連成一個鏈表。 假設哈希地址在區(qū)間0 . m-1上，則哈希表為一個指針數(shù)組。,typedef struct node /定義鏈表中結點 KeyType key； 其它成員 ； struct node *next； Node，*Nodeptr； typedef Nodeptr chainhashm； / 定義指針數(shù)組,ASLsucc =(61+22+3)/9 =13/9,例1: 關鍵字集合 19,