第9章 查找(相關(guān)試題)數(shù)據(jù)結(jié)構(gòu)

1、1 查查 找找 方方 法法 比較式比較式 查找法查找法 計算式計算式 查找法查找法 基于基于樹樹的的 查找法查找法 基于基于線性表線性表 的查找法的查找法 分塊（或索引順序表）查找法分塊（或索引順序表）查找法 折半（或二分）查找法折半（或二分）查找法 順序查找法順序查找法 對存儲結(jié)構(gòu)對存儲結(jié)構(gòu) 和關(guān)鍵字排和關(guān)鍵字排 列方式?jīng)]有列方式?jīng)]有 特殊要求特殊要求 只適合順序存只適合順序存 儲的有序表儲的有序表 另建一個索另建一個索 引表，分塊引表，分塊 有序，塊間有序，塊間 可用折半查可用折半查 找，塊內(nèi)順找，塊內(nèi)順 序查找序查找 二叉排序樹二叉排序樹 平衡二叉樹（平衡二叉樹（AVL） B-樹樹 B+

2、樹樹 哈希法哈希法/散列法散列法/雜湊法雜湊法 在記錄存儲位置在記錄存儲位置 與關(guān)鍵字之間建與關(guān)鍵字之間建 立確定的關(guān)系立確定的關(guān)系 哈希函數(shù)哈希函數(shù) 左子樹上所左子樹上所 有節(jié)點的值有節(jié)點的值 根節(jié)點的值根節(jié)點的值 右子樹上所右子樹上所 有節(jié)點的值有節(jié)點的值 左、右子樹深左、右子樹深 度之差的絕對度之差的絕對 值不超過值不超過1的的 二叉排序樹二叉排序樹 一種平衡的多路一種平衡的多路 查找樹，查找樹，m叉樹叉樹 B-樹的變型樹，關(guān)樹的變型樹，關(guān) 鍵字信息全部在葉鍵字信息全部在葉 子結(jié)點中，其它結(jié)子結(jié)點中，其它結(jié) 點是其索引點是其索引 3 4 5 6 7 10 i123456789 10 11

3、 Ci 12 4 9 10 11 12 13 14 15 16 若在若在A的的左子樹的左子樹上插入左子樹的左子樹上插入結(jié)結(jié) 點，使點，使A的平衡因子從的平衡因子從1增加至增加至2， 需要進行一次需要進行一次順時針旋轉(zhuǎn)順時針旋轉(zhuǎn)。 (以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 若在若在A的的右子樹的右子樹上插入右子樹的右子樹上插入結(jié)結(jié) 點，使點，使A的平衡因子從的平衡因子從-1增加至增加至-2， 需要進行一次需要進行一次逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)。 (以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 1）LL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： 17 若在若在A的的右子樹的左子樹上插入右子樹的左子樹上插入結(jié)結(jié) 點，使點，使A的平衡因子從的平衡因子從-1增加至增加至-2， 需要需要先進行先進行順順時針旋轉(zhuǎn)，再時針旋轉(zhuǎn)，再逆逆時時 針旋轉(zhuǎn)針旋轉(zhuǎn)。 (以插入的結(jié)點以插入的結(jié)點C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 4）RL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： A B C A B C A B C 若在若在A的的左子樹的右子樹上插入左子樹的右子樹上插入 結(jié)點，使結(jié)點，使A的平衡因子從的平衡因子從1增加至增加至 2，需要，需要先進行先進行逆逆時針旋轉(zhuǎn)，再時針旋轉(zhuǎn)，再 順順時針旋轉(zhuǎn)。時針旋轉(zhuǎn)。 (以插入的結(jié)點以插入的結(jié)點C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） AB C A B C A B C 3 3）LRLR平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： 18 root 50 15 71 84 3