靜態(tài)搜索結(jié)構(gòu)動態(tài)搜索結(jié)構(gòu)散列可擴(kuò)充散列-文庫吧
2025-08-25 08:23 本頁面
【正文】 每次都比較位于這個數(shù)列的黃金分割點(diǎn) 以下序列中查找元素 10的過程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 平均查找性能優(yōu)于折半查找 O(log2n) 最壞情況比折半查找差 （ 3）靜態(tài)樹表的搜索 不等概率查找時折半查找不一定好， 以每點(diǎn)查找次數(shù)（概率）為這點(diǎn)的權(quán) wi 帶權(quán)二叉樹總路徑長度 PH=∑wihi i PH 最小的二叉樹叫 靜態(tài)最優(yōu)二叉樹 不同于霍夫曼樹：每個結(jié)點(diǎn)都有權(quán)值，都 要查找。 E C A G B D H F I 5 4 5 1 1 2 3 4 3 A B C D E F G H I 1 1 2 5 3 4 4 3 5 PH=31+22+24+13 +53+43+33+14+54 =78 不是靜態(tài)最優(yōu)二叉樹 查找次數(shù) 權(quán)值 次優(yōu)查找樹 Nearly Optimal Search 數(shù)據(jù) al,al+1,,ai1,ai, ai+1,,ah 權(quán)值 wl,wl+1,wi1,wi,wi+1,,wh 令 h i1 Δpi= ∑wj∑wj j=i+1 j=l 取最小值： Δpi=min{Δpj: l≤j≤h} 以 ai為根， al+1,,ai1為左子樹 ai+1,,ah 為右子樹 構(gòu)造次優(yōu)查找樹 i 令 swi= ∑wj , Δpi = swhswiswi1 j=l A B C D E F G H I wi 1 1 2 5 3 4 4 3 5 s wi 1 2 4 9 12 16 20 23 28 Δpi 27 25 22 15 7 0 8 15 23 Δpi 11 9 3 1 9 8 1 7 Δpi 3 1 2 A B C D E F G H I wi 1 1 2 5 3 4 4 3 5 F D A H B E I G C 3 4 2 1 1 5 5 3 4 HP=4*1+5*2+3*2+ 1*3+3*3+4*3+5*3+ 1*4+2*4=7178 次最優(yōu)樹 平均查找次數(shù) O(HP/swh) 索引順序表 分塊有序 后一子表中的關(guān)鍵字都大于前一子表中的關(guān)鍵字 22 48 86 1 7 13 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 最大關(guān)鍵字 起始地址 索引表 索引順序表的查找 查找 關(guān)鍵字 key=38 1. 先檢索索引表 確定子表位置 2. 再在子表中搜索 22 48 86 1 7 13 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 索引表 索引順序表的查找成功的平均概率時間復(fù)雜性 索引表查找時間 +子表查找時間 設(shè)索引表長為 s，搜索表長為 n,被平均分成 s塊， 每塊長 n/s, 索引表平均查找時間 (s+1)/2 子表平均查找時間 (n/s+1)/2 189。(s+1)+ 189。(n/s+1)= 189。(s+n/s)+1 當(dāng) s=√n 時 有最小值 √n +1 有序索引順序表 當(dāng)索引順序表已經(jīng)排序時，子塊搜索可以用折半搜索。 平均查找時間： (s+1)/2 +log2(1+n/s)1/2 = log2(1+n/s)+s/2 索引也用折半查找，平均查找時間 log2(s+1)1/2 +log2(1+n/s)1/2 = log2(s+1)(1+n/s)1 當(dāng) s= √n 時 2 log2(√n +1)1 二、動態(tài)搜索表 特點(diǎn) 查找過程中生成搜索表 查找失敗時插入紀(jì)錄 二叉搜索樹 平衡二叉搜索 AVL樹 二叉搜索樹 （二叉排序樹） 其左非空子樹上所有結(jié)點(diǎn)的值都 小于 根結(jié)點(diǎn)的值 其右非空子樹上所有結(jié)點(diǎn)的值都 大于 根結(jié)點(diǎn)的值 左右子樹也是 二叉搜索樹 49 38 65 13 97 27 76 49 二叉搜索樹的作用： 排序 ， 檢索 49 38 65 97 76 13 27 49 二叉搜索樹的插入過程 45 12 8 57 60 20 11 59 50 3 45 12 57 8 20 60 3 11 59 50 57 20 8 45 60 59 3 12 50 11 57 20 60 8 45 11 3 12 50 59 平衡二叉樹 AVL樹 ——加快查找排序的速度 定義： 左右兩子樹深度之差不超過 1， 左子樹和右子樹都是平衡二叉樹。 45 12 57 8 20 60 3 11 59 50 45 12 8 20 3 11 不平衡 平衡 同一個數(shù)組的二叉排序樹和二叉平衡樹 20 30 80 40 10 60 50 70 49 20 65 97 50 27 13 49 10701340 30 49806049 10 65 97 60 27 13 49 50 701340 20 498030AVL樹的結(jié)點(diǎn) 增加一個平衡因子 left data balanceFactor right balance=height(right subtree)height(left subtree) balance=1或 1 49 38 65 13 1 1 平衡因子 左重加左 ——右轉(zhuǎn) 結(jié)點(diǎn) p左重 ，還要 加 一個 左 結(jié)點(diǎn) 不平衡 49 38 65 13 10 p lc 右轉(zhuǎn)： 將 p作 lc的右子結(jié)點(diǎn) 49 38 65 13 10 p lc 左重加左 ——右轉(zhuǎn) 結(jié)點(diǎn) p左重 ，還要 加 一個 左 結(jié)點(diǎn) 不平衡 38 13 10 40 20 p lc 4 38 13 10 40 20 p lc 4 右轉(zhuǎn)： 將 p作 lc的右子結(jié)點(diǎn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1