windows用戶-(編輯修改稿)
2024-08-13 18:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 上查找 ?樹(shù)中已有 ， 不再插入 ?樹(shù)中沒(méi)有 ， 查找 直至某個(gè)葉子結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)為空為止 ， 則插入結(jié)點(diǎn)應(yīng)為該 葉子結(jié)點(diǎn) 的左孩子或右孩子 2022年 8月 14日 45 12 53 3 37 24 100 61 90 78 20 插入結(jié)點(diǎn) 20 二叉排序樹(shù)的操作－插入 2022年 8月 14日 {10， 18， 3， 8， 12， 2， 7} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 從空樹(shù)出發(fā)，經(jīng)過(guò)一系列的查找、插入操作之后，可生成一棵二叉排序樹(shù) 二叉排序樹(shù)的操作－生成 2022年 8月 14日 不同插入次序的序列生成不同形態(tài)的二叉排序樹(shù) 40 24 55 12 37 12 24 37 40 55 40， 24， 12， 37， 55 12， 24， 37， 40， 55 二叉排序樹(shù)的操作－生成 2022年 8月 14日 二叉排序樹(shù)的操作－刪除 ? 將因刪除結(jié)點(diǎn)而斷開(kāi)的二叉鏈表重新鏈接起來(lái) ? 防止重新鏈接后樹(shù)的高度增加 2022年 8月 14日 –刪除葉結(jié)點(diǎn) ，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。 –被刪結(jié)點(diǎn)缺右子樹(shù) ，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。 –被刪結(jié)點(diǎn)缺左子樹(shù) ，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。 – 被刪結(jié)點(diǎn)左、右子樹(shù)都存在 ，可以在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn) (關(guān)鍵碼最小 ),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來(lái)處理這個(gè)結(jié)點(diǎn)的刪除問(wèn)題。 2022年 8月 14日 第 i層結(jié)點(diǎn)需比較 i次。在等概率的前提下，上述兩圖的 平均查找長(zhǎng)度 為： )(35/)54321()()23221(11右圖左圖????????????????niiiniiicpcp40 24 55 12 37 12 24 37 40 55 查找的性能分析 2022年 8月 14日 平均查找長(zhǎng)度和二叉樹(shù)的形態(tài)有關(guān)，即， 最好： log2n（形態(tài)勻稱，與二分查找的判定樹(shù)相似） 最壞 : （ n+1)/2（單支樹(shù)） 查找的性能分析 40 24 55 12 37 12 24 37 40 55 )(35/)54321()()23221(11右圖左圖????????????????niiiniiicpcp 2022年 8月 14日 問(wèn)題：如何提高二叉排序樹(shù)的查找效率？ 盡量讓二叉樹(shù)的形狀均衡 ?左、右子樹(shù)是平衡二叉樹(shù)； ?所有結(jié)點(diǎn)的左、右子樹(shù)深度之差的絕對(duì)值 ≤ 1 平衡二叉樹(shù) 平衡因子 :該結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度差 2022年 8月 14日 ? 任一結(jié)點(diǎn)的平衡因子只能?。? 0 或 1；如果樹(shù)中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于 1，則這棵二叉樹(shù)就失去平衡，不再是 AVL樹(shù)； ? 對(duì)于一棵有 n個(gè)結(jié)點(diǎn)的 AVL樹(shù)，其 高度保持在O(log2n)數(shù)量級(jí)， ASL也保持在 O(log2n)量級(jí)。 2022年 8月 14日 (a) 平衡樹(shù) (b) 不平衡樹(shù) 練習(xí)：判斷下列二叉樹(shù)是否 AVL樹(shù)？ 0 0 0 1 1 1 1 2 0 0 0 1 1 B與 B+樹(shù)（自學(xué)） B+和 B樹(shù) 是平衡多路查找， B樹(shù) 特點(diǎn)為：若樹(shù)中結(jié)點(diǎn)有 m個(gè)關(guān)鍵字則該結(jié)點(diǎn)有 m+1棵子樹(shù)； B+樹(shù) 特點(diǎn)為：若樹(shù)中結(jié)點(diǎn)有 m個(gè)關(guān)鍵字則該結(jié)點(diǎn)有 m棵子樹(shù)，且還多了個(gè)指向最小關(guān)鍵字的葉子結(jié)點(diǎn)的頭指針 。 預(yù)習(xí)任務(wù)（經(jīng)驗(yàn)值： 200） 哈希函數(shù)有哪些構(gòu)造方法？ 哈希表有什么處理沖突的方法？ 數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法 開(kāi)放定址法、 鏈地址法 2022年 8月 14日 哈希表的查找 ? 基本思想： 記錄的存儲(chǔ)位置與關(guān)鍵字之間存在對(duì)應(yīng)關(guān)系， Loc(i)=H(keyi) ? 優(yōu)點(diǎn)： 查找速度極快 O(1),查找效率與元素個(gè)數(shù) n無(wú)關(guān) 哈希函數(shù) 關(guān)鍵字 集合 存儲(chǔ)地址 集合 hash 2022年 8月 14日 若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如： 將 2022022810201的所有信息存入 V[01]單元； 將 2022022810202的所有信息存入 V[02]單元； …… 將 2022022810231的所有信息存入 V[31]單元。 查找 2022022810216的信息，可直接訪問(wèn) V[16]！ 例 1 2022年 8月 14日 數(shù)據(jù)元素序列 (14， 23， 39， 9， 25， 11)， 若規(guī)定每個(gè)元素 k的存儲(chǔ)地址 H（ k） ＝ k， 請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖 。 … 14 … 11 … 9 … 內(nèi)容 地址 … 39 … 25 24 23 14 11 9 23 25 39 例 2 2022年 8月 14日 根據(jù)哈希函數(shù) H（ k）＝ k 查找 key=9,則訪問(wèn) H(9)=9號(hào)地址，若內(nèi)容為 9則成功； 若查不到，則返回一個(gè)特殊值，如空指針或空記錄。 如何查找 … 14 … 11 … 9 … 內(nèi)容 地址 … 39 … 25 24 23 14 11 9 23 25 39 2022年 8月 14日 哈希方法 (雜湊法 ) 選取某個(gè) 函數(shù) ，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放； 查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值 k計(jì)算地址， 將 k與地址單元中元素關(guān)鍵碼進(jìn)行比 ，確定查找是否成功。 哈希函數(shù) (雜湊函數(shù) )： 哈希方法中使用的 轉(zhuǎn)換函數(shù) 有關(guān)術(shù)語(yǔ) 2022年 8月 14日 沖 突： 不同的關(guān)鍵碼映射到同一個(gè)哈希地址 哈希表 (雜湊表 )： 按上述思想構(gòu)造的表 有關(guān)術(shù)語(yǔ) … 14 … 11 … 9 … 內(nèi)容 地址 … 39 … 25 24 23 14 11 9 23 25 39 同義詞： 具有 相同函數(shù)值 的兩個(gè)關(guān)鍵字 key1?key2，但 H(key1)=H(key2) 2022年 8月 14日 （ 14， 23， 39， 9， 25， 11） 哈希函數(shù)： H(k)=k mod 7 25 39 23 9 14 6個(gè)元素用 7個(gè) 地址應(yīng)該足夠 ! H(14)=14%7=0 11 H(25)=25%7=4 H(11)=11%7=4 同義詞 有沖突 0 1 2 3 4 5 6 沖突現(xiàn)象舉例 2022年 8月 14日 沖突是不可能避免的 如何減少?zèng)_突 構(gòu)造好的哈希函數(shù) 制定一個(gè)好的解決沖突方案 2022年 8月 14日
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1