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

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

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

3、 Ci 12 4 9 10 11 12 13 14 15 16 若在若在A的的左子樹(shù)的左子樹(shù)上插入左子樹(shù)的左子樹(shù)上插入結(jié)結(jié) 點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至2， 需要進(jìn)行一次需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)。 (以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 若在若在A的的右子樹(shù)的右子樹(shù)上插入右子樹(shù)的右子樹(shù)上插入結(jié)結(jié) 點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從-1增加至增加至-2， 需要進(jìn)行一次需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn)。 (以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 1）LL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： 17 若在若在A的的右子樹(shù)的左子樹(shù)上插入右子樹(shù)的左子樹(shù)上插入結(jié)結(jié) 點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從-1增加至增加至-2， 需要需要先進(jìn)行先進(jìn)行順順時(shí)針旋轉(zhuǎn)，再時(shí)針旋轉(zhuǎn)，再逆逆時(shí)時(shí) 針旋轉(zhuǎn)針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 4）RL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： A B C A B C A B C 若在若在A的的左子樹(shù)的右子樹(shù)上插入左子樹(shù)的右子樹(shù)上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至 2，需要，需要先進(jìn)行先進(jìn)行逆逆時(shí)針旋轉(zhuǎn)，再時(shí)針旋轉(zhuǎn)，再 順順時(shí)針旋轉(zhuǎn)。時(shí)針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)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