第9章 查找(相關試題)數(shù)據(jù)結構

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

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

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