【正文】 記錄插入圖書表，對這類表除了提供前面的介紹的查找外，還要提供動態(tài)查找功能： 1. 查找某個“特定”元素是否在表中，若不在，將該元素插入； 2. 查找某個“特定”元素是否在表中，若在，從表中刪除； ? 如何組織動態(tài)查找表？ 用靜態(tài)查找方法不能滿足要求了。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 921 動態(tài)查找表 二叉排序樹 二叉排序樹又稱二叉查找樹 ? 空樹或者是具有如下特性的二叉樹： 1. 若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值； 2. 若右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值； 3. 左、右子樹也都分別是二叉排序樹。 ? 當(dāng)樹中不存在查找的結(jié)點時，作插入操作 ? 新插入的結(jié)點一定是葉子結(jié)點（只需改動一個結(jié)點的指針） ? 該葉子結(jié)點是查找不成功時路徑上訪問的最后一個結(jié)點左孩子或右孩子 (新結(jié)點值小于或大于該結(jié)點值 ) 56 64 5 92 37 88 19 80 21 13 75 例：在右圖二叉樹中插入結(jié)點 94。也即保持中序遍歷后，輸出為有序序列 ? 被刪除結(jié)點具有以下三種情況 1. 是葉子結(jié)點 2. 只有左子樹或右子樹 3. 同時有左、右子樹 ? 下面針對三種情況各舉一例。 ? 例：刪除右二叉 排序 樹中的 88節(jié)點 56 64 5 92 37 88 19 80 21 13 75 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 928 動態(tài)查找表 ? 被刪除結(jié)點只有左子樹或右子樹 刪除結(jié)點 ,讓其父結(jié)點指向該結(jié)點的指針指向其左子樹 (或右子樹 ),即用孩子結(jié)點替代被刪除結(jié)點即可 ? 例：對于右邊二叉 排序 樹中，先刪除節(jié)點 37，再刪除節(jié)點 64。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 930 動態(tài)查找表 ? 二叉排序樹性能分析 ? 在最好的情況下，二叉排序樹為一近似完全二叉樹時，其查找深度為 log2n量級，即其時間復(fù)雜性為 O(log2n) ? 在最壞的情況下，二叉排序樹為近似線性表時 (如以升序或降序輸入結(jié)點時，見右圖 )，其查找深度為 n量級，即其時間復(fù)雜性為 O(n) 80 88 92 64 75 21 19 13 56 37 5 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 931 動態(tài)查找表 ? 二叉排序樹特性 ? 一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列（通過中序遍歷） ? 插入新記錄時，只需改變一個結(jié)點的指針，相當(dāng)于在有序序列中插入一個記錄而不需要移動其它記錄 ? 二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲結(jié)構(gòu) ? 但當(dāng)插入記錄的次序不當(dāng)時 (如升序或降序 )，則二叉排序樹深度很深（見右圖），增加了查找的時間 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， 阿德爾森一維爾斯和蘭迪斯 )是二叉排序樹的另一種形式?？梢宰C明，它們的深度和 logn是同數(shù)量級的（其中 n為節(jié)點個數(shù)）。 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é)點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進(jìn)行平衡處理，使其變成一棵平衡二叉樹。下面將分四種情況討論平衡處理。 ? 平衡處理：將 C順時針旋轉(zhuǎn)，成為 B的右子樹，而原來 B的右子樹則變成 C的左子樹，待扦入結(jié)點 A作為 B的左子樹。 ? 平衡處理：將 B變到 A與 C 之間，使之成為 LL型，然后按第 1種情形 LL型處理。 ? 平衡處理：將 A逆時針旋轉(zhuǎn)，成為 B的左子樹，而原來 B的左子樹則變成 A的右子樹，待扦入結(jié)點 C成為 B的右子樹。 ? 平衡處理：將 B變到 A與 C之間，使之成為 RR型，然后按第 (3) 種情形 RR型處理。 ? 分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹。 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)查找表 ? 平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 943 動態(tài)查找表 ? 例 2，對例 1給定的關(guān)鍵字序列 4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找 6的次數(shù)及成功的平均查找長度。得到的平衡二叉樹見下座圖，得到的二叉排序樹見下右圖。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 944 哈希表 哈希表 哈希 (Hash)表又稱散列表 ,是一種直接計算記錄存放地址的方法，它在關(guān)鍵碼與存儲位置之間直接建立了映象?？蓪懗桑? addr(ai)= H(keyi) ? H( )為哈希函數(shù) ? keyi是表中元素 ai關(guān)鍵字 ,addr(ai)是存儲地址 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 945 哈希表 ? 哈希查找 ? 哈希查找也叫散列查找，是利用哈希函數(shù)進(jìn)行查找的過程 ? 首先利用哈希函數(shù)及記錄的關(guān)鍵字計算出記錄的存儲地址 ? 然后直接到指定地址進(jìn)行查找 ? 不需要經(jīng)過比較，一次存取就能得到所查元素 ? 哈希沖突 ? 不同的記錄，其關(guān)鍵字通過哈希函數(shù)的計算，可能得到相同的地址 ? 把不同的記錄映射到同一個散列地址上，這種現(xiàn)象稱為沖突 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 946 哈希表 ? 哈希表定義 ? 根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的處理沖突的方法 ? 將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集上 ? 以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置 ? 如此構(gòu)造所得的查找表稱之為“哈希表”。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 951 哈希表 ? 數(shù)字分析法舉例 有 80個記錄，關(guān)鍵字為 8位十進(jìn)制數(shù)，哈希地址為 2位十進(jìn)制數(shù) 8 1 3 4 6 5 3 2