【正文】 10 11 5 13 19 21 37 56 64 75 80 88 92 low high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 直至 lowhigh時(shí)，查找失敗 2022年 8月 14日 折半查找（非遞歸算法） ?設(shè)表長(zhǎng)為 n， low、 high和 mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn) ,k為給定值 ?初始時(shí)，令 low=1,high=n,mid=?(low+high)/2? ?讓 k與 mid指向的記錄比較 – 若 k==R[mid].key，查找成功 – 若 kR[mid].key，則 high=mid1 – 若 kR[mid].key，則 low=mid+1 ?重復(fù)上述操作，直至 lowhigh時(shí)，查找失敗 2022年 8月 14日 折半查找（遞歸算法） int Search_Bin (SSTable ST, keyType key, int low, int high) { if(lowhigh) return 0。 if(key==[mid].key) return mid。 2022年 8月 14日 查找成功時(shí)比較次數(shù)：為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)，不超過(guò)樹(shù)的深度 d = ? log2 n ? + 1 查找不成功的過(guò)程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑 d或d1。 二叉排序樹(shù)或是空樹(shù)，或是滿足如下性質(zhì)的二叉樹(shù)： (1)若其左子樹(shù)非空，則 左子樹(shù) 上所有結(jié)點(diǎn)的值均 小 于根結(jié)點(diǎn)的值； (2)若其右子樹(shù)非空，則 右子樹(shù) 上所有結(jié)點(diǎn)的值均 大 于等于根結(jié)點(diǎn)的值； (3)其左右子樹(shù)本身又各是一棵二叉排序樹(shù) 進(jìn)階任務(wù) （完成每任務(wù)加經(jīng)驗(yàn)值 100） 請(qǐng)把下面名詞術(shù)語(yǔ)翻譯成英文，并大聲讀與拼寫出來(lái)： 查找 關(guān)鍵字 靜態(tài)查找表 動(dòng)態(tài)查找表 平均查找長(zhǎng)度 順序查找 折半查找 二叉排序樹(shù) 平衡二叉樹(shù) 散列表 散列函數(shù) 沖突 同義詞 裝填因子 search Static search table Dynamic search table Average search length Sequential Search Binary Search Binary Sort Tree Balanced Binary Tree Hash table Hash function Conflict synonyms filling factor Keyword 2022年 8月 14日 二叉排序樹(shù)或是空樹(shù)，或是滿足如下性質(zhì)的二叉樹(shù)： (1)若其左子樹(shù)非空，則 左子樹(shù) 上所有結(jié)點(diǎn)的值均 小于根結(jié)點(diǎn)的值； (2)若其右子樹(shù)非空，則 右子樹(shù) 上所有結(jié)點(diǎn)的值均 大于等于根結(jié)點(diǎn)的值； (3)其左右子樹(shù)本身又各是一棵二叉排序樹(shù) 二叉排序樹(shù) 2022年 8月 14日 練習(xí)（經(jīng)驗(yàn)值 200） 下列圖形中，哪個(gè)不是二叉排序樹(shù) ？ 2022年 8月 14日 45 12 53 3 37 24 100 61 90 78 3， 12， 24， 37， 45， 53， 61， 78， 90， 100 遞增 得到一個(gè)關(guān)鍵字的遞增有序序列 練習(xí)（經(jīng)驗(yàn)值 200） 中序遍歷二叉排序樹(shù)后的結(jié)果有什么規(guī)律？ 2022年 8月 14日 若查找的關(guān)鍵字 等于 根結(jié)點(diǎn)， 成功 否則 若 小于 根結(jié)點(diǎn)，查其 左子樹(shù) 若 大于 根結(jié)點(diǎn)，查其 右子樹(shù) 在左右子樹(shù)上的操作類似 122 250 300 110 200 99 105 230 216 二叉排序樹(shù)的操作－查找 2022年 8月 14日 （ 1）若二叉排序樹(shù)為空，則查找失敗，返回空指針。 【 算法思想 】 2022年 8月 14日 BSTree SearchBST(BSTree T,KeyType key) { if((!T) || key==T) return T。 //在左子樹(shù)中繼續(xù)查找 else return SearchBST(Trchild,key)。 –被刪結(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)題。在等概率的前提下，上述兩圖的 平均查找長(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í)。 預(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ī)，