靜態(tài)搜索結(jié)構(gòu)動(dòng)態(tài)搜索結(jié)構(gòu)散列可擴(kuò)充散列-文庫(kù)吧
2025-08-25 08:23 本頁(yè)面
【正文】 每次都比較位于這個(gè)數(shù)列的黃金分割點(diǎn) 以下序列中查找元素 10的過(guò)程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 平均查找性能優(yōu)于折半查找 O(log2n) 最壞情況比折半查找差 （ 3）靜態(tài)樹(shù)表的搜索 不等概率查找時(shí)折半查找不一定好， 以每點(diǎn)查找次數(shù)（概率）為這點(diǎn)的權(quán) wi 帶權(quán)二叉樹(shù)總路徑長(zhǎng)度 PH=∑wihi i PH 最小的二叉樹(shù)叫 靜態(tài)最優(yōu)二叉樹(shù) 不同于霍夫曼樹(shù)：每個(gè)結(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ù) 查找次數(shù) 權(quán)值 次優(yōu)查找樹(shù) 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為左子樹(shù) ai+1,,ah 為右子樹(shù) 構(gòu)造次優(yōu)查找樹(shù) 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ù) 平均查找次數(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 索引表 索引順序表的查找成功的平均概率時(shí)間復(fù)雜性 索引表查找時(shí)間 +子表查找時(shí)間 設(shè)索引表長(zhǎng)為 s，搜索表長(zhǎng)為 n,被平均分成 s塊， 每塊長(zhǎng) n/s, 索引表平均查找時(shí)間 (s+1)/2 子表平均查找時(shí)間 (n/s+1)/2 189。(s+1)+ 189。(n/s+1)= 189。(s+n/s)+1 當(dāng) s=√n 時(shí) 有最小值 √n +1 有序索引順序表 當(dāng)索引順序表已經(jīng)排序時(shí)，子塊搜索可以用折半搜索。 平均查找時(shí)間： (s+1)/2 +log2(1+n/s)1/2 = log2(1+n/s)+s/2 索引也用折半查找，平均查找時(shí)間 log2(s+1)1/2 +log2(1+n/s)1/2 = log2(s+1)(1+n/s)1 當(dāng) s= √n 時(shí) 2 log2(√n +1)1 二、動(dòng)態(tài)搜索表 特點(diǎn) 查找過(guò)程中生成搜索表 查找失敗時(shí)插入紀(jì)錄 二叉搜索樹(shù) 平衡二叉搜索 AVL樹(shù) 二叉搜索樹(shù) （二叉排序樹(shù)） 其左非空子樹(shù)上所有結(jié)點(diǎn)的值都 小于 根結(jié)點(diǎn)的值 其右非空子樹(shù)上所有結(jié)點(diǎn)的值都 大于 根結(jié)點(diǎn)的值 左右子樹(shù)也是 二叉搜索樹(shù) 49 38 65 13 97 27 76 49 二叉搜索樹(shù)的作用： 排序 ， 檢索 49 38 65 97 76 13 27 49 二叉搜索樹(shù)的插入過(guò)程 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 平衡二叉樹(shù) AVL樹(shù) ——加快查找排序的速度 定義： 左右兩子樹(shù)深度之差不超過(guò) 1， 左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)。 45 12 57 8 20 60 3 11 59 50 45 12 8 20 3 11 不平衡 平衡 同一個(gè)數(shù)組的二叉排序樹(shù)和二叉平衡樹(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樹(shù)的結(jié)點(diǎn) 增加一個(gè)平衡因子 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左重 ，還要 加 一個(gè) 左 結(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左重 ，還要 加 一個(gè) 左 結(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號(hào)-1