【文章內(nèi)容簡介】 態(tài)查找表 ? 二叉排序樹特性 ? 一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列（通過中序遍歷） ? 插入新記錄時，只需改變一個結(jié)點的指針，相當于在有序序列中插入一個記錄而不需要移動其它記錄 ? 二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲結(jié)構(gòu) ? 但當插入記錄的次序不當時 (如升序或降序 )，則二叉排序樹深度很深（見右圖），增加了查找的時間 80 88 92 64 75 21 19 13 56 37 5 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 932 動態(tài)查找表 ? 平衡二叉樹 平衡二叉樹 (Balanced Binary Tree, HeightBalanced Tree,又稱 AVL樹 ,Adelsen Velskii and Landis， 阿德爾森一維爾斯和蘭迪斯 )是二叉排序樹的另一種形式。其特點為：樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于 1，即 |hLhR|≤1?？梢宰C明，它們的深度和 logn是同數(shù)量級的（其中 n為節(jié)點個數(shù)）。 56 64 5 92 37 88 19 80 21 13 75 60 56 5 64 19 13 75 37 80 92 88 21 AVL樹 非 AVL樹 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 933 動態(tài)查找表 ? 平衡二叉樹平衡因子 ? 每個結(jié)點附加一個數(shù)字 , 給出該結(jié)點左子樹的高度減去右子樹的高度所得的高度差 ,這個數(shù)字即為結(jié)點的平衡因子 (balance factor) ? AVL樹任一結(jié)點平衡因子只能取 1, 0, 1 ? 若某個結(jié)點的平衡因子的絕對值大于 1，則這棵二叉搜索樹就失去了平衡，不再是 AVL樹。 56 5 64 19 13 75 37 80 92 88 21 0 0 1 0 1 0 0 0 1 0 0 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 934 動態(tài)查找表 ? 非平衡二叉樹的平衡處理 若一棵二叉排序樹是平衡二叉樹，扦入某個結(jié)點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。 處理的原則應該是處理與插入點最近的、而平衡因子又比 1大或比 1小的結(jié)點。下面將分四種情況討論平衡處理。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 935 動態(tài)查找表 1. LL型 的處理 (左左型 ) ? 如下圖所示，若在 C的左孩子 B上扦入一個左孩子結(jié)點 A，使 C的平衡因子由 1變成了 2，成為不平衡的二叉樹序樹。 ? 平衡處理：將 C順時針旋轉(zhuǎn)，成為 B的右子樹，而原來 B的右子樹則變成 C的左子樹，待扦入結(jié)點 A作為 B的左子樹。 C B A 2 1 0 C B A 0 0 0 結(jié)點旁邊的數(shù)字表示該 結(jié)點的平衡因子 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 936 動態(tài)查找表 2. LR型的處理 (左右型 ) ? 如下圖所示，在 C的左孩子 A上扦入一個右孩子 B，使的 C的平衡因子由 1變成了 2，成為不平衡的二叉排序樹。 ? 平衡處理：將 B變到 A與 C 之間，使之成為 LL型，然后按第 1種情形 LL型處理。 C B A 2 1 0 C B A 0 0 0 C B A 2 1 0 結(jié)點旁邊的數(shù)字表示該 結(jié)點的平衡因子 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 937 動態(tài)查找表 3. RR型的處理 (右右型 ) ? 如下圖所示，在 A的右孩子 B上扦入一個右孩子 C，使 A的平衡因子由 1變成 2，成為不平衡的二叉排序樹。 ? 平衡處理：將 A逆時針旋轉(zhuǎn)，成為 B的左子樹，而原來 B的左子樹則變成 A的右子樹，待扦入結(jié)點 C成為 B的右子樹。 C B A 2 1 0 C B A 0 0 0 結(jié)點旁邊的數(shù)字表示該 結(jié)點的平衡因子 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 938 動態(tài)查找表 4. RL型的處理 (右左型 ) ? 如下圖所示，在 A的右孩子 C上扦入一個左孩子 B，使 A的平衡因子由 1變成 2，成為不平衡的二叉排序樹。 ? 平衡處理：將 B變到 A與 C之間，使之成為 RR型，然后按第 (3) 種情形 RR型處理。 C B A 2 1 0 C B A 0 0 0 結(jié)點旁邊的數(shù)字表示該 結(jié)點的平衡因子 A C B 2 1 0 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 939 動態(tài)查找表 ? 例 1：給定一個關(guān)鍵字序列 4,5,7,2 ,1,3,6，試生成一棵平衡二叉樹。 ? 分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見下圖。 4 0 a) 插入 4，平衡 4 1 b) 插入 5，平衡 5 0 c) 插入 7，不平衡，要處理 4 2 5 1 7 0 4 0 5 0 7 0 RR型處理 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 940 動態(tài)查找表 4 0 5 1 7 0 d) 插入 7，平衡 2 1 4 1 5 2 7 0 2 2 e) 插入 1，不平衡，要處理 1 0 4 0 5 0 7 0 2 0 1 0 LL型處理 4 0 5 2 7 0 2 1 1 1 f) 插入 3，不平衡，要處理 3 0 LR型處理 3 0 4 0 5 1 2 0 1 0 7 0 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 941 動態(tài)查找表 3 0 4 1 5 2 2 0 1 0 7 1 f) 插入 6，不平衡，要處理 0 6 RL型處理 3 0 4 0 6 0 2 0 1 0 7 0 5 0 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 942 動態(tài)查找表 ? 平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復雜度 O(n)，它的時間復雜度與二叉排序樹的最好時間復雜相同，都為 O(log2n)。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 943 動態(tài)查找表 ? 例 2，對例 1給定的關(guān)鍵字序列 4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找 6的次數(shù)及成功的平均查找長度。 ? 分析：由于關(guān)鍵字序列的順序己經(jīng)確定，故得到的二叉排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見下座圖，得到的二叉排序樹見下右圖。 3 4 6 2 1 7 5 平衡二叉樹 3 4 5 2 1 7 6 二叉排序樹 從右圖的二叉排序樹可知，查找 6需 4次，平均查找長度 ASL=(1+2+2+3+3+3+4)/7=18/7≈ 從左圖的平衡二叉樹可知，查找 6需 2次，平均查找長度 ASL=(1+2+2+3+3+3+3)=17/7≈ 從結(jié)果可知， 平衡二叉樹的查找性能優(yōu)于二叉排序樹 。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 944 哈希表 哈希表 哈希 (Hash)表又稱散列表 ,是一種直接計算記錄存放地址的方法，它在關(guān)鍵碼與存儲位置之間直接建立了映象。 ? 哈希 函數(shù) ? 哈希函數(shù)是從關(guān)鍵字空