寫在前面：本文僅供個(gè)人學(xué)習(xí)使用。《大話數(shù)據(jù)結(jié)構(gòu)》通俗易懂，適合整體做筆記輸出，構(gòu)建體系。并且文中很多圖片來源于該書，如有侵權(quán)，請(qǐng)聯(lián)系刪除。

文章目錄

• • 8.1 開場白
  • 8.2 查找概論
  • 8.3 順序表查找
  • • 8.3.1 順序表查找算法
    • 8.3.2 順序表查找優(yōu)化
  • 8.4 有序表查找
  • • 8.4.1 折半查找
    • 8.4.2 插值查找
    • 8.4.3 斐波那契查找
  • 8.5 線性索引查找
  • • 8.5.1稠密索引
    • 8.5.2 分塊索引
    • 8.5.3倒排索引
  • 8.6 二叉排序樹
  • • 8.6.1 二叉排序樹查找操作
    • 8.6.2 二叉排序樹插入操作
    • 8.6.3 二叉排序樹刪除操作
    • 8.6.4 二叉排序樹總結(jié)
  • 8.7 平衡二叉樹(AVL樹)
  • • 8.7.1 平衡二叉樹實(shí)現(xiàn)原理
    • 8.7.2 平衡二叉樹實(shí)現(xiàn)算法
  • 8.8 多路查找樹(B樹)
  • • 8.8.1 2-3樹
    • • 2-3樹的插入實(shí)現(xiàn)
      • 2-3樹的刪除實(shí)現(xiàn)
    • 8.8.2 2-3-4樹
    • 8.8.3 B樹
    • 8.8.4 B+樹
  • 8.9 散列表（哈希表）查找概述
  • • 8.9.1 散列表查找定義
    • 8.9.2 散列表查找步驟
  • 8.10 散列函數(shù)的構(gòu)造方法
  • • 8.10.1 直接定址法
    • 8.10.2 數(shù)字分析法
    • 8.10.3 平方取中法
    • 8.10.4 折疊法
    • 8.10.5 除留余數(shù)法
    • 8.10.6 隨機(jī)數(shù)法
  • 8.11 處理散列沖突的方法
  • • 8.11.1 開放定址法
    • 8.11.2 再散列函數(shù)法
    • 8.11.3 鏈地址法
    • 8.11.4 公共溢出區(qū)法
  • 8.12 散列表查找實(shí)現(xiàn)
  • • 8.12.1 散列表查找算法實(shí)現(xiàn)
    • 8.12.2 散列表查找性能分析

8.1 開場白

相信在座的同學(xué)都用過搜索引擎。那么，你知道它的大概工作原理嗎？

當(dāng)你精心制作了一個(gè)網(wǎng)頁、或?qū)懥艘黄┛汀⒒蛘呱蟼髁艘唤M照片到互聯(lián)網(wǎng)上，來自世界各地的無數(shù)“蜘蛛”便會(huì)蜂擁而至。所謂蜘蛛就是搜索引擎公司服務(wù)器上的軟件，它如同蜘蛛一樣把互聯(lián)網(wǎng)當(dāng)成了蜘蛛網(wǎng)，沒日沒夜地訪問互聯(lián)網(wǎng)上的各種信息。

它抓取并復(fù)制你的網(wǎng)頁，且通過你網(wǎng)頁上的鏈接爬上更多的頁面，將所有信息納入到搜索引擎網(wǎng)站的索引數(shù)據(jù)庫。服務(wù)器拆解你網(wǎng)頁上的文字內(nèi)容、標(biāo)記關(guān)鍵詞的位置、字體、顏色，以及相關(guān)圖片、音頻、視頻的位置等信息，并生成龐大的索引記錄，如圖8-1-1所示。

當(dāng)你在搜索引擎上輸入一個(gè)單詞，點(diǎn)擊搜索時(shí)，它會(huì)在不到1秒內(nèi)，帶著單詞奔向索引數(shù)據(jù)庫的每個(gè)神經(jīng)末梢，檢索到所有包含搜索詞的網(wǎng)頁，依據(jù)它們的瀏覽次數(shù)與關(guān)聯(lián)性等一系列算法確定網(wǎng)頁級(jí)別，排列出順序，最終按你期望的格式呈現(xiàn)在網(wǎng)頁上。

這就是一個(gè)“關(guān)鍵詞”的云端之旅。過去的十多年，成就了本世紀(jì)最早期的創(chuàng)新明星Google，還有Yandex、Navar和百度等搜索引擎，搜索引擎已經(jīng)稱為人們最依賴的互聯(lián)網(wǎng)工具。

作為學(xué)習(xí)編程的人，面對(duì)查找或者叫做搜索這種最為頻繁的操作，理解它的原理并學(xué)習(xí)應(yīng)用它是非常必要的事情，讓我們對(duì)“Search”的探索之旅開始吧。

8.2 查找概論

只要你打開電腦，就會(huì)涉及到查找技術(shù)。如炒股軟件中查股票信息、硬盤文件中找照片等，所有這些需要被查的數(shù)據(jù)所在的集合，我們給它們一個(gè)統(tǒng)稱叫查找表。

查找表（search table）是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。例如圖8-2-1就是一個(gè)查找表。

關(guān)鍵字（key）是數(shù)據(jù)元素中某個(gè)數(shù)值項(xiàng)的值，又稱為鍵值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。也可以表示一個(gè)記錄的某個(gè)數(shù)據(jù)項(xiàng)（字段），我們稱為關(guān)鍵碼，如圖中的①和②所示。

若次關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)記錄，則稱此關(guān)鍵字為主關(guān)鍵字(Primary key).這也就意味著，對(duì)不同的記錄，其主關(guān)鍵字均不相同，主關(guān)鍵字所在的數(shù)據(jù)項(xiàng)稱為主關(guān)鍵碼，如圖③和④所示。

那么對(duì)于那些可以標(biāo)識(shí)多個(gè)數(shù)據(jù)元素（或記錄）的關(guān)鍵字，我們 稱為次關(guān)鍵字（Secondary key），如圖⑤所示。次關(guān)鍵字也可以理解為是不用以唯一識(shí)別一個(gè)數(shù)據(jù)元素（或記錄）的關(guān)鍵字。

查找（searching）就是根據(jù)給定的某個(gè)值，在查找表中確定其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。

若表中存在這樣的一個(gè)記錄，則稱查找是成功的，此時(shí)查找的結(jié)果給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置。比如圖8-2-1所示，如果我們查找主關(guān)鍵碼“代碼”的主關(guān)鍵字為“sh601398”的記錄時(shí)，就可以得到第2條唯一記錄。 如果我們查找次關(guān)鍵碼“漲跌幅”為“-0.11”的記錄時(shí)，就可以得到兩條記錄。

若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不成功，此時(shí)查找的結(jié)果可給出一個(gè)“空”記錄或“空”指針。

查找表按照操作方式來分有兩大種： 靜態(tài)查找表和動(dòng)態(tài)查找表。

靜態(tài)查找表（Static Search Table）：只作查找操作的查找表。
它的主要操作有： （1） 查找某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中。（2）檢索某個(gè)“特定的”數(shù)據(jù)元素和各種屬性。

動(dòng)態(tài)查找表（Dynamic Search Table）：在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已經(jīng)存在的某個(gè)數(shù)據(jù)元素。
它的操作就是兩個(gè)：（1） 查找時(shí)插入數(shù)據(jù)元素；（2）查找時(shí)刪除數(shù)據(jù)元素。

為了提高查找的效率，我們需要專門為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu)，這種面向查找操作的數(shù)據(jù)結(jié)構(gòu)稱為查找結(jié)構(gòu)。

從邏輯上來說，查找所基于的數(shù)據(jù)結(jié)構(gòu)是集合，集合中的記錄之間沒有本質(zhì)關(guān)系。可以要想獲得較高的查找性能，我們就不能不改變數(shù)據(jù)元素之間的關(guān)系，在存儲(chǔ)時(shí)可以將查找集合組織成表、樹等結(jié)構(gòu)。

例如，對(duì)于靜態(tài)查找表來說，我們不妨應(yīng)用線性表結(jié)構(gòu)來組織數(shù)據(jù)，這樣可以使用順序查找算法，如果再對(duì)主關(guān)鍵字排序，則可以應(yīng)用折半查找等技術(shù)進(jìn)行高效的查找。

如果是需要?jiǎng)討B(tài)查找，則會(huì)復(fù)雜一些，可以考慮二叉排序樹的查找技術(shù)。

另外，還可以利用散列表結(jié)構(gòu)來解決一些查找問題，這些技術(shù)都會(huì)在接下來一一介紹。

8.3 順序表查找

設(shè)想一下，要在散落的一大堆書中找到你需要的那本有多麻煩。碰到這種情況大多人都會(huì)考慮去做這樣一件事，那就是把這些書排列整齊，比如豎起來排到書架上，這樣根據(jù)書名，就很容易找到需要的圖書，如圖8-3-1所示。

散落的圖書可以理解為一個(gè)集合，而將它們排列整齊，就如同是將此集合構(gòu)造成一個(gè)線性表，我們要針對(duì)這一線性表進(jìn)行查找操作，因此它就是靜態(tài)查找表。

順序查找（Sequntial Search） 又叫線性查找，是最基本的查找技術(shù)，它的查找過程是：從表中第一個(gè)（或最后一個(gè)）記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值比較，如某個(gè)記錄的關(guān)鍵字和給定值相等，則查找成功，找到所查的記錄；如果直到最后一個(gè)（或第一個(gè)）記錄，其關(guān)鍵字和給定值比較時(shí)都不等，則表中沒有所查的記錄，查找不成功。

8.3.1 順序表查找算法

/* 無哨兵順序查找，a為數(shù)組，n為要查找的數(shù)組個(gè)數(shù)，key為要查找的關(guān)鍵字 */ int Sequential_Search(int *a,int n,int key) {int i;for(i=1;i<=n;i++){if (a[i]==key) return i;}return 0; }

這段代碼非常簡單，就是在數(shù)組a（注意元素值從下標(biāo)1開始）中查看有沒有關(guān)鍵字，當(dāng)你需要查找復(fù)雜表結(jié)構(gòu)的記錄時(shí)，只需要把數(shù)組a與關(guān)鍵字key定義成你需要的表結(jié)構(gòu)和數(shù)據(jù)類型即可。

8.3.2 順序表查找優(yōu)化

到這里并非完美，因?yàn)槊看窝h(huán)時(shí)都需要對(duì)i是否越界，即是否小于等于n做判斷。事實(shí)上，還可以有更好一點(diǎn)的辦法，設(shè)置一個(gè)哨兵，可以解決不需要每次讓i和n作比較。看下面的改進(jìn)后的順序查找算法代碼

/* 有哨兵順序查找 */ int Sequential_Search2(int *a,int n,int key) {int i;a[0]=key;// 設(shè)置a[0]為關(guān)鍵字值，我們稱之為”哨兵“i=n;循環(huán)從數(shù)組尾部開始while(a[i]!=key){i--;}return i;//返回0則表示查找失敗 }

此時(shí)代碼時(shí)從尾部開始查找，由于a[0]=key,也就是說，如果在a[i] 中有key 則返回i值，查找成功；否則一定時(shí)最終a[0]處等于key值，此時(shí)返回的是0，即說明查找失敗。

這種在查找方向的盡頭放置”哨兵“免去了在查找過程中每一次比較后都要判斷查找位置是否越界的小技巧，看似與原先差別不大，但在總數(shù)據(jù)量較多時(shí)，效率提高很大，是非常好的編碼技巧。 當(dāng)然,"哨兵"也不一定非要出現(xiàn)在數(shù)組開始，也可以在末端。

對(duì)于這種順序查找算法來說，查找成功最好的情況是在第一個(gè)位置就找到，算法上的時(shí)間復(fù)雜度為O(1)，最壞的情況則是在最后一個(gè)位置找到，最壞時(shí)間復(fù)雜度是O(n),我們之間推導(dǎo)過，關(guān)鍵字在任何一個(gè)位置的概率是相同的，所以平均查找次數(shù)是n(n+1)/2,最終的時(shí)間復(fù)雜度為O(n).

很顯然，順序查找計(jì)數(shù)是有很大缺點(diǎn)的，n很大時(shí)，查找效率極為低下，不過優(yōu)點(diǎn)也是有的，這個(gè)算法非常簡單，對(duì)靜態(tài)查找表的記錄沒有任何要求，在一些小型數(shù)據(jù)的查找時(shí)，是可以適用的。

另外，也正由于查找概率的不同，我們完全可以將容易查找的記錄放在前面，而不常用的記錄放置在后面，效率就可以大幅提高。

8.4 有序表查找

一個(gè)線性表有序時(shí)，對(duì)于查找總是有幫助的。

8.4.1 折半查找

折半查找（Binary Search）技術(shù)，又稱為二分查找。它的前提是線性表中的記錄必須是關(guān)鍵碼有序（通常從小到大有序），線性表必須采用順序存儲(chǔ)。折半查找的基本思想是:在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵字相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所有查找區(qū)域無記錄，查找失敗為止。

/* 折半查找 */ int Binary_Search(int *a,int n,int key) {int low,high,mid;low=1; /* 定義最低下標(biāo)為記錄首位 */high=n; /* 定義最高下標(biāo)為記錄末位 */while(low<=high){mid=(low+high)/2; /* 折半 */if (key<a[mid]) /* 若查找值比中值小 */high=mid-1; /* 最高下標(biāo)調(diào)整到中位下標(biāo)小一位 */else if (key>a[mid])/* 若查找值比中值大 */low=mid+1; /* 最低下標(biāo)調(diào)整到中位下標(biāo)大一位 */else{return mid; /* 若相等則說明mid即為查找到的位置 */}}return 0; }

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為$?lo{g}_{2}n?+1$,在這里盡管折半查找判定二叉樹并不是完全二叉樹，但同樣的推導(dǎo)可以得出，最壞情況是查找到關(guān)鍵字或查找失敗的次數(shù)是$?lo{g}_{2}n?+1$
最好情況呢?當(dāng)然是1次了。

因此最終我們折半查找的時(shí)間復(fù)雜度為$O(logn)$，它顯然遠(yuǎn)遠(yuǎn)好于順序查找的O(n)復(fù)雜度了。

不過由于折半查找的前提條件是需要有序表順序存儲(chǔ)，對(duì)于靜態(tài)查找表，一次排序后不再變化，這樣的算法已經(jīng)比較好了。但對(duì)于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來說，維護(hù)有序的排序會(huì)帶來不小的工作量，那就不建議使用。

8.4.2 插值查找

現(xiàn)在我們的問題是，為什么一定要折半，而不是折四分之一或者折更多呢？

打個(gè)比方，在英文詞典中查找apple這個(gè)單詞，你下意識(shí)翻開詞典的前面還是后面？如果再讓你查zoo這個(gè)單詞呢？ 很顯然，這里你絕對(duì)不會(huì)是從中間開始查起，而是有一定目的的往前或往后翻。

同樣的，比如要在取值=~10000之間 共有100個(gè)元素從小到大均勻分布的數(shù)組中查找5，我們自然會(huì)考慮從數(shù)組下標(biāo)較小的開始查找。

看來，我們的折半查找，還是有改進(jìn)空間的。

折半查找mid= (low+high)/2 = low+(high-low)/2

算法科學(xué)家們考慮的就是將這個(gè)1/2進(jìn)行改進(jìn)，改進(jìn)為下面的計(jì)算方案：

$$mid=low+\frac{key?a[low]}{a[high]?a[low]}(high?low)$$

將1/2改成$\frac{key?a[low]}{a[high]?a[low]}$有什么道理嗎?

假設(shè) a[11]={0,1,16,24,35,47,59,62,73,88,99},low=1,high=10,則 a[low]=1,a[high]=99,如果我們要查找的是key=16時(shí)，按照原來折半的做法，我們需要4次（如圖8-4-6）才可以得到結(jié)果。

但如果用新方法，$\frac{key+a[low]}{a[high]?a[low]}=(16?1)/(99?1)=0.153$,即mid= 1+0.153*(10-1)=2.377，取整得到mid=2，我們只需要兩次就查找到結(jié)果了，顯然大大提高了查找的效率。

換句話說，我們只需要在折半查找算法的代碼中更改一行代碼便可以得到插值查找的代碼

/* 插值查找 */ int Interpolation_Search(int *a,int n,int key) {int low,high,mid;low=1; /* 定義最低下標(biāo)為記錄首位 */high=n; /* 定義最高下標(biāo)為記錄末位 */while(low<=high){mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */if (key<a[mid]) /* 若查找值比插值小 */high=mid-1; /* 最高下標(biāo)調(diào)整到插值下標(biāo)小一位 */else if (key>a[mid])/* 若查找值比插值大 */low=mid+1; /* 最低下標(biāo)調(diào)整到插值下標(biāo)大一位 */elsereturn mid; /* 若相等則說明mid即為查找到的位置 */}return 0; }

插值查找（Interpolation Search）是根據(jù)要查找的關(guān)鍵字key與查找表中最大最小記錄的關(guān)鍵字比較后的查找方法，其核心在于插值的計(jì)算公式$\frac{key?a[low]}{a[high]?a[low]}$。 應(yīng)該說，從時(shí)間復(fù)雜度來看，它就是O(logn),但對(duì)于表長較大，而關(guān)鍵字分布又比較均勻的查找表來說，差值查找算法的平均性能比折半查找要好得多。反之，數(shù)組中如果分布類似{0,1,2,2000,2001,…,99999919,99999999} 這種極端不平均的數(shù)據(jù)，用插值查找未必是合適的算法。

8.4.3 斐波那契查找

還有沒有其他辦法？ 我們折半查找是從中間分，也就是說，每一次查找總是一分為二，無論數(shù)據(jù)是偏大還是偏小，很多時(shí)候這都未必是最合理的做法。除了插值查找外，我們?cè)俳榻B一種有序查找，斐波那契查找(Fibonacci Search)，它是利用黃金分割的原理來實(shí)現(xiàn)的。

為了能夠介紹清楚這個(gè)查找算法，我們先需要有一個(gè)斐波那契數(shù)列的數(shù)組，如圖8-4-8所示。

下面我們根據(jù)代碼來看程序是如何運(yùn)行的

/* 斐波那契查找 */ int Fibonacci_Search(int *a,int n,int key) {int low,high,mid,i,k=0;low=1; /* 定義最低下標(biāo)為記錄首位 */high=n; /* 定義最高下標(biāo)為記錄末位 */while(n>F[k]-1)k++;for (i=n;i<F[k]-1;i++)a[i]=a[n];while(low<=high){mid=low+F[k-1]-1;if (key<a[mid]){high=mid-1; k=k-1;}else if (key>a[mid]){low=mid+1; k=k-2;}else{if (mid<=n)return mid; /* 若相等則說明mid即為查找到的位置 */else return n;}}return 0; }

1 程序開始運(yùn)行，參數(shù) a[11]={0,1,16,24,35,47,59,62,73,88,99}, n=10,要查找的關(guān)鍵字key=59。注意此時(shí)我們已經(jīng)有了事先計(jì)算好的全局變量數(shù)組F 的具體數(shù)據(jù)，它是斐波那契數(shù)列， F={0,1,1,2,3,5,8,13,21,…}

2 第6-8行是計(jì)算當(dāng)前的n處于斐波那契數(shù)列的位置。現(xiàn)在是n=10，F[6]<10<F[7],，所以計(jì)算出來k=7。

3 第9~10行，由于k=7，計(jì)算時(shí)是以F[7]=13為基礎(chǔ)，而a中最大的僅是a[10],后面的a[11],a[12]均未賦值， 這不能構(gòu)成有序序列，因此將它們都賦值為最大的數(shù)組值，所以此時(shí)a[11]=a[12]=a[10]=99(此段代碼后面有解釋)。

4第11~31行查找正式開始。

5 第13行，mid=1+F[7-1]-1=8,也就是說，我們第一個(gè)要對(duì)比的數(shù)值是從下標(biāo)為8開始的。

6 由于此時(shí)key=59而a[8]=73,因此執(zhí)行第16~17行 得到high=7，k=6.

7再次循環(huán)，mid=low+F[k-1]-1 =1+F[6-1]-1=5, 此時(shí)a[5]=47<key,因此執(zhí)行19~23行代碼，得到low=mid+1=6，k=k-2=4 ，注意此時(shí)k下調(diào)2個(gè)單位。

8 再次循環(huán)，mid=low+F[k-1]-1 =6+F[4-1]-1=7, 此時(shí)a[7]=62>key,因此執(zhí)行14~18行代碼，得到high=mid-1=6，k=k-1=3 .

9再次循環(huán)， mid=low+F[k-1]-1 =6+F[3-1]-1=6, 此時(shí)a[6]=59=key，因此執(zhí)行代碼第26~27行，返回值為6. 程序運(yùn)行結(jié)束。

如果key=99，此時(shí)查找循環(huán)第一次時(shí)，mid=8與上例是相同的，第二次循環(huán)時(shí)，mid=11，如果a[11]沒有值（a中最大的僅是a[10],后面的a[11],a[12]均未賦值， 這不能構(gòu)成有序序列）就會(huì)使得與key的比較失敗，為了避免這樣的情況出現(xiàn)，第9~10行的代碼就起到了這樣的作用。

斐波那契查找算法的核心在于：
1） 當(dāng) key=a[mid]時(shí)，查找就成功；
2）當(dāng)key<a[mid]時(shí)，新范圍是 第low個(gè)到第mid-1個(gè)，此時(shí)范圍個(gè)數(shù)為F[k-1]-1個(gè)。
3） 當(dāng)key>a[mid]時(shí)，新范圍時(shí)第m+1個(gè)到第high個(gè)，此時(shí)范圍個(gè)數(shù)是F[k-2]-1個(gè)。

也就是說，如果要查找的記錄在右側(cè)，則左側(cè)的數(shù)據(jù)偶讀不用再判斷了，不斷反復(fù)進(jìn)行下去，對(duì)處于當(dāng)中的大部分?jǐn)?shù)據(jù)，其工作效率要高一些。所以盡管斐波那契查找的時(shí)間復(fù)雜度也為O(logn)，但就平均性能而言，斐波那契查找要由于折半查找。可惜如果是最壞情況，比如這里key=1，那么始終都處于左側(cè)長半?yún)^(qū)在查找，則查找效率要低于折半查找。

還有比較關(guān)鍵的一點(diǎn)，折半查找是進(jìn)行加法與除法運(yùn)算（mid=(low+high)/2;），插值查找進(jìn)行復(fù)雜的四則運(yùn)算（$mid=low+\frac{key?a[low]}{a[high]?a[low]}(high?low)$），而斐波那契查找只是最簡單的加減法運(yùn)算（mid=low+F[k-1]-1），在海量數(shù)據(jù)的查找過程中，這種細(xì)微的差別可能會(huì)影響最終的查找效率。

應(yīng)該說，三種有序表的查找本質(zhì)上是分隔點(diǎn)的選擇不同，各有優(yōu)劣，實(shí)際開發(fā)時(shí)可根據(jù)數(shù)據(jù)的特點(diǎn)綜合考慮再做出選擇。

8.5 線性索引查找

我們前面講的幾種比較高效的查找方法都是在有序的基礎(chǔ)上進(jìn)行操作的，但事實(shí)上，很多數(shù)據(jù)集可能增長非常快，例如，某些微博網(wǎng)站或大型論壇的帖子和回復(fù)數(shù)每天都是成百萬上千萬條，如圖8-5-1所示，或者一些服務(wù)器日志信息記錄也是海量數(shù)據(jù)，要保證記錄全部時(shí)按照當(dāng)中的某個(gè)關(guān)鍵字有序，其時(shí)間代價(jià)是非常高昂的，所以這種數(shù)據(jù)結(jié)構(gòu)通常都是按先后順序存儲(chǔ)。

那么，對(duì)于這樣的查找表，我們?nèi)绾文軌蚩焖俨檎业叫枰臄?shù)據(jù)呢？ 辦法就是-----索引。

數(shù)據(jù)結(jié)構(gòu)的最終目的是提高數(shù)據(jù)的處理速度，索引是為了加快查找速度而設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)。索引就是把一個(gè)關(guān)鍵字與它對(duì)應(yīng)的記錄相關(guān)聯(lián)的過程，一個(gè)索引由若干個(gè)索引項(xiàng)構(gòu)成，每個(gè)索引項(xiàng)至少應(yīng)包含關(guān)鍵字和其對(duì)應(yīng)的記錄在存儲(chǔ)器中的位置等信息。索引技術(shù)是組織大型數(shù)據(jù)庫以及磁盤文件的一種重要技術(shù)。

索引按照結(jié)構(gòu)可以分為線性索引、樹形索引和多級(jí)索引。我們這里就只介紹線性索引技術(shù)。所謂線性索引就是將索引項(xiàng)集合組織為線性結(jié)構(gòu)，也稱為索引表。我們重點(diǎn)介紹三種線性索引:稠密索引、分塊索引和倒排索引。

8.5.1稠密索引

稠密索引是指在線性索引中，將數(shù)據(jù)集中的每個(gè)記錄對(duì)應(yīng)一個(gè)索引項(xiàng)。如圖8-5-2所示。

稠密索引要對(duì)應(yīng)的可能是成千上萬的數(shù)據(jù)，因此，對(duì)于稠密索引這個(gè)索引表來說，索引項(xiàng)一定是按照關(guān)鍵碼有序的排列。

索引表有序也就意味著，我們要查找關(guān)鍵字時(shí)，可以用到折半、插值、斐波那契等有序查找方法，大大提高了效率。 比如圖8-5-2中，我要查找關(guān)鍵字是18的記錄，如果從右側(cè)的數(shù)據(jù)表中查找，那就只能順序查找，需要查找6次才可以查到結(jié)果。 而如果是從左邊的索引表中查找，只需兩次折半查找就可以得到18對(duì)應(yīng)的指針，最終查到結(jié)果。

這顯然是稠密索引的優(yōu)點(diǎn)，但是如果數(shù)據(jù)集非常大，比如上億，那也就意味著索引也得同樣的數(shù)據(jù)集長度規(guī)模，對(duì)于內(nèi)存有限的計(jì)算機(jī)來說，可能就需要反復(fù)去訪問磁盤，查找性能反而大大下降了。

8.5.2 分塊索引

回想一下圖書館是如何藏書的。顯然它不會(huì)是順序擺放的，給我們一個(gè)稠密索引表去查，然后再找到書給你。圖書館的圖書分類擺放是有完整的學(xué)科體系的，而它最重要的一個(gè)特點(diǎn)就是分塊。

稠密索引因?yàn)樗饕?xiàng)與數(shù)據(jù)集的記錄個(gè)數(shù)相同，所以空間代價(jià)很大。為了減少索引項(xiàng)的個(gè)數(shù)，我們可以對(duì)數(shù)據(jù)集進(jìn)行分塊，使其分塊有序，然后再對(duì)每一塊建立一個(gè)索引項(xiàng)，從而減少索引項(xiàng)的個(gè)數(shù)。

分塊有序，是把數(shù)據(jù)集的記錄分成了若干塊，并且這些塊需要滿足兩個(gè)條件：

• 塊內(nèi)無序，即每一塊內(nèi)的記錄不要求有序。當(dāng)然，你如果能夠讓塊內(nèi)有序?qū)Σ檎襾碚f更理想，不過這就要付出大量時(shí)間和空間的代價(jià)，因此通常我們不要求塊內(nèi)有序。
• 塊間有序，例如，要求第二塊所有記錄的關(guān)鍵字均要大于第一塊中所有記錄的關(guān)鍵字，第三塊的所有記錄的關(guān)鍵字均要大于第二塊的所有記錄關(guān)鍵字…,因?yàn)橹挥袎K間有序，才有可能在查找時(shí)帶來效率。

對(duì)于分塊有序的數(shù)據(jù)集，將每塊對(duì)應(yīng)一個(gè)索引項(xiàng)，這種索引方法稱為分塊索引。如圖8-5-4所示，我們定義的分塊索引的索引項(xiàng)結(jié)構(gòu)分三個(gè)數(shù)據(jù)項(xiàng):

• 最大關(guān)鍵碼，它存儲(chǔ)每一塊中最大的關(guān)鍵字，這樣的好處是可以使得在它之后的下一塊中的最小關(guān)鍵字也能比這一塊最大的關(guān)鍵字還要大。
• 存儲(chǔ)了塊中的記錄個(gè)數(shù)，以便于循環(huán)時(shí)使用。
• 用于指向塊首數(shù)據(jù)元素的指針，便于開始對(duì)這一塊中記錄進(jìn)行遍歷。

在分塊索引表中查找，就是分兩步進(jìn)行：

在分塊索引表中查找待查關(guān)鍵字所在的塊。由于分塊索引表是塊間有序的，因此很容易利用折半、插值等算法得到結(jié)果。例如，如圖8-5-4的數(shù)據(jù)集中查找62，我們可以很快從左上角的索引表中由57<62>96 得到62在第三個(gè)塊中。

根據(jù)塊首指針找到對(duì)應(yīng)的塊，并在塊中順序查找關(guān)鍵碼。因?yàn)閴K中可以是無序的，因此只能順序查找。

應(yīng)該說，分塊索引的思想是很容易理解的，我們通常在整理書架時(shí)，都會(huì)考慮不同的層板放置不同類別的圖書。例如，我家里就是最上層方不太常看的小說，中間層放計(jì)算機(jī)相關(guān)的專業(yè)書，這就是分塊的概念，并且讓它們塊間有序了。 只至于上層是《紅樓夢(mèng)》在《三國演義》的左邊還是有邊，并不是很重要。 畢竟要找小說《紅樓夢(mèng)》，只需要對(duì)這一層的書用眼睛掃一遍即可。

我們?cè)賮矸治鲆幌路謮K索引的平均查找長度。設(shè)n個(gè)記錄的數(shù)據(jù)集被平均分為m塊，每個(gè)塊中有t條記錄，顯然 n=m*t. 再假設(shè) Lb 為查找索引表的平均查找長度，因最好與最差的等概率原則，所以Lb的平均長度為 (m+1)/2,Lw為塊中查找記錄的平均查找長度，同理可以知道它的平均查找長度為(t+1)/2.

這樣分塊索引查找的平均查找長度為:

注意這個(gè)式子的推導(dǎo)是為了讓整個(gè)分塊索引查找長度依賴于n和t兩個(gè)變量。從這里我們也就得到，平均長度不僅僅取決于數(shù)據(jù)集的總記錄數(shù)n，還和每一個(gè)塊的記錄個(gè)數(shù)t相關(guān)。最佳的情況就是分的塊數(shù)m與塊中的記錄數(shù)t相同，此時(shí)意味著 $n=m?t=t^2$,即

可見，分塊索引的效率比順序查找的O(n)是高了不少，不過它顯然與折半查找的O(logn)相比還有不小的差距。 因此再去欸的那個(gè)所在塊的過程中，由于塊間有序，所以可以應(yīng)用折半、插值等手段來提高效率。

總的來說，分塊索引在兼顧了對(duì)細(xì)分塊不需要有序的情況下，大大增加了整體查找的速度，所以普遍被用于數(shù)據(jù)庫表查找等技術(shù)的應(yīng)用當(dāng)中。

8.5.3倒排索引

我不知道大家有沒有對(duì)搜索引擎好奇過，無論你查找什么樣的信息，它都可以在極短的時(shí)間內(nèi)給你一些結(jié)果，如圖8-5-5所示。是什么算法技術(shù)得到這樣的高效查找呢？

我們?cè)谶@里介紹最簡單的，也算是最基礎(chǔ)的搜索技術(shù)—倒排索引。

我們來看樣例，現(xiàn)在有兩篇極短的英文文章—其實(shí)只能算是英文句子，我們暫時(shí)認(rèn)為它是文章，編號(hào)分別是1和2.

假設(shè)我們忽略掉“books” “friends”中的復(fù)數(shù)s，以及大小寫差異，我們可以整理出這樣的一張單詞表，如表8-5-1所示，并將單詞做了排序，也就是表格顯示了每個(gè)不同的單詞分別出現(xiàn)在哪篇文章中，比如“good”出現(xiàn)在兩篇文章中，而“is”只是在文章2中出現(xiàn)。

有了這樣一張單詞表，我們要搜索文章，就非常方便了。如果你在搜索框中填寫book關(guān)鍵字。系統(tǒng)就先在這張單詞表中有序查找“book”，找到后將它對(duì)應(yīng)的文章編號(hào)1和2的文章地址（通常在搜索引擎中就是網(wǎng)頁的標(biāo)題和鏈接）返回，并告訴你，查找到兩條記錄，用時(shí)0.0001秒。由于單詞表是有序的，查找效率很高，返回的又只是文章的編號(hào)，所以整體速度會(huì)非常快。

如果沒有這張單詞表，為了能證實(shí)所有的文章中有沒有沒有關(guān)鍵字book，則需要對(duì)每一篇文章每一個(gè)單詞順序查找。在文章數(shù)是海量的情況下，這樣的做法只存在理論上的可行性，現(xiàn)實(shí)中沒有人愿意使用它。

在這里這張單詞表就是索引表，索引項(xiàng)的通用結(jié)構(gòu)是：

• 次關(guān)鍵碼，例如上面的英文單詞；
• 記錄號(hào)表，例如上面的文章編號(hào)。

其中記錄號(hào)表存儲(chǔ)具有相同次關(guān)鍵字的所有記錄的記錄號(hào)（可以是指向記錄的指針或者是該記錄的主關(guān)鍵字）。這樣的索引方法就是倒排索引（Inverted index）. 倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性（或字段、次關(guān)鍵碼）的值來查找記錄。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引。

倒排索引的好處顯然就是查找記錄非常快，基本等于生成索引表后，查找時(shí)都不用去讀取記錄，就可以得到結(jié)果。但是它的缺點(diǎn)是這個(gè)記錄號(hào)不定長，比如上例中有7個(gè)單詞的文章編號(hào)只有一個(gè)，而book ，good 等單詞有兩個(gè)文章編號(hào)，若是對(duì)多篇文章所有單詞建立倒排索引，那每個(gè)單詞都將對(duì)應(yīng)相當(dāng)多的文章編號(hào)，維護(hù)比較困難，插入和刪除操作都需要做相應(yīng)的處理。

當(dāng)然，現(xiàn)實(shí)中的搜索技術(shù)非常復(fù)雜，這里只介紹了最簡單的思想。

8.6 二叉排序樹

假設(shè)查找的數(shù)據(jù)集是普通的順序存儲(chǔ)，那么插入操作就是將記錄放在表的末端，給表記錄數(shù)加一即可，刪除操作可以是刪除后，后面的記錄向前移，也可以是要?jiǎng)h除的元素與最后一個(gè)元素互換，表記錄數(shù)減一，反正整個(gè)數(shù)據(jù)集也沒有什么順序，這樣的效率也不錯(cuò)。應(yīng)該說，插入和刪除對(duì)于順序存儲(chǔ)結(jié)構(gòu)來說，效率是可以接受的，但這樣的表由于無序造成查找的效率低下。

如果查找的數(shù)據(jù)集是有序線性表，并且是順序存儲(chǔ)的，查找可以用折半、插值、斐波那契等查找算法來實(shí)現(xiàn)，可惜，因?yàn)橛行?#xff0c;在插入和刪除操作上，就需要耗費(fèi)大量的時(shí)間。

有沒有一種既可以使得插入和刪除效果不錯(cuò)，又可以比較高效率地實(shí)現(xiàn)查找的算法呢？ 還真有。

我們?cè)?.2 節(jié)把這種需要在查找時(shí)插入或刪除的查找表稱為動(dòng)態(tài)查找表。我們現(xiàn)在就來看看什么樣的結(jié)構(gòu)可以實(shí)現(xiàn)動(dòng)態(tài)查找表的高效率。

如果在復(fù)雜的問題面前，我們束手無策的話，不妨先從最簡單的情況入手。現(xiàn)在我們的目標(biāo)是插入和查找同樣高效。假設(shè)我們的數(shù)據(jù)集開始只有一個(gè)數(shù){62},然后仙子啊需要將88插入數(shù)據(jù)集，于是數(shù)據(jù)集成了{(lán)62,88},還保持著從小到大有序。再查找有沒有58，沒有則插入，可此時(shí)要想在線性表的順序存儲(chǔ)中有序，就得移動(dòng)62和88的位置，如圖8-6-2的左圖，可不可以不移動(dòng)呢？

嗯，當(dāng)然是可以，那就是二叉樹結(jié)構(gòu)。當(dāng)我們用二叉樹的方式時(shí)，首先我們將第一個(gè)數(shù)62定為根結(jié)點(diǎn)，88因?yàn)楸?2大，因此讓它作為62的右子樹，58因比62小，所以成為它的左子樹。此時(shí)58的插入并沒有影響到62和88的關(guān)系，如上圖右圖所示。

也就是說，若我們現(xiàn)在需要對(duì)集合{62,88,58,47,35,73,51,99,37,93}做查找，在我們打算創(chuàng)建此集合時(shí)就考慮用二叉樹結(jié)構(gòu)，而且是排好序的二叉樹來創(chuàng)建。 如圖8-6-3所示，62，58，88創(chuàng)建好后，下一個(gè)數(shù)47因?yàn)楸?8小，是它的左子樹（見③），35是47的左子樹（見④)，73比62大，但卻比88小，是88的左子樹（見⑤），51比62小，比58小，比47大，是47的右子樹（見⑥），99比62大，比88大，是88的右子樹（見⑦），37比62、58、、47都小，但是比35大，所以37是35的右子樹（見⑧），93則比62、88大，比99小，所以98是99的左子樹（見⑨）。

這樣我們就得到了一棵二叉樹，并且當(dāng)我們對(duì)它進(jìn)行中序遍歷時(shí)，就可以得到一個(gè)有序的序列{35,37,47,51,58,62,73,88,93,99},所以我們通常稱它為二叉排序樹。

二叉排序樹(Binary Sort Tree) ，又稱二叉查找樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

• 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
• 若它的右子樹不空，則柚子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
• 它的左右子樹也分別為二叉排序樹。

從二叉排序樹的定義也可以知道，它前提是二叉樹，然后它采用了遞歸的定義方式，再者，它的結(jié)點(diǎn)間滿足一定的次序關(guān)系，左子樹結(jié)點(diǎn)一定比其雙親結(jié)點(diǎn)小，右子樹結(jié)點(diǎn)一定比其雙親結(jié)點(diǎn)大。

構(gòu)造一棵二叉排序樹的目的，其實(shí)并不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度。不管怎么說，在一個(gè)有序數(shù)據(jù)集上的查找，速度總是要快于無序的數(shù)據(jù)集的，而二叉排序樹這種非線性結(jié)構(gòu)，也有利于插入和刪除的實(shí)現(xiàn)。

8.6.1 二叉排序樹查找操作

首先我們提供一個(gè)二叉樹的結(jié)構(gòu)

//二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義tydedef struct BiTNode{ //結(jié)點(diǎn)結(jié)構(gòu)int data; // 結(jié)點(diǎn)數(shù)據(jù)struct BiTNode *lchild, *rchild;// 左右孩子指針} BiTNode, *BiTree;

然后我們來看看二叉排序樹的查找是如何實(shí)現(xiàn)的

//遞歸查找二叉排序樹T中是否存在key //指針f指向T的雙親，其初始調(diào)用值為NULL //若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE //否則指針p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)并返回FALSEStatus SearchBST(BiTree T, int key , BiTree f, BiTree *p){if(!T){*p=f;return FALSE;}else if(key==T->data){*p=T;return TRUE;}else if(key<T->data){return SearchBST(T->lchild,key,T,p);//在左子樹繼續(xù)查找}else return SearchBST(T->rchild,key ,T ,p);//在右子樹繼續(xù)查找}

1 SearchBST 函數(shù)是一個(gè)可遞歸運(yùn)行的函數(shù)，函數(shù)調(diào)用時(shí)的語句為 SearchBST(T,93,NULL,p);參數(shù)T是一個(gè)二叉鏈表，其中數(shù)據(jù)如圖8-6-3所示，key代表要查找的關(guān)鍵字，目前我們打算查找93，二叉樹f指向T的雙親，當(dāng)T指向根結(jié)點(diǎn)時(shí)，f的初值就為NULL，它在遞歸時(shí)有用，最后的參數(shù)p時(shí)為了查找成功后可以得到查找到的結(jié)點(diǎn)位置。

下面復(fù)習(xí)一下二叉鏈表

二叉樹每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表為二叉鏈表。結(jié)點(diǎn)結(jié)構(gòu)圖如下所示

其中data為數(shù)據(jù)域，lchild和rchild都是指針域，分別存放指向左孩子和右孩子的指針。

以下是我們的二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義代碼。

typedef struct BiTNode{TElemType data; //結(jié)點(diǎn)數(shù)據(jù)struct BiTNode *lchild ,*rchild;//左右孩子指針 }BiTNode, *BiTree;

結(jié)構(gòu)示意圖如下圖所示

下面繼續(xù)二叉排序樹的查找

2 第3~7行，是用來判斷當(dāng)前二叉樹是否到葉子結(jié)點(diǎn)，顯然圖8-6-3告訴我們當(dāng)前T指向根結(jié)點(diǎn)62的位置，T不為空，第5 ~ 6行不執(zhí)行。

3 第8~12行是查找到相匹配的關(guān)鍵字時(shí)執(zhí)行語句，顯然93≠62，第10 ~11行不執(zhí)行。

4 第13~14行是當(dāng)要查找的關(guān)鍵字小于當(dāng)前結(jié)點(diǎn)值時(shí)執(zhí)行，由于93＞62，第14行不執(zhí)行。

5 第15~16行時(shí)當(dāng)要查找的關(guān)鍵字大于當(dāng)前結(jié)點(diǎn)值時(shí)執(zhí)行，由于93＞62，所以遞歸調(diào)用SearchBST(T->rchild,key,T,p); 此時(shí)T指向了62的右孩子88，如圖8-6-4所示。

6 此時(shí)第二層SearchBST，因93比88大，所以執(zhí)行第16行，再次遞歸調(diào)用SearchBST(T->rchild,key,T,p); 此時(shí)T指向了88的右孩子99，如圖8-6-5所示。

7 第三層的SearchBST，因93小于99，所以執(zhí)行第14行，遞歸調(diào)用SearchBST(T->lchild,key,T,p); 此時(shí)T指向了99的左孩子93，如圖8-6-6所示。

8 第四層 SearchBST，因?yàn)閗ey==T->data，所以執(zhí)行10~11行，此時(shí)指針p指向93所在的結(jié)點(diǎn)，并返回TRUE到第三層、第二層、第一層，最終函數(shù)返回TRUE.

8.6.2 二叉排序樹插入操作

看了二叉排序樹的查找函數(shù)，那么所謂的二叉排序樹的插入，其實(shí)也就是將關(guān)鍵字放到樹中合適的位置而已，來看代碼。

//當(dāng)二叉排序樹T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)， //插入key并返回TRUE,否則返回FALSEStatus InsertBST(BiTree *T, int key){BiTree p,s;if( !SearchBST( *T, key ,NULL, &p)){ //查找不成功：p返回不成功最后訪問的結(jié)點(diǎn)位置s=(BiTree) malloc(sizeof(BiTNode));s->data=key; //值key賦值s結(jié)點(diǎn)s->lchild=s->rchild=NULL;//葉子結(jié)點(diǎn)if(!p){//空的*T=s; // 插入s為新的根結(jié)點(diǎn)}else if(key<p->data)p->lchild=s;//插入s為左孩子else p->rchild=s;//插入s為右孩子return TRUE;}else return FALSE;// 樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入}

這段代碼非常簡單。如果你調(diào)用函數(shù) InsertBST(T,93) 那么結(jié)果就是FALSE ，如果是InsertBST(T,95)，那么一定就是在93結(jié)點(diǎn)增加一個(gè)右孩子95，并且返回TRUE。如圖8-6-7所示。

有了二叉排序樹的插入代碼，我們要實(shí)現(xiàn)二叉排序樹的構(gòu)建就非常容易了。下面的代碼可以構(gòu)建如圖8-6-3的一棵樹。

int i;int a[10]={62,88,58,47,35,73,51,99,37,93};BiTree T=NULL;for(i=0;i<10;i++){InsertBST(&T, a[i]);}

8.6.3 二叉排序樹刪除操作

俗話說“請(qǐng)神容易送神難”，我們已經(jīng)介紹了二叉排序樹的查找和插入算法，但是對(duì)于二叉排序樹的刪除，就不是那么容易，我們不能因?yàn)閯h除了結(jié)點(diǎn)，而讓這棵樹變得不滿足二叉排序樹的特性，所以刪除需要考慮多種情況。

如果需要查找并刪除 如37、51、73、93這些在二叉排序樹中是葉子的結(jié)點(diǎn)，那是很容易的，畢竟刪除它們對(duì)整棵樹來說，其他結(jié)點(diǎn)的結(jié)構(gòu)并未受到影響，如圖8-6-8所示。

對(duì)于要?jiǎng)h除的結(jié)點(diǎn)只有左子樹或者右子樹的情況，相對(duì)也比較好處理。 那就是結(jié)點(diǎn)刪除后，將它的左子樹或右子樹移動(dòng)到刪除結(jié)點(diǎn)的位置即可，可以理解為獨(dú)子繼承家業(yè)。比如圖8-6-9，就是先刪除35和99結(jié)點(diǎn)，再刪除58結(jié)點(diǎn)的變化圖，最終，這個(gè)結(jié)構(gòu)還是一個(gè)二叉排序樹。

但是對(duì)于要?jiǎng)h除的結(jié)點(diǎn)既有左子樹又有右子樹的情況怎么辦呢？ 比如圖8-6-10中的結(jié)點(diǎn)47 若要?jiǎng)h除了，它的兩個(gè)兒子以及子孫們?cè)趺崔k呢？（這里增加了結(jié)點(diǎn)47下的子孫結(jié)點(diǎn)數(shù)量）

起初的想法，我們當(dāng)結(jié)點(diǎn)47只有一個(gè)左子樹，那么做法和一個(gè)左子樹的操作一樣，讓35以及它之下的結(jié)點(diǎn)成為58的左子樹，然后再對(duì)47的右子樹所有結(jié)點(diǎn)進(jìn)行插入操作，如圖8-6-11所示。這是比較簡單的做法，可是47的右子樹有子孫共5個(gè)結(jié)點(diǎn)，這么做效率不高不說，還會(huì)導(dǎo)致整個(gè)二叉排序樹結(jié)構(gòu)發(fā)生很大的變化，有可能會(huì)增加樹的高度。增加高度可不是個(gè)好事，這我們待會(huì)再說，總之這個(gè)想法不太好。

我們仔細(xì)觀察一下，47的兩個(gè)子樹中能否找到一個(gè)結(jié)點(diǎn)可以代替47呢？ 果然有，37或者48 都可以代替47，此時(shí)在刪除47后，整個(gè)二叉排序樹并沒有發(fā)生什么本質(zhì)的變化。

為什么是37或者48？對(duì)的，它們正好是二叉排序樹中比它小或比它大的最接近47的兩個(gè)數(shù)。也就是說，如果我們對(duì)這個(gè)二叉排序樹進(jìn)行中序遍歷，得到的序列是{29,35,36,37,47,48,49,50,51,56,58,62,73,88,93,99} ,它們正好是47的前驅(qū)和后繼。

因此，比較好的做法就是，找到需要?jiǎng)h除的結(jié)點(diǎn)p的直接前驅(qū)（或直接后繼）s，用s來代替結(jié)點(diǎn)p，然后再刪除此結(jié)點(diǎn)s，如圖8-6-12所示。

根據(jù)我們對(duì)刪除結(jié)點(diǎn)三種情況的分析:

• 葉子結(jié)點(diǎn)；
• 僅有左子樹或右子樹的結(jié)點(diǎn)；
• 左右子樹都有的結(jié)點(diǎn)。
  我們來看代碼，下面這個(gè)算法是遞歸方式對(duì)二叉排序樹T查找key，查找到時(shí)刪除。

//若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該結(jié)點(diǎn) //并返回TRUE，否則返回FALSEStatus DeleteBST( BiTree *T, int key){if( ! * T) //不存在關(guān)鍵字等于key的數(shù)據(jù)元素return FALSE;else{if(key==(*T)->data) return Delete(T);// 找到關(guān)鍵字等于key的數(shù)據(jù)元素else if( key<(*T)->data)return DeleteBST(&(*T)->lchild,key);else return DeleteBST(&(*T)->rchild,key);}}

這段代碼和前面的二叉排序樹查找?guī)缀跬耆嗤?#xff0c;唯一的區(qū)別在于第8行，此時(shí)執(zhí)行第是Delete方法，對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行刪除操作。我們來看Delete的代碼

//從二叉排序樹中刪除結(jié)點(diǎn)p，并重接它的左或右子樹Status Delete(BiTree *p){BiTree q,s;if((*p)->rchild ==NULL) { //右子樹為空，只需要重掛接它的左子樹q=*p; (*p)=(*p)->lchild; free(q); //先把它賦值給結(jié)點(diǎn)q，然后把它左兒子付給它，然后釋放q}else if( (*p)->lchild == NULL){ //左子樹為空，只需要重掛接它的右子樹q=*p; *p= (*p) ->rchild; free(q);}else{ //左右子樹都不為空q=*p; s=(*p)->lchild;while( s->rchild){ //轉(zhuǎn)左，燃火向右到盡頭（找待刪結(jié)點(diǎn)的前驅(qū)）q=s; s=s->rchild;}(*p)->data=s->data; // s指向被刪除結(jié)點(diǎn)的直接前驅(qū)if(q!= *p)q->rchild=s->lchild; //重接q的右子樹elseq->lchild=s->lchild; //重接q的左子樹free(s);}return TRUE; }

1 程序開始執(zhí)行， 代碼第4~7行目的是為了刪除沒有右子樹只有左子樹的結(jié)點(diǎn)。此時(shí)只需要將此結(jié)點(diǎn)的左孩子替換它自己，然后釋放此結(jié)點(diǎn)的內(nèi)存，就等于刪除了。

2 代碼第8~11行 是同樣的道理 ，處理只有右子樹而沒有左子樹的結(jié)點(diǎn)。

3第12~25行，處理復(fù)雜的左右子樹都存在的問題。

4 在第14行，將要?jiǎng)h除的結(jié)點(diǎn)p賦值給臨時(shí)變量q，再將p的左孩子 p->lchild 賦值給臨時(shí)變量s。此時(shí) q指向47結(jié)點(diǎn)， s指向35結(jié)點(diǎn)，如圖8-6-13所示。

5 第15~18行，循環(huán)找到左子樹的右結(jié)點(diǎn)，直到右側(cè)盡頭。就當(dāng)前的例子來所，就是讓q指向35，而s指向了37這個(gè)再?zèng)]有右子樹的結(jié)點(diǎn)，如下圖所示。

6 第19行，此時(shí)讓待刪除的結(jié)點(diǎn)p的位置的數(shù)據(jù)被賦值為s->data ,即讓 p->data = 37，如下圖所示。【用直接前驅(qū)覆蓋】

7 第20~23行，如果q和p的指向不同，則將s->lchild 賦值給q->rchild,否則就是將s->lchild 賦值給q->lchild，顯然這個(gè)例子p不等于q，將s->lchild 指向的36 賦值給 q->rchild ,也就是讓q->rchild 指向36結(jié)點(diǎn)，如下圖。

8 第24行，free(s)，就非常好理解了，將結(jié)點(diǎn)37刪除，如下圖。

從這段代碼可以看出，我們其實(shí)是在找刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)替換，對(duì)于用后繼結(jié)點(diǎn)替換的思路，方法上是一樣的。

8.6.4 二叉排序樹總結(jié)

總之，二叉排序樹是以鏈接的方式存儲(chǔ)，保持了鏈接存儲(chǔ)結(jié)構(gòu)在執(zhí)行插入和刪除操作時(shí)不用移動(dòng)元素的優(yōu)點(diǎn)，只要找到合適的插入和刪除位置后，僅需要修改鏈接指針即可。 插入刪除的時(shí)間性能比較好。而對(duì)于二叉排序樹的查找，走的就是從根結(jié)點(diǎn)到要查找結(jié)點(diǎn)的路徑，其比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹的層數(shù)。 也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀。可問題就在于，二叉排序樹的形狀是不確定的。

例如{62,88,58,47,35,73,51,99,37,93} 這樣的數(shù)組，我們可以構(gòu)建如圖8-6-18左圖的二叉排序樹。但如果數(shù)組元素的次序是從小到大有序，則二叉排序樹就變成了極端的右斜樹，注意它依然是一棵二叉排序樹，如右圖。此時(shí)，同樣是查找結(jié)點(diǎn)99，左圖僅需要2次比較，而右圖就需要進(jìn)行10次比較才可以得到結(jié)果，二者差異很大。

也就是說，我們希望二叉排序樹是比較平衡的，即其深度與完全二叉樹相同，均為$?lo{g}_{2}n?+1$，那么查找的時(shí)間復(fù)雜度就是O(logn)，近似于二分查找，事實(shí)上，上圖中的左圖也不夠平衡，明顯的左重右輕。

不平衡的最壞情況就是像上圖右圖的斜樹，查找時(shí)間復(fù)雜度為O(n),這等同于順序查找。

因此，我們希望對(duì)一個(gè)集合按照二叉排序樹查找，最好是把它構(gòu)建成一個(gè)平衡的二叉排序樹。這樣我們就引申出另一個(gè)問題，如何讓二叉排序樹平衡的問題。

最后，記住二叉排序樹解決的問題是:

$既可以使得插入和刪除效果不錯(cuò)，又可以比較高效率地實(shí)現(xiàn)查找$

8.7 平衡二叉樹(AVL樹)

平衡二叉樹（Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree），是一種排序二叉樹，其中每一個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度差至多為1.

有兩位俄羅斯的數(shù)學(xué)家 G.M.Adelson-Velskii和 E.M.Landis 在1962年共同發(fā)明一種解決平衡二叉樹的算法，所以有不少資料也稱平衡二叉樹為AVL樹。

從平衡二叉樹的英文名字中，你也可以體會(huì)到，它是一種高度平衡的二叉排序樹。那什么叫做高度平衡呢？ 意思是說， 要么它是一棵空樹，要么它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1. 我們將二叉樹上結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子BF（Balance Factor），那么平衡二叉樹上所有結(jié)點(diǎn)的平衡因此只可能是-1，0，1.只要二叉樹上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹就是不平衡的。

看圖8-7-2，為什么圖1是平衡二叉樹，而圖2而不是呢？這里要考察的是我們對(duì)平衡二叉樹定義的理解，它的前提首先是一棵二叉排序樹，右上圖的59比58大，卻是58的左子樹，這是不符合二叉排序樹的定義的。圖3不是平衡二叉樹在于結(jié)點(diǎn)58的左子樹高度為2，而沒有右子樹，兩者之差大于1，因此它是不平衡的。而經(jīng)過適當(dāng)調(diào)整的ttu4，它就符合平衡二叉樹的定義，因此它是平衡二叉樹。

距離插入結(jié)點(diǎn)最近的，且平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹，我們 稱為最小不平衡子樹。 圖8-7-3，當(dāng)新插入結(jié)點(diǎn)37時(shí)，距離它最近的平衡因子絕對(duì)值超過1的結(jié)點(diǎn)為58，所以從58開始以下的子樹為最小不平衡二叉樹。

8.7.1 平衡二叉樹實(shí)現(xiàn)原理

平衡二叉樹構(gòu)建的基本思想就是在構(gòu)建二叉排序樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡二叉樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡二叉樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。

為了能在講解算法時(shí)輕松一些，我們先講一個(gè)平衡二叉樹構(gòu)建過程的例子。 假設(shè)我們現(xiàn)在有一個(gè)數(shù)組 a[10]={3,2,1,4,5,6,7,10,9,8} 需要構(gòu)建二叉排序樹。在沒有學(xué)習(xí)平衡二叉樹之前，根據(jù)二叉排序樹的特性，我們通常會(huì)將它構(gòu)建成如圖8-7-4的圖1所示的樣子。雖然它完全符合二叉排序樹的定義，但是對(duì)這樣高度達(dá)到8的二叉樹來說，查找是非常不利的。我們更期望能構(gòu)建如圖8-7-4圖2的樣子，高度為4的二叉排序樹才可以提供高的查找效率。那么現(xiàn)在我們就來研究如何將一個(gè)數(shù)組構(gòu)建出圖2的樹結(jié)構(gòu)。

對(duì)于數(shù)組 a[10]={3,2,1,4,5,6,7,10,9,8} 的前兩位3和2，我們很正常地構(gòu)建，到了第三個(gè)數(shù)“1”時(shí)，發(fā)現(xiàn)此時(shí)根結(jié)點(diǎn)3的平衡因子變成了2，此時(shí)整棵樹成為了最小不平衡子樹，因此需要調(diào)整，如圖8-7-5的圖1（結(jié)點(diǎn)左上角數(shù)字為平衡因子BF值）。因?yàn)锽F值為正，因此我們將整個(gè)樹進(jìn)行右旋（順時(shí)針旋轉(zhuǎn)），此時(shí)結(jié)點(diǎn)2變成了根結(jié)點(diǎn)，3變成了2的右孩子，這樣三個(gè)結(jié)點(diǎn)的BF值均為0，非常的平衡，如圖2所示。

然后我們?cè)僭黾咏Y(jié)點(diǎn)4，平衡因子沒有超過2，如圖3.

增加結(jié)點(diǎn)5，結(jié)點(diǎn)的3的BF值變成了-2，說明要旋轉(zhuǎn)了。由于BF是負(fù)值，所以我們對(duì)這棵最小不平衡二叉樹左旋（逆時(shí)針旋轉(zhuǎn)），如圖4，此時(shí)我們整個(gè)樹又達(dá)到了平衡。

繼續(xù)，增加結(jié)點(diǎn)6時(shí)，發(fā)現(xiàn)根結(jié)點(diǎn)2的BF值變成了-2，如圖8-7-6的圖6，所以我們對(duì)根結(jié)點(diǎn)進(jìn)行左旋，注意此時(shí)本來結(jié)點(diǎn)3是4的左孩子，由于旋轉(zhuǎn)后需要滿足二叉排序樹特性，因此它成了結(jié)點(diǎn)2的右孩子，如圖7.增加結(jié)點(diǎn)7，同樣的左旋轉(zhuǎn)，使得整棵樹達(dá)到平衡，如圖8和圖9.

當(dāng)增加結(jié)點(diǎn)10時(shí)，結(jié)構(gòu)無變化，如圖8-7-7的圖10.再增加結(jié)點(diǎn)9，此時(shí)結(jié)點(diǎn)7的BF變成了-2，理論上我們只需要旋轉(zhuǎn)最小不平衡子樹7、9、10即可，但是如果左旋轉(zhuǎn)后，結(jié)點(diǎn)9就變成了10的右孩子，這是不符合二叉排序樹的特性的，此時(shí)不能簡單地左旋，如圖11所示。

仔細(xì)觀察圖11，發(fā)現(xiàn)根本原因在于結(jié)點(diǎn)7的BF是-2，而結(jié)點(diǎn)10的BF是1，也就是說，他們倆一正一負(fù)，符號(hào)并不統(tǒng)一，而前面的幾次旋轉(zhuǎn)，無論左旋還是右旋，最小不平衡子樹的根結(jié)點(diǎn)它的子結(jié)點(diǎn)符號(hào)都是相同的。這就是不能直接進(jìn)行旋轉(zhuǎn)的關(guān)鍵。那怎么辦呢？

不統(tǒng)一，不統(tǒng)一就把它們先轉(zhuǎn)到符號(hào)統(tǒng)一再說，于是我們先對(duì)結(jié)點(diǎn)9和結(jié)點(diǎn)10右旋，使得10變成結(jié)點(diǎn)9的右子樹，結(jié)點(diǎn)8的BF變成-1，此時(shí)就和結(jié)點(diǎn)7的BF值符號(hào)統(tǒng)一了，如圖8-7-7的圖12所示。

這樣我們?cè)僖越Y(jié)點(diǎn)7為最小不平衡子樹進(jìn)行左旋，得到圖8-7-8的圖13.
接著插入結(jié)點(diǎn)8，情況和剛才類似，結(jié)點(diǎn)6的BF是-2，而它的右孩子9的BF是1，如圖14，因此首先以9為根結(jié)點(diǎn)，進(jìn)行右旋，得到圖15，此時(shí)結(jié)點(diǎn)6和結(jié)點(diǎn)7的符號(hào)都是負(fù)，再以6為根結(jié)點(diǎn)左旋，最終得到最后的平衡二叉樹。

相信大家有點(diǎn)明白，所謂的平衡二叉樹，其實(shí)就是在二叉排序樹創(chuàng)建過程中保證它的平衡性，一旦發(fā)現(xiàn)有不平衡的情況，馬上處理，這樣就不會(huì)造成不可收拾的情況出現(xiàn)。通過剛才這個(gè)例子，你會(huì)發(fā)現(xiàn)，當(dāng)最小不平衡子樹根結(jié)點(diǎn)的平衡因子BF是大于1時(shí)，就右旋，小于-1時(shí)就左旋。插入結(jié)點(diǎn)后，最小不平衡子樹的BF與它的子樹的BF符號(hào)相反時(shí)，就需要對(duì)結(jié)點(diǎn)先進(jìn)行一次旋轉(zhuǎn)以使得符號(hào)相同，之后再反向旋轉(zhuǎn)一次才能夠完成平衡操作。

8.7.2 平衡二叉樹實(shí)現(xiàn)算法

好了，有了這么多的準(zhǔn)備工作，我們可以來講解代碼了。首先是需要改進(jìn)二叉排序樹的結(jié)點(diǎn)結(jié)構(gòu)，增加一個(gè)bf，用來存儲(chǔ)平衡因子。

//二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義typedef struct BiTNode{int data;// 結(jié)點(diǎn)數(shù)據(jù)int bf;// 結(jié)點(diǎn)的平衡因子struct BiTNode *lchild, *rchild;//左右孩子指針 }BiTNode, *BiTNode;

然后，對(duì)于右旋操作，我們的代碼如下。

//對(duì)以p為根的二叉排序樹作右旋處理 //處理之后p指向新的樹根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點(diǎn)void R_Rotate(BiTree *p){BiTree L;L=(*p) -> lchild; //L指向p的左子樹根結(jié)點(diǎn)(* p) -> rchild=L->rchild;L->rchild=( *p);*p =L;}

此段代碼的意思是說，當(dāng)傳入一個(gè)二叉排序樹P，將的它的左孩子結(jié)點(diǎn)定義為L，將L的右子樹變成P的左子樹，再將P改成L的右子樹，最后將L替換P成為根結(jié)點(diǎn)。 這樣就完成了一次右旋操作，如圖8-7-9所示。圖中三角形代筆子樹，N代表新增結(jié)點(diǎn)。 上面例子中的新增結(jié)點(diǎn)N（對(duì)應(yīng)下圖中的圖1和圖2），就是右旋操作。

左旋操作代碼如下

//對(duì)以p為根的二叉排序樹做左旋處理//處理之后p指向新的樹根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點(diǎn)R void L_Rotate(BiTree *p){BiTree R;R=( *p)->rchild;(*p)->rchild= R->rchild;R->lchild=(*p);*p=R; //p指向新的根結(jié)點(diǎn) }

這段代碼和右旋代碼對(duì)稱，在此不做過多解釋。

現(xiàn)在我們來看看左平衡旋轉(zhuǎn)處理的函數(shù)代碼

#define LH 1 //左高 #define EH 0 //等高 #define RH -1 //右高//對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理 //本算法結(jié)束時(shí)，指針T指向新的根結(jié)點(diǎn)void LeftBalance(BiTree *T){BiTree L,Lr;L=(*T)->lchild;// L指向T的左子樹根結(jié)點(diǎn)switch( L->bf){case LH: // 新結(jié)點(diǎn)插入在T的左孩子的左子樹上，要做單右旋處理(*T)->bf=L->bf=EH;R_Rotate(T);break;case RH: //新結(jié)點(diǎn)插入在T的左孩子的右子樹上，要做雙旋處理Lr=L->rchild;// Lr指向T的左孩子的右子樹根switch(Lr->bf){case LH:(*T)->bf=RH;L->bf=EH;break;case EH:(*T)->bf=L->bf=EH;break;case RH:(*T)->bf=EH;L->bf=LH;break;}Lr->bf=EH;L_Rotate(*(*T)->lchild); //對(duì)T的左子樹作左旋平衡處理R_Rotate(T);//對(duì)T作右旋平衡處理}}

首先，我們定義了三個(gè)常數(shù)變量，分別是1、0和-1.

1 函數(shù)被調(diào)用，傳入一個(gè)需要調(diào)整平衡性的子樹T. 由于LeftBalance 函數(shù)被調(diào)用時(shí)，其實(shí)是已經(jīng)確認(rèn)當(dāng)前子樹是不平衡狀態(tài)，且左子樹的高度大于右子樹的高度。換句話說，此時(shí)T的根結(jié)點(diǎn)應(yīng)該是平衡因子BF的值大于1的數(shù)。

2 第4行，我們將T的左孩子賦值給L.

3 第5~27行是分支判斷

4 當(dāng)L的平衡因子為LH，即為1時(shí)，表明它與根結(jié)點(diǎn)的BF值符號(hào)相同，因此，第8行，將 它們的BF值都改成0，并且第8行，進(jìn)行右旋操作。操作方式如圖8-7-9所示。

5 當(dāng)L的平衡因子為RH，即為-1時(shí)，表明它與根節(jié)點(diǎn)的BF值符號(hào)相反，此時(shí)需要作雙旋處理。第13~22行代碼，針對(duì)L的右孩子Lr的BF作判斷，修改根結(jié)點(diǎn)T的L的BF值。第24行將當(dāng)前Lr的BF改為0.

6 第25行，對(duì)根結(jié)點(diǎn)的左子樹進(jìn)行左旋，如圖8-7-10第二圖所示。

7 第26行，對(duì)根結(jié)點(diǎn)進(jìn)行右旋，如圖8-7-10第三圖所示，完成平衡操作。

同樣的，右平衡旋轉(zhuǎn)處理的函數(shù)代碼非常類似，直接看代碼，不做講解了。

/* 對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理， */ /* 本算法結(jié)束時(shí)，指針T指向新的根結(jié)點(diǎn) */ void RightBalance(BiTree *T) { BiTree R,Rl;R=(*T)->rchild; /* R指向T的右子樹根結(jié)點(diǎn) */ switch(R->bf){ /* 檢查T的右子樹的平衡度，并作相應(yīng)平衡處理 */ case RH: /* 新結(jié)點(diǎn)插入在T的右孩子的右子樹上，要作單左旋處理 */ (*T)->bf=R->bf=EH;L_Rotate(T);break;case LH: /* 新結(jié)點(diǎn)插入在T的右孩子的左子樹上，要作雙旋處理 */ Rl=R->lchild; /* Rl指向T的右孩子的左子樹根 */ switch(Rl->bf){ /* 修改T及其右孩子的平衡因子 */ case RH: (*T)->bf=LH;R->bf=EH;break;case EH: (*T)->bf=R->bf=EH;break;case LH: (*T)->bf=EH;R->bf=RH;break;}Rl->bf=EH;R_Rotate(&(*T)->rchild); /* 對(duì)T的右子樹作右旋平衡處理 */ L_Rotate(T); /* 對(duì)T作左旋平衡處理 */ } }

我們前面例子中的新增結(jié)點(diǎn)9和8就是典型的右平衡旋轉(zhuǎn)，并且雙旋完成平衡的例子（如圖9-7-7的圖11，12，圖8-7-8的圖14、15、16）

有了這些準(zhǔn)備，我們的主函數(shù)才正式登場

//若平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為額的新結(jié)點(diǎn)并返回1，否則返回0. //若因插入而使二叉排序樹失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長高與否。Status InsertAVL(BiTree *T, int e, Status *taller){if(! *T){//插入新結(jié)點(diǎn)，樹“長高”，置taller 為TRUE*T=(BiTree) malloc(sizeof(BiNode));(*T)->data=e;(*T)->lchild=(*T)->rchild=NULL;(*T)->bf=EH;*taller=TRUE;}else{if(e==(*T)->data){//樹中已經(jīng)存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入*taller=FALSE;return FALSE;}if( e<(*T)->data){//應(yīng)繼續(xù)在T的左子樹中進(jìn)行搜索if( !InsertAVL( &(*T)->lchild,e,taller)) //未插入return FALSE;if(*taller){//已經(jīng)插入到T的左子樹中且左子樹長高switch((*T)->bf){//檢查T的平衡度case LH://原本左子樹比右子樹高，需要作左平衡處理LeftBalance(T);*taller=FALSE;break;case EH://原本左右子樹高度相同，現(xiàn)因?yàn)樽笞訕湓龈叨鴺湓龈?span id="ze8trgl8bvbq" class="token punctuation">(*T)->bf=LH;*taller=TRUE;break;case RH: //原本右子樹比左子樹高，現(xiàn)在左右子樹等高(*T)->bf=EH;*taller=FALSE;break;}}}else{//應(yīng)該繼續(xù)在T的右子樹中進(jìn)行搜索if( !InsertAVL( &(*T)->rchild,e,taller)) //未插入return FALSE;if(*taller){//已經(jīng)插入到T的右子樹中且右子樹長高switch((*T)->bf){//檢查T的平衡度case LH://原本左子樹比右子樹高，現(xiàn)在左右子樹等高(*T)->bf=EH;*taller=FALSE;break;case EH://原本左右子樹高度相同，現(xiàn)因?yàn)橛易訕湓龈叨鴺湓龈?span id="ze8trgl8bvbq" class="token punctuation">(*T)->bf=RH;*taller=TRUE;break;case RH: //原本右子樹比左子樹高，需要作右平衡處理RightBalance(T);*taller=FALSE;break;}}}}return TRUE; }

1 程序開始執(zhí)行時(shí)，第3~10行是指當(dāng)前T為空時(shí)，則申請(qǐng)內(nèi)存新增一個(gè)結(jié)點(diǎn)。

2 第13~17行表示當(dāng)存在相同結(jié)點(diǎn)，則不需要插入

3 第18~40行，當(dāng)新結(jié)點(diǎn)小于T的跟結(jié)點(diǎn)值時(shí)，則在T的左子樹中查找

4 第20~21行，遞歸調(diào)用本函數(shù)，直到找到則返回false，否則說明插入結(jié)點(diǎn)成功，繼續(xù)執(zhí)行下面的語句。

5 第22~39行，當(dāng)taller為true時(shí)，說明插入了結(jié)點(diǎn)（在左子樹中），此時(shí)需要判斷T的平衡因子，如果時(shí)1，說明左子樹高于右子樹，需要調(diào)用LeftBalance函數(shù)進(jìn)行左平衡旋轉(zhuǎn)處理。如果為0或者-1，則說明新插入結(jié)點(diǎn)沒有讓整棵二叉排序樹失去平衡性，只需要修改相關(guān)的BF值即可。

6 第41~63行，說明新結(jié)點(diǎn)e大于T的根結(jié)點(diǎn)的值，在T的有子樹中查找。代碼與上面類似。不再贅述。

對(duì)于這段代碼，我們只需要在需要構(gòu)建平衡二叉樹的時(shí)候執(zhí)行如下列代碼即可在內(nèi)存中生成一棵與圖8-7-4的圖2相同的平衡的二叉樹。

int i; int a[10]={3,2,1,4,5,6,7,10,9,8} BiTree T=NULL; Status taller; for(i=0;i<10;i++){InserAVL(&T,a[i],&taller); }

終于講完了，本算法代碼較長，是有些復(fù)雜，編程中容易在很多細(xì)節(jié)上出錯(cuò)，要想真正掌握它，需要自己多練習(xí)。不過其思想還是不難理解的，總之就是把不平衡消滅在最早時(shí)刻。

如果我們需要查找的集合本身沒有順序，在頻繁查找的同時(shí)也需要經(jīng)常的插入和刪除，顯然我們需要構(gòu)造一棵二叉排序樹，但是不平衡的二叉排序樹，查找效率是很低的，因此我們?cè)跇?gòu)建時(shí)，就讓這棵二叉排序樹是平衡二叉樹，此時(shí)我們的查找時(shí)間復(fù)雜度為O(logn)，而插入和刪除也為O(logn)。這顯然是比較理想的一種動(dòng)態(tài)查找表算法。

8.8 多路查找樹(B樹)

內(nèi)存一般都是由硅制的存儲(chǔ)芯片組成，這種技術(shù)的每個(gè)存儲(chǔ)單元單位代價(jià)都是比磁盤存儲(chǔ)技術(shù)昂貴兩個(gè)數(shù)量級(jí)，因此基于磁盤技術(shù)的外存，容量比內(nèi)存的容量至少大兩個(gè)數(shù)量級(jí)。這也就是目前PC通常內(nèi)存幾個(gè)G而已，而硬盤去可以成百上千G容量的原因。

我們前面討論的數(shù)據(jù)結(jié)構(gòu)，處理數(shù)據(jù)都是在內(nèi)存中，因此考慮的都是內(nèi)存中的運(yùn)算時(shí)間復(fù)雜度。

但如果我們要操作的數(shù)據(jù)集非常大，達(dá)到內(nèi)存已經(jīng)沒有辦法處理了怎么辦呢? 如數(shù)據(jù)庫中上千萬條記錄的數(shù)據(jù)表、硬盤中上萬個(gè)文件等。在這種情況下，對(duì)數(shù)據(jù)的處理需要不斷從硬盤等存儲(chǔ)設(shè)備中調(diào)入或調(diào)出內(nèi)存頁面。

一旦涉及到這樣的外部存儲(chǔ)設(shè)備，關(guān)于時(shí)間復(fù)雜度的計(jì)算就會(huì)發(fā)生變化，訪問該集合元素的時(shí)間已經(jīng)不僅僅是尋找該元素所需比較次數(shù)的函數(shù)，我們必須考慮對(duì)硬盤等外部設(shè)備的訪問時(shí)間以及將會(huì)對(duì)該設(shè)備做出多少次單獨(dú)訪問。

試想一下，為了要在一個(gè)擁有幾十萬個(gè)文件的磁盤中查找一個(gè)文本文件，你設(shè)計(jì)的算法需要讀取磁盤上萬次還是讀取幾十次，這是有本質(zhì)差別的。此時(shí)，為了降低對(duì)外存設(shè)備的訪問次數(shù)，我們就需要新的數(shù)據(jù)結(jié)構(gòu)來處理這樣的問題。

我們之前談到的樹，都是一個(gè)結(jié)點(diǎn)可以有多個(gè)孩子，但是它自身只存儲(chǔ)一個(gè)元素。二叉樹限制更多，結(jié)點(diǎn)最多只能有兩個(gè)孩子。

一個(gè)結(jié)點(diǎn)只能存儲(chǔ)一個(gè)元素，在元素非常多的時(shí)候，就使得要么樹的度（結(jié)點(diǎn)擁有子樹的個(gè)數(shù)的最大值）非常大，要么樹的高度非常大，甚至兩者都必須足夠大才行。這就使得內(nèi)存存取外存次數(shù)非常多，這顯然成立時(shí)間效率上的瓶頸，這迫使我們要打破每一個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)元素的限制，為此引入了多路查找樹這個(gè)概念。

多路查找樹（Multi-way Search Tree），其每一個(gè)結(jié)點(diǎn)的孩子數(shù)可以多于兩個(gè)，且每一個(gè)結(jié)點(diǎn)處可以存儲(chǔ)多個(gè)元素。由于它是查找樹，所以元素之間存在某種特定的排序關(guān)系。

在這里，每一個(gè)結(jié)點(diǎn)可以存儲(chǔ)多少個(gè)元素，以及它的孩子數(shù)的多少是非常關(guān)鍵的。為此，我們講解它的四種特殊形式：2-3樹，2-3-4樹，B樹和B+樹。

8.8.1 2-3樹

2和3是基本的阿拉伯?dāng)?shù)字，用它們來命名一種樹結(jié)構(gòu)，顯然是說明這種結(jié)構(gòu)與數(shù)字2和3有密切關(guān)系。

2-3樹是這樣的一棵多路查找樹：其中的每一個(gè)結(jié)點(diǎn)都具有兩個(gè)孩子（我們稱之為2結(jié)點(diǎn)）或三個(gè)孩子（我們稱之為3結(jié)點(diǎn)）。

一個(gè)2結(jié)點(diǎn)包含一個(gè)元素和兩個(gè)孩子（或沒有孩子），且與二叉排序樹類似，左子樹包含的元素小于該元素，右子樹包含的元素大于該元素。不過，與二叉排序樹不同的是，這個(gè)2結(jié)點(diǎn)要么沒有孩子，要有就有2個(gè)，不能只有1個(gè)孩子。

一個(gè)3結(jié)點(diǎn)包含一小一大兩個(gè)元素和三個(gè)孩子（或沒有孩子），一個(gè)3結(jié)點(diǎn)要么沒有孩子，要么具有3個(gè)孩子。如果某個(gè)3結(jié)點(diǎn)有孩子的話，左子樹包含小于較小元素的元素，右子樹包含大于較大元素的元素，中間子樹包含介于兩元素之間的元素。

并且2-3樹中所有葉子結(jié)點(diǎn)都在同一層次上。如圖8-8-2所示，圖中就是一棵有效的2-3樹。

2-3樹的插入實(shí)現(xiàn)

對(duì)于2-3樹的插入來說，與二叉排序樹相同，插入操作一定是發(fā)生在葉子結(jié)點(diǎn)上。可與二叉排序樹不同的是，2-3樹插入一個(gè)元素的過程有可能會(huì)對(duì)該樹的其余結(jié)構(gòu)產(chǎn)生連鎖反應(yīng)。

2-3樹插入可分為三種情況：

1）對(duì)于空樹，插入一個(gè)2結(jié)點(diǎn)即可，這很容易理解。

2）插入結(jié)點(diǎn)到一個(gè)2結(jié)點(diǎn)的葉子上。應(yīng)該說，由于其本身就只有一個(gè)元素，所以只需要將其升級(jí)為3結(jié)點(diǎn)即可。如圖8-8-3所示（這里是對(duì)圖8-8-2的簡化表達(dá)），我們希望從左圖的2-3樹種插入元素3，根據(jù)遍歷可知，3比8小，比4小，于是就只能考慮插入到葉子結(jié)點(diǎn)1所在的位置，因此很自然的想法就是將此結(jié)點(diǎn)變成一個(gè)3結(jié)點(diǎn)，即右圖這樣完成插入操作。當(dāng)然，要視插入的元素與當(dāng)前葉子結(jié)點(diǎn)的元素大小關(guān)系，決定誰在左誰在右。例如，若插入的是0，則此結(jié)點(diǎn)就是0在1的左邊了。

3）要往3結(jié)點(diǎn)中插入一個(gè)新元素。因?yàn)?結(jié)點(diǎn)本身已經(jīng)是2-3樹的結(jié)點(diǎn)最大容量（已經(jīng)有兩個(gè)元素），因此就需要將其拆分，且在該3結(jié)點(diǎn)中的兩元素以及待插入元素中，選擇其一向上移動(dòng)一層。復(fù)雜的情況也在于此。

第一種情況，見圖8-8-4，需要向左圖中插入元素5.經(jīng)過遍歷可得到元素6比8小比4大，因此它應(yīng)該是需要插入在擁有6和7元素的這個(gè)3結(jié)點(diǎn)位置。問題就在于，這已經(jīng)是一個(gè)3結(jié)點(diǎn)，不能再添加。此時(shí)發(fā)現(xiàn)它的雙親結(jié)點(diǎn)4是個(gè)2結(jié)點(diǎn)，因此考慮讓它升級(jí)為3結(jié)點(diǎn)，這樣它就得有3個(gè)孩子，于是就想到，將6、7結(jié)點(diǎn)拆分，讓6與4結(jié)合形成3結(jié)點(diǎn)，將5成為它的中間孩子，將7變成它的右孩子，如右圖。

另一種情況，如圖8-8-5所示，需要向左圖插入元素11.經(jīng)過遍歷可得到元素比12小，比10大，因此它應(yīng)該插入在擁有9、10元素的3結(jié)點(diǎn)位置。同樣道理，9和10 所在節(jié)點(diǎn)不能再增加元素。此時(shí)發(fā)現(xiàn)它的雙親結(jié)點(diǎn)12，14也是3結(jié)點(diǎn)，也不能再插入新元素。在往上看，12，14的雙親結(jié)點(diǎn)，結(jié)點(diǎn)8是2結(jié)點(diǎn)。于是就想到，將9，10拆分，12，14也拆分，讓根結(jié)點(diǎn)8升級(jí)到3結(jié)點(diǎn)，最終形成右圖的樣子。

再來看個(gè)例子，如圖8-8-6所示，需要在左圖中插入元素2.

經(jīng)過遍歷可得到元素2比4小，比1大，因此需要插入在擁有1和3元素的3結(jié)點(diǎn)位置。與上例一樣，你會(huì)發(fā)現(xiàn)1，3結(jié)點(diǎn)，4，6結(jié)點(diǎn)，甚至是8，12都是3結(jié)點(diǎn)，那就意味著，當(dāng)前我們的樹結(jié)構(gòu)是3層已經(jīng)不能滿足結(jié)點(diǎn)增加的要求了。于是將1，3拆分，4，6拆分，甚至根結(jié)點(diǎn)8，12也拆分，形成右圖所示的樣子。

通過這個(gè)例子，也讓我們發(fā)現(xiàn)，如果2-3樹插入的傳播效應(yīng)導(dǎo)致了根結(jié)點(diǎn)的拆分，則樹的高度就會(huì)增加。

2-3樹的刪除實(shí)現(xiàn)

對(duì)于2-3樹的刪除來說，如果對(duì)前面插入的理解到位的話，應(yīng)該不是難事兒。2-3樹的刪除也分為三種情況。與插入相反，我們從3結(jié)點(diǎn)說起。

1） 所刪除元素位于一個(gè)3結(jié)點(diǎn)的葉子結(jié)點(diǎn)上，這非常簡單，只需要在該結(jié)點(diǎn)處刪除該元素即可，不會(huì)影響到整棵樹的其他結(jié)點(diǎn)的結(jié)構(gòu)。如圖8-8-7所示，刪除元素9，只需要將此結(jié)點(diǎn)改成只有元素10的2結(jié)點(diǎn)即可。

2） 所刪除的元素位于一個(gè)2結(jié)點(diǎn)上，即要?jiǎng)h除的是一個(gè)只有一個(gè)元素的結(jié)點(diǎn)。如果按照以前樹的理解，刪除即可，可是現(xiàn)在2-3樹的定義告訴我們這樣做是不可以的。比如圖8-8-8中，如果我們刪除了結(jié)點(diǎn)1，那么結(jié)點(diǎn)4本來是一個(gè)2結(jié)點(diǎn)（它擁有2個(gè)孩子），此時(shí)它就不滿足定義了。

對(duì)于刪除葉子是2結(jié)點(diǎn)的情況，我們需要分為四種情況來處理。

情形一，此結(jié)點(diǎn)的雙親也是2結(jié)點(diǎn)，且擁有一個(gè)3結(jié)點(diǎn)的右孩子。
如圖8-8-9，刪除結(jié)點(diǎn)1，那么只需要左旋，即6變成雙親，4成為6的左孩子，7是6的右孩子。

情形二，此結(jié)點(diǎn)的雙親是2結(jié)點(diǎn)，它的右孩子也是2結(jié)點(diǎn)。

如圖8-8-10，此時(shí)刪除結(jié)點(diǎn)4，如果直接左旋回造成沒有右孩子，因此需要對(duì)整棵樹變形，辦法就是，我們的目標(biāo)就是讓結(jié)點(diǎn)7變成結(jié)點(diǎn)3，那就得讓比7稍大的元素8下來，隨即就得讓比元素8稍大的元素補(bǔ)充結(jié)點(diǎn)8的位置，于是就有了中間圖，于是再用左旋的方式，變成右圖的效果。

情形三，此結(jié)點(diǎn)的雙親是一個(gè)3結(jié)點(diǎn)。

如圖8-8-11，此時(shí)刪除結(jié)點(diǎn)10，意味著雙親12，14這個(gè)結(jié)點(diǎn)不能成為3結(jié)點(diǎn)了，于是將此結(jié)點(diǎn)拆分，并將12與13合并成為左孩子。

情形四，如果當(dāng)前樹是一個(gè)滿二叉樹的情況，此時(shí)刪除任何一個(gè)結(jié)點(diǎn)都使得整棵樹不能滿足2-3樹的定義。如圖8-8–12所示，刪除葉子結(jié)點(diǎn)8時(shí)，就不得不考慮要將2-3的層數(shù)減少，辦法是將8的雙親和其左子樹6合并成為一個(gè)3結(jié)點(diǎn)，再將14與9合并成3結(jié)點(diǎn)，最后變成右圖。

3）所刪除的元素位于非葉子的分支結(jié)點(diǎn)。此時(shí)我們通常是將樹按照中序遍歷后得到此元素的前驅(qū)或者后繼元素，考慮讓它們來補(bǔ)位即可。

如果我們要?jiǎng)h除的分支結(jié)點(diǎn)是2結(jié)點(diǎn)。如圖8-8-13，我們要?jiǎng)h除結(jié)點(diǎn)4，分析后得到它的前驅(qū)是1后繼是6，顯然，由于6，7是3結(jié)點(diǎn)，只需要用6來補(bǔ)位即可。

如果我們要?jiǎng)h除的分支結(jié)點(diǎn)是3結(jié)點(diǎn)的某一元素，如圖8-8-14所示我們要?jiǎng)h除12，14結(jié)點(diǎn)的12，此時(shí)，經(jīng)過分析，顯然應(yīng)該是將3結(jié)點(diǎn)的左孩子的10上升到刪除位置合適。

當(dāng)然，如果對(duì)2-3樹的插入和刪除等所有情況講解，既占篇幅，又沒必要，總的來說它是有規(guī)律 的，需要你們?cè)谏厦娴倪@些例子中多去體會(huì)后掌握。

8.8.2 2-3-4樹

有了2-3樹的講解，2-3-4樹就很好理解了，它其實(shí)就是2-3樹概念的拓展，包括了4結(jié)點(diǎn)的使用。一個(gè)4結(jié)點(diǎn)包含小中大三個(gè)元素和四個(gè)孩子（或沒有孩子），一個(gè)4結(jié)點(diǎn)要么沒有孩子，要么具有4個(gè)孩子。如果某個(gè)4結(jié)點(diǎn)有孩子的話，左子樹包含小于最小元素的元素；第二個(gè)子樹包含大于最小元素，小于第二元素的元素；第三子樹包含大于第二元素，小于最大元素的元素；右子樹包含大于最大元素的元素。

由于2-3-4樹和2-3樹類似，我么你這里就簡單介紹一下，如果我們構(gòu)建一個(gè)數(shù)組為{7,1,2,5,6,9,8,4,3} 的2-3-4樹的過程，如圖8-8-15所示。圖1是在分別插入7，1，2時(shí)候的結(jié)果，因?yàn)?個(gè)元素滿足2-3-4樹的單個(gè)4結(jié)點(diǎn)定義，因此此時(shí)不需要拆分，接著插入元素5，因?yàn)橐呀?jīng)超過4結(jié)點(diǎn)的定義，因此要拆分，變成圖2的樣子。之后的圖其實(shí)就是在元素不斷插入時(shí)最后形成了圖7的2-3-4樹。

圖8-8-16 是對(duì)一個(gè)2-3-4樹的刪除結(jié)點(diǎn)的演變過程，刪除順序?yàn)?，6，3，4，5，2，9.

8.8.3 B樹

我們本節(jié)名稱叫B樹，但到現(xiàn)在才開始提到它，似乎這主角出來的實(shí)在太晚了，可其實(shí)，我們前面一直都在將B樹。

B樹（B-Tree）是一種平衡的多路查找樹，2-3樹和2-3-4樹都是B樹的特例。結(jié)點(diǎn)最大的孩子數(shù)目稱為B樹的階（Order），因此，2-3樹是3階B樹，2-3-4樹是4階B樹。

一個(gè)m階B樹具有如下性質(zhì)：

• 如果根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則其至少有兩棵子樹。
• 每一個(gè)非根的分支結(jié)點(diǎn)都有k-1個(gè)元素和k個(gè)孩子，其中 $?m/2?\le k\le m（這里是向上取整）$
• 所有葉子結(jié)點(diǎn)都位于同一層次。
• 所有分支結(jié)點(diǎn)包含下列信息數(shù)據(jù)$n,A_0,K_1,A_1,K_2,A_2,...,K_n,A_n$ ，其中 $K_i$為關(guān)鍵字，且$K_i<K_{i+1},$Ai為指向子樹根結(jié)點(diǎn)的指針，且指針$A_{i?1}$所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于 $K_i$,$A_n$所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于$K_n$,n （$?m/2??1\le n\le m?1（這里是向上取整）$）為關(guān)鍵字的個(gè)數(shù)（或n+1為子樹的個(gè)數(shù)）

例如，在講2-3-4樹的時(shí)候插入9個(gè)數(shù)后的圖轉(zhuǎn)成B樹示意圖就如圖8-8-17右圖所示，左側(cè)灰色方塊表示當(dāng)前結(jié)點(diǎn)的元素個(gè)數(shù)。

在B樹上查找的過程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)中查找關(guān)鍵字的交叉過程。

比方說，我們要查找數(shù)字7，首先從外存（比如硬盤中）讀取得到根結(jié)點(diǎn)3，5，8三個(gè)元素，發(fā)現(xiàn)7不在其中，但在5和8之間，因此就通過A2再讀取外存的6，7結(jié)點(diǎn)，查找到所要的元素。

至于B樹的插入和刪除，方式是與2-3樹和2-3-4樹相類似的，只不過階數(shù)可能回很大而已。

我們?cè)诒竟?jié)的開頭提到，如果內(nèi)存與外存交換數(shù)據(jù)次數(shù)頻繁，會(huì)造成了時(shí)間效率上的瓶頸，那么B樹結(jié)構(gòu)怎么就可以做到減少次數(shù)呢?

我們的外存，比如硬盤，是將所有的信息分割成同樣大小的頁面，每次硬盤讀寫的都是一個(gè)或多個(gè)完整的頁面，對(duì)于一個(gè)硬盤來說，一頁的長度可能是211到214個(gè)字節(jié)。

在一個(gè)典型的B樹應(yīng)用中，要處理的硬盤數(shù)據(jù)量非常大，因此無法一次全部裝入內(nèi)存。因此我們會(huì)對(duì)B樹進(jìn)行調(diào)整，使得B樹的階數(shù)（或結(jié)點(diǎn)的元素）與硬盤存儲(chǔ)的頁面大小相匹配。比如說一棵B樹的階為1001（即1個(gè)結(jié)點(diǎn)包含1000個(gè)關(guān)鍵字），高度為2，它存儲(chǔ)超過10億個(gè)關(guān)鍵字，我們只要讓根結(jié)點(diǎn)持久地保留在內(nèi)存中，那么在這棵樹上，尋找某一關(guān)鍵字至多需要兩次硬盤讀取即可。這就好比我們普通人數(shù)錢都是一張一張地?cái)?shù)，而銀行職員數(shù)錢則是五張、十張，甚至幾十張一數(shù)，速度當(dāng)然是比常人快了不少。

通過這種方式，在內(nèi)存有限的情況下，每一次磁盤的訪問我們都可以獲得最大數(shù)量的數(shù)據(jù)。由于B樹每結(jié)點(diǎn)可以具有比二叉樹多得多的元素，所以與二叉樹的操作不同，它們減少了必須訪問結(jié)點(diǎn)和數(shù)據(jù)塊的數(shù)量，從而提高了性能。可以說，B樹的數(shù)據(jù)結(jié)構(gòu)就是為內(nèi)外存的數(shù)據(jù)交互準(zhǔn)備的。

那么對(duì)于n個(gè)關(guān)鍵字的m階B樹，最壞情況是要查找?guī)状文?#xff1f; 我們來分析一下。

第一層至少有1個(gè)結(jié)點(diǎn)，第二層至少有2個(gè)結(jié)點(diǎn)，由于除根結(jié)點(diǎn)外每個(gè)分支結(jié)點(diǎn)至少有$?m/2?$棵子樹，則第三層至少有$2\times ?m/2?$個(gè)結(jié)點(diǎn)，…,這樣第k+1層至少有$2\times (?m/2?{)}^{k?1}$個(gè)結(jié)點(diǎn)，而實(shí)際上，k+1層的結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。若m階B樹有n個(gè)關(guān)鍵字，那么當(dāng)你找到了葉子結(jié)點(diǎn)，其實(shí)也就等于查找不成功的結(jié)點(diǎn)為n+1，因此$n+1\ge 2\times (?m/2?{)}^{k?1}$，即：

$$k\le lo{g}_{?\frac{m}{2}?}(\frac{n+1}{2})+1$$

也就是說，在含有n個(gè)關(guān)鍵字的B樹上查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字結(jié)點(diǎn)路徑上涉及的結(jié)點(diǎn)數(shù)不超過$lo{g}_{?\frac{m}{2}?}(\frac{n+1}{2})+1$。

8.8.4 B+樹

盡管我們講了B樹，但是它還是有缺陷的。對(duì)于樹結(jié)構(gòu)來說，我們都可以通過中序遍歷來順序查找樹中的元素，這一切都是在內(nèi)存中進(jìn)行。

可是在B樹結(jié)構(gòu)中，我們往返于每個(gè)結(jié)點(diǎn)之間也就意味著，我們必須得在硬盤的頁面之間進(jìn)行多次訪問，如圖8-8-18所示，我們希望遍歷這棵B樹，假設(shè)每個(gè)結(jié)點(diǎn)都屬于硬盤的不同頁面，我們?yōu)榱酥行虮闅v所有的元素，頁面2→頁面1→頁面3→頁面1→頁面4→頁面1→頁面5. 而且我們每次經(jīng)過結(jié)點(diǎn)遍歷時(shí)，都會(huì)對(duì)結(jié)點(diǎn)中元素進(jìn)行一次遍歷，這就非常糟糕。有沒有可能讓遍歷時(shí)每個(gè)元素只訪問一次呢？

為了說明解決這個(gè)問題的方法，我舉個(gè)例子。一個(gè)優(yōu)秀的企業(yè)盡管可能有非常成熟的屬性組織結(jié)構(gòu)，但是這并不意味著員工也很滿意，恰恰相反，由于企業(yè)管理更多考慮的是企業(yè)的利益，這就容易忽略員工的各種訴求，造成了管理者與員工之間的矛盾。正因?yàn)槿绱?#xff0c;工會(huì)就產(chǎn)生了，工會(huì)原意指基于共同利益而自發(fā)組織的社會(huì)團(tuán)體。這個(gè)共同利益團(tuán)體諸如為同一雇主工作的員工，在某一產(chǎn)品領(lǐng)域的個(gè)人。工會(huì)組織成立的主要作用，可以與雇主談判工資薪水、工作時(shí)限和工作條件等。這樣，其實(shí)在整個(gè)企業(yè)的運(yùn)轉(zhuǎn)過程中，除了正規(guī)的層級(jí)管理外，還有一個(gè)代表員工的團(tuán)隊(duì)在發(fā)揮另外的作用。

同樣的，為了解決所有元素遍歷等基本問題，我們?cè)谠械腂樹結(jié)構(gòu)基礎(chǔ)上，加上了新的元素組織方式，這就是B+樹。

B+樹是應(yīng)文件系統(tǒng)的需求而出的一種B樹的變形樹，注意嚴(yán)格意義上來講，它其實(shí)已經(jīng)不是第六章定義的樹了。 在B樹中，每一個(gè)元素在該樹中只出現(xiàn)一次，有可能在葉子結(jié)點(diǎn)上，也有可能在分支結(jié)點(diǎn)上。而在B+樹中，出現(xiàn)在分支結(jié)點(diǎn)中的元素會(huì)被當(dāng)作它們?cè)诜种ЫY(jié)點(diǎn)位置的中序后繼者（葉子結(jié)點(diǎn)）中再次列出。另外，每一個(gè)葉子結(jié)點(diǎn)都會(huì)保存一個(gè)孩子想后一葉子結(jié)點(diǎn)的指針。

例如圖8-8-19所示，就是一棵B+樹的示意圖，灰色關(guān)鍵字即是根節(jié)點(diǎn)中的關(guān)鍵字在葉子結(jié)點(diǎn)再次列出，并且所有葉子結(jié)點(diǎn)都鏈接在一起。

一棵m階的B+樹和m階B樹的差異在于：

• 有n棵子樹的結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字
• 所有的葉子結(jié)點(diǎn)包含全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
• 所有分支結(jié)點(diǎn)可以看成是索引，結(jié)點(diǎn)中僅含有其子樹中的最大（最小）關(guān)鍵字。

這樣的數(shù)據(jù)結(jié)構(gòu)最大好處在于，如果要隨機(jī)查找，我們就從根結(jié)點(diǎn)出發(fā)，與B樹的查找方式相同，只不過即使在分支結(jié)點(diǎn)找到了待查找的關(guān)鍵字，它也只是用來索引的，不能提供實(shí)際記錄的訪問，還是需要到達(dá)包含此關(guān)鍵字的終端結(jié)點(diǎn)。

如果我們是需要從最小關(guān)鍵字進(jìn)行從小到大的順序查找，我們就可以從最左側(cè)的葉子結(jié)點(diǎn)出發(fā)，不經(jīng)過分支結(jié)點(diǎn)，而是沿著指向下一葉子的指針就可以遍歷所有的關(guān)鍵字。

B+樹的結(jié)構(gòu)特別適合帶有范圍的查找。比如查找我們學(xué)校18~22歲的學(xué)生的人數(shù)，我們可以通過從根結(jié)點(diǎn)出發(fā)找到第一個(gè)18歲的學(xué)生，然后再在葉子結(jié)點(diǎn)按順序查找符合范圍的所有記錄。

B+樹的插入、刪除過程也都與B樹類似，只不過插入和刪除的元素都是在葉子結(jié)點(diǎn)上進(jìn)行而已。

8.9 散列表（哈希表）查找概述

能夠直接通過關(guān)鍵字key得到要查找的記錄的內(nèi)存存儲(chǔ)的位置呢？

8.9.1 散列表查找定義

我們需要某個(gè)函數(shù) f，使得

存儲(chǔ)位置= f ( 關(guān)鍵字 )

那樣我們就可以通過查找關(guān)鍵字不需要比較就能獲得需要的記錄的存儲(chǔ)位置。這是一種新的存儲(chǔ)技術(shù)—散列技術(shù)。

散列技術(shù)是在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key) 。 查找時(shí)，根據(jù)這個(gè)確定的對(duì)應(yīng)關(guān)系找到給定值key 的映射f(key)，若查找集合中存在這個(gè)記錄，則必定在f(key) 的位置上。

這里我們把這種對(duì)應(yīng)關(guān)系f稱為散列函數(shù) ，又稱為哈希(Hash)函數(shù)。
按這個(gè)思想，采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)空間稱為散列表或者哈希表（Hash Table）。那么關(guān)鍵字對(duì)應(yīng)的記錄存儲(chǔ)位置我們稱為散列地址。

8.9.2 散列表查找步驟

整個(gè)散列過程其實(shí)就是兩步。

1）在存儲(chǔ)時(shí)，通過散列函數(shù)計(jì)算記錄的散列地址，并按照此散列地址存儲(chǔ)該記錄。不管是什么記錄，我們需要用同一個(gè)散列函數(shù)計(jì)算出地址再存儲(chǔ)。

2）當(dāng)查找記錄時(shí)，我們通過同樣的散列函數(shù)計(jì)算記錄的散列地址，按此散列地址訪問該記錄。說起來很簡單，在哪兒存的，就到哪兒找，由于存取用的是同一個(gè)散列函數(shù)，因此結(jié)果當(dāng)然是相同的。

所以說，散列技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法。然而它與線性表、樹、圖等結(jié)構(gòu)不同的是，前面幾種結(jié)構(gòu)，數(shù)據(jù)元素之間都存在某種邏輯關(guān)系，可以用連線圖示表示，而散列技術(shù)的記錄之間不存在什么邏輯關(guān)系，它只有關(guān)鍵字有關(guān)。因此，散列主要是面向查找的存儲(chǔ)結(jié)構(gòu)。

散列技術(shù)最適合的求解問題是查找與給定值相等的記錄。 對(duì)于查找來說，簡化了比較過程，效率就會(huì)大大提高。但萬事有利就有弊，散列技術(shù)不具備很多常規(guī)數(shù)據(jù)結(jié)構(gòu)的能力。

比如那種同樣的關(guān)鍵字，它能對(duì)應(yīng)很多記錄的情況，卻不適合用散列技術(shù)。一個(gè)班級(jí)幾十個(gè)人，他們的性別有男有女，你用關(guān)鍵字男去查找，對(duì)應(yīng)的有許多學(xué)生的記錄，這顯示是不合適的。只有用如學(xué)號(hào)或者身份證號(hào)來散列存儲(chǔ)，此時(shí)一個(gè)號(hào)碼唯一對(duì)應(yīng)一個(gè)學(xué)生。

同樣散列表也不適合范圍查找，比如查找一個(gè)班級(jí)18~22歲的同學(xué)，在散列表中無法進(jìn)行。想獲得表中記錄的排序也不可能，像最大值、最小值等結(jié)果也都無法從散列表中計(jì)算出來。

我們說了這么多，散列函數(shù)應(yīng)該如何設(shè)計(jì)？ 這個(gè)我們需要重點(diǎn)來講解，總之設(shè)計(jì)一個(gè)簡單、均勻、存儲(chǔ)利用率高的散列函數(shù)是散列技術(shù)中最關(guān)鍵的問題。

另一個(gè)問題是沖突。在理想的情況下，每一個(gè)關(guān)鍵字，通過散列函數(shù)計(jì)算出來的地址都是不一樣的，可現(xiàn)實(shí)中，這只是一個(gè)理想。我們時(shí)常會(huì)碰到兩個(gè)關(guān)鍵字 key1≠ key2，但是f(key1) = f(key2) ，這種現(xiàn)象我們稱為沖突（collision），并把key1和key2稱為這個(gè)散列函數(shù)的同義詞（synonym）。出現(xiàn)了沖突當(dāng)然非常糟糕，那就造成數(shù)據(jù)查找錯(cuò)誤。經(jīng)過我們可以通過精心設(shè)計(jì)的散列函數(shù)讓沖突盡可能少，但是不能完全避免。于是如何處理沖突就成了一個(gè)重要的課題，后面會(huì)有詳細(xì)講解。

8.10 散列函數(shù)的構(gòu)造方法

不管做什么事要達(dá)到最優(yōu)都不容易，既要付出盡可能的少，又要得到最大化的多。那么什么才是好的散列函數(shù)呢？ 這里我們有兩個(gè)原則可以參考。
1 計(jì)算簡單

散列函數(shù)的計(jì)算時(shí)間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵字比較的時(shí)間。

2散列地址分布均勻

我們剛才也提到?jīng)_突帶來的問題，最好的辦法就是盡量讓散列均勻地分布在存儲(chǔ)空間中，這樣可以保證存儲(chǔ)空間的有效利用，并減少為處理沖突而耗費(fèi)的時(shí)間。

接下來我們介紹幾種常用的散列函數(shù)構(gòu)造方法。

8.10.1 直接定址法

我們現(xiàn)在要對(duì)0~100歲的人口數(shù)字統(tǒng)計(jì)，如表8-10-1所示，那么我們對(duì)年齡這個(gè)關(guān)鍵字就可以直接用年齡的數(shù)字作為地址。此時(shí)f(key)=key.

如果我們現(xiàn)在要統(tǒng)計(jì)的是80后出生年份的人口數(shù)，如下表。那么我們對(duì)出生年份這個(gè)關(guān)鍵字可以用年份減去1980來作為地址。此時(shí)f(key)=key-1980.

也就是說，我們可以取關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址，即
$$f(key)=a\times key+b,(a,b為常數(shù))$$

這樣的散列函數(shù)優(yōu)點(diǎn)是簡單、均勻，也不會(huì)產(chǎn)生沖突，但問題是這需要事先知道關(guān)鍵字的分布情況，適合查找表較小且連續(xù)的情況。由于這樣的限制，在現(xiàn)實(shí)應(yīng)用中，此方法雖然簡單，但卻并不常用。

8.10.2 數(shù)字分析法

如果我們的關(guān)鍵字是位數(shù)較多的數(shù)字，比如我們的11為手機(jī)號(hào)，其中前三位是接入號(hào)，一般對(duì)應(yīng)不同運(yùn)營商公司的子品牌，比如130是聯(lián)通如意通，136是移動(dòng)神州行，153是電信等。中間四位是HLR識(shí)別號(hào)，表示用戶號(hào)的歸屬地；后四位才是真正的用戶號(hào)，如下表。

若我們現(xiàn)在要存儲(chǔ)某家公司員工登記表，如果用手機(jī)號(hào)作為關(guān)鍵字，那么極有可能前7位都是相同的。那么我們選擇后面的四位稱為散列地址就是不錯(cuò)的選擇。如果這樣的抽取工作還是容易出現(xiàn)沖突問題，還可以對(duì)抽取出來的數(shù)字再進(jìn)行反轉(zhuǎn)（如1234改成4321），右環(huán)位移（如1234變成4123），左環(huán)位移，甚至前兩數(shù)和后兩數(shù)疊加（如1234改成12+34=46）等方法。總的目的就是為了提供一個(gè)散列函數(shù)，能夠合理地將關(guān)鍵字分配到散列表的各位置。

這里我們提到了一個(gè)關(guān)鍵詞—抽取。抽取方法是使用關(guān)鍵字的一部分來計(jì)算散列存儲(chǔ)位置的方法，這在散列函數(shù)中是經(jīng)常用到的手段。

數(shù)字分析法適合處理關(guān)鍵字位數(shù)比較多的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻，就可以考慮用這個(gè)方法。

8.10.3 平方取中法

這個(gè)方法計(jì)算很簡單，假設(shè)關(guān)鍵字是1234，它的平方是1522756，再抽取中間的3位就是227，用作散列地址。 再比如關(guān)鍵字4321，那么它的平方就是18671041，抽取中間的3位就可以是671或者是710，用作散列地址。平方取中法比較適用于不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。

8.10.4 折疊法

折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時(shí)可以短些），然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。

比如我們的關(guān)鍵字是 9876543210，散列表表長為3位，我們將它分為四組，987，654，321，0，然后將它們疊加求和987+654+321+0=1962，再求后3位得到散列地址為962.

有時(shí)可能這還不夠保證均勻分布，不妨從一端向另一端來回折疊后對(duì)齊相加。比如我們將987和321反轉(zhuǎn)，再與654和0相加，變成789+654+123+0=1566，此時(shí)散列地址為566.

折疊法事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況。

8.10.5 除留余數(shù)法

此方法為最常用的構(gòu)造散列函數(shù)的方法。對(duì)于散列表長為m的散列函數(shù)公式為

$$f(key)=key\mathrm{m}\mathrm{o}\mathrm{d}p(p\le m)$$

mod是取模（求余數(shù)）的意思。事實(shí)上，這方法不僅可以對(duì)關(guān)鍵字直接取模，還可以在折疊、平方取中后再取模。

很顯然，該方法的關(guān)鍵在于選擇合適的p，p如果選得不好，就可能會(huì)容易產(chǎn)生同義詞。

例如表8-10-4，我們對(duì)于有12個(gè)記錄的關(guān)鍵字構(gòu)造散列表，就用了f(key)= key mod 12 的方法，比如 29 mod 12 =5 ,所以它存儲(chǔ)在下標(biāo)為5的位置。

不過這也會(huì)存在沖突， 如下表，p=12，此時(shí)下標(biāo)全部是0，這就極為糟糕。

我們不選 p=12來做除留余數(shù)法，而選用p=11，如下表

此時(shí)只有12和144有沖突，相對(duì)來說，就要好很多。

因此根據(jù)前輩們的經(jīng)驗(yàn)，若散列表表長為m，通常p為小于等于表長（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。

8.10.6 隨機(jī)數(shù)法

選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。也就是f(key)= random(key) ,這里的random是隨機(jī)數(shù)函數(shù)。當(dāng)關(guān)鍵字的長度不等時(shí)，采用這個(gè)方法構(gòu)造散列函數(shù)是比較合理的。

有同學(xué)問，如果關(guān)鍵字是字符串如何處理？ 其實(shí)無論是英文字符，還是中文字符，也包含各種各樣的符號(hào)，它們都可以轉(zhuǎn)化為某種數(shù)字來對(duì)待，比如ASCII碼或者Unicode碼等，因此也就可以使用上述方法。

總之，現(xiàn)實(shí)中，應(yīng)該視不同的情況采用不同的散列函數(shù)。我們只能給出一些考慮因素來提供參考:

計(jì)算散列地址所需要的時(shí)間

關(guān)鍵字的長度

散列表的大小

關(guān)鍵字的分布情況

記錄查找的頻率。

綜合這些因素，才能決策選擇哪種散列函數(shù)更合適。

8.11 處理散列沖突的方法

沖突其實(shí)是不能避免的，要考慮怎么來處理。

8.11.1 開放定址法

所謂的開放定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列列表足夠大，空的散列地址總能找到，并將記錄存入。

它的公式是

比如說，我們的關(guān)鍵字集合為{12,67,56,16,25,37,22,29,15,47,48,34}，表長為12.我們用散列函數(shù) f(key) = key mod 12.

當(dāng)計(jì)算 前5個(gè)數(shù){12,67,56,16,25}時(shí)，都是沒有沖突的散列地址，直接存入，如下表。

計(jì)算key=37時(shí)，發(fā)現(xiàn)f(37)=1,此時(shí)就和25的位置沖突。于是我們應(yīng)用上面的公式 f(37)=(f(37)+1) mod 12 =2 ,于是將37存入下標(biāo)為2的位置。 如下表

接下來22，29，15，47都沒有沖突，正常的存入，如下表。

到了 key=48， 我們計(jì)算得到f(48)=0,沖突，不要緊 ， f(48)=(f(48)+1) mod 12 =1 ，還是沖突。 再來， f(48)=(f(48)+2) mod 12 =2，沖突…，一直到 f(48)=(f(48)+6) mod 12 =6 時(shí) ，才有空位，機(jī)不可失，趕快存入，如下表。

我們把這種解決沖突的開放定址法稱為線性探索法。

從這個(gè)例子中我們也看到，在解決沖突的時(shí)候，還會(huì)碰到 如48和37這種本來都不是同義詞卻需要爭奪一個(gè)地址的情況，我們稱這種現(xiàn)象為堆積。很顯然，堆積的出現(xiàn)，使得我們需要不斷處理沖突，無論是存入還是查找效率都會(huì)大大降低。

考慮深一步，如果發(fā)生這樣的情況，當(dāng)最后一個(gè)key=34， f(key)=10 ,與22 所在的位置沖突，可是22后面沒有空位置了，反而它的前面有一個(gè)空位置，盡管可以不但求余數(shù)后得到結(jié)果，但效率很差。 因此我們可以改進(jìn) $d_i=1^2,?1^2,2^2,?2^2,...,q^2,?q^2(q\le m/2)$，這樣就等于時(shí)可以雙向?qū)ふ业娇赡艿目瘴恢谩?對(duì)于34來說，我們?nèi)i=-1即可找到空位置了。另外增加平方運(yùn)算的目的是為了不讓關(guān)鍵字都聚集在某一塊區(qū)域。我們稱這種方法為二次探測(cè)法。

還有一種方法是，在沖突時(shí)，對(duì)于位移量 di采用隨機(jī)函數(shù)得到，我們稱之為隨機(jī)探測(cè)法。

此時(shí)一定有人會(huì)問，既然是隨機(jī)，那么查找的時(shí)候不也隨機(jī)生成di嗎？ 如何可以獲得相同的地址？ 這是一個(gè)問題。這里的隨機(jī)其實(shí)是偽隨機(jī)數(shù)。 偽隨機(jī)數(shù)是說， 如果我們?cè)O(shè)置隨機(jī)種子相同，則不斷調(diào)用隨機(jī)函數(shù)可以生成不會(huì)重復(fù)的數(shù)列，我們?cè)诓檎視r(shí)，用同樣的隨機(jī)種子，它每次得到的數(shù)列是相同的，相同的di當(dāng)然可以得到相同的散列地址。

總之，開放定址法只要在散列表未滿時(shí)，總是能找到不發(fā)生沖突的地址，是我們常用的解決沖突的方法。

8.11.2 再散列函數(shù)法

對(duì)于我們的散列表來說，我們事先準(zhǔn)備多個(gè)散列函數(shù)。

這里RHi就是不同的散列函數(shù)，你可以把我們前面說的什么除留余數(shù)、折疊、平方取中全部用上。每當(dāng)發(fā)生散列地址沖突時(shí)，就換一個(gè)散列函數(shù)計(jì)算，相信總會(huì)有一個(gè)可以把沖突解決掉。這種方法能夠使得關(guān)鍵字不產(chǎn)生聚集，當(dāng)然，相應(yīng)地增加了計(jì)算的時(shí)間。

8.11.3 鏈地址法

思路還是可以再換一換，為什么有沖突就要換地方呢，我們直接就在原地想辦法不行嗎？ 于是我們就有了鏈地址法。

將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，我們稱這種表為同義詞子表，在散列表中只存儲(chǔ)所有 同義詞子表的頭指針。 對(duì)于關(guān)鍵字集合{12,67,56,16,25,37,22,29,15,47,48,34},我們用前面同樣的12為除數(shù)，進(jìn)行除留余數(shù)法，可以得到下圖的結(jié)構(gòu)，此時(shí)，已經(jīng)不存在什么沖突換址的問題，無論有多少個(gè)沖突，都只是在當(dāng)前位置給單鏈表增加結(jié)點(diǎn)。

鏈地址法對(duì)于可能會(huì)造成很多沖突的散列函數(shù)來說，提供了絕不會(huì)出現(xiàn)找不到地址的保證。當(dāng)然，這也就帶來了查找時(shí)需要遍歷單鏈表的性能損耗。

8.11.4 公共溢出區(qū)法

這個(gè)方法其實(shí)更好理解，你不是沖突嗎？好吧，凡是沖突的都跟我走，我給你們這些沖突找個(gè)地兒待著。這就如同孤兒院收留很多無家可歸的孩子一樣，我們?yōu)樗袥_突的關(guān)鍵字建立一個(gè)公共的溢出區(qū)來存放。

就前面的例子而言，我們共有三個(gè)關(guān)鍵字{37,48,34}以之前的關(guān)鍵字位置有沖突，那么就將它們存儲(chǔ)在溢出表，如下圖。

在查找時(shí)，對(duì)給定值通過散列函數(shù)計(jì)算出散列地址后，先與基本表的相應(yīng)位置進(jìn)行比對(duì)，如果相等，則查找成功；如果不相等，則到溢出表去進(jìn)行順序查找。如果相對(duì)于基本表而言，有沖突的數(shù)據(jù)很少的情況下，公共溢出區(qū)的結(jié)構(gòu)對(duì)查找性能來說還是非常高的。

8.12 散列表查找實(shí)現(xiàn)

說了這么多散列表查找的思想，我們就來看看查找的實(shí)現(xiàn)代碼

8.12.1 散列表查找算法實(shí)現(xiàn)

首先需要定義一個(gè)散列表的結(jié)構(gòu)以及一些相關(guān)的常數(shù)，其中HashTable就是散列表結(jié)構(gòu)。結(jié)構(gòu)當(dāng)中的elem為一個(gè)動(dòng)態(tài)數(shù)組。

#define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 #define NULLKEY -32768typedef struct{int *elem;// 數(shù)據(jù)元素存儲(chǔ)基址，動(dòng)態(tài)分配數(shù)組int count;//當(dāng)前數(shù)據(jù)元素個(gè)數(shù) }HashTable; int m=0;//散列表表長，全局變量

有了結(jié)構(gòu)的定義，我們可以對(duì)散列表進(jìn)行初始化

//初始化散列表Status InitHashTable(HashTable *H){int i;m=HASHSIZE;H->count=m;H->elem=(int *) malloc(m*sizeof(int));for(i=0;i<m;i++)H->elem[i]=NULLKEY;return OK;}

為了插入時(shí)計(jì)算地址，我們需要定義散列函數(shù)，散列函數(shù)可以根據(jù)不同情況更改算法。

int Hash( int key){return key % m; // 除留余數(shù)法 }

初始化完成后，我們可以對(duì)散列表進(jìn)行插入操作。假設(shè)我們要插入的關(guān)鍵字集合就是前面的{12,67,56,16,25,37,22,29,15,47,48,34}.

//插入關(guān)鍵字進(jìn)散列表void InsertHash(HashTable *H,int key){int addr=Hash(key); //求散列地址while( H->elem[addr] != NULLKEY) //如果不為空，表示沖突addr= (addr+1) %m; //開放定址法的線性探測(cè)H->elem[addr]=key;//直到有空位后插入關(guān)鍵字}

代碼中插入關(guān)鍵字時(shí)，首先算出散列地址，如果當(dāng)前地址不為空關(guān)鍵字，則說明有沖突。此時(shí)我們應(yīng)用開放定址法的線性探測(cè)進(jìn)行重新尋址，此時(shí)也可以更改為鏈地址法等其他解決沖突的方法。

散列表存在后，我們?cè)谛枰獣r(shí)就可以通過散列表查找要找的記錄。

//散列表查找關(guān)鍵字Status SearchHash(HashTable H, int key , int *addr){*addr=Hash(key); //求散列地址while( H.elem[*addr]!=key) { //如果不為空，有沖突*addr=(*addr+1) %m; //開放定址法的線性探測(cè)if(H.elem[*addr] == NULLKEY || *addr == Hash(key))return UNSUCCESS;//如果循環(huán)回到原點(diǎn)，則說明關(guān)鍵字不存在}return SUNCESS;}

8.12.2 散列表查找性能分析

最后，我們對(duì)散列表查找的性能做一個(gè)簡單的分析。如果沒有沖突，散列查找是我們本章介紹的所有查找里面效率最高的，散列查找時(shí)間復(fù)雜度為O(1),這是在沒有沖突的情況下。但是在實(shí)際情況下，沖突是不可避免的。那么散列查找的平均查找長度取決于哪些因素呢？

1 散列函數(shù)是否均勻
散列函數(shù)的好壞直接影響著出現(xiàn)沖突的頻繁程度，不過，由于不同的散列函數(shù)對(duì)同一組隨機(jī)的關(guān)鍵字，產(chǎn)生沖突的可能性是相同的，因此我們可以不考慮它對(duì)平均查找長度的影響。

2 處理沖突的方法

相同的關(guān)鍵字、相同的散列函數(shù)，但處理沖突的方法不同，會(huì)使得平均查找長度不同。比如線性探測(cè)處理沖突可能會(huì)產(chǎn)生堆積，顯然就沒有二次探測(cè)法好，而鏈地址法處理沖突不會(huì)產(chǎn)生任何堆積，因而具有更好的平均查找性能。

3 散列表的裝填因子

所謂的裝填因子 α =$\frac{填入表中的記錄個(gè)數(shù)}{散列表長度}$。 α標(biāo)志著散列表的裝滿程度。 當(dāng)填入表中的記錄越多，α就越大，產(chǎn)生沖突的可能性就越大。比如我們前面的例子，如圖8-11-5，如果你的散列表長度是12，而填入表中的記錄個(gè)數(shù)為11，那么此時(shí)的裝填因子α =11/12=0.9167，再填入最后一個(gè)關(guān)鍵字產(chǎn)生沖突的可能性就非常之大。 也就是說，散列表的平均查找長度取決于裝填因子，而不是取決于查找集合中的記錄個(gè)數(shù)。

不管記錄個(gè)數(shù)n有多大，我們總可以選擇一個(gè)合適的裝填因子以便將平均查找長度限定在一個(gè)范圍之內(nèi)，此時(shí)我們散列查找的時(shí)間復(fù)雜度就真的是O(1)了。為了做到這一點(diǎn)，通常我們都是將散列表的空間設(shè)置得比查找集合大，此時(shí)雖然浪費(fèi)了一定的空間，但換來的是查找效率的大大提升，總的來說，還是非常值得的。

散列函數(shù)測(cè)試代碼

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 100 /* 存儲(chǔ)空間初始分配量 */#define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 /* 定義散列表長為數(shù)組的長度 */ #define NULLKEY -32768 typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ typedef struct {int *elem; /* 數(shù)據(jù)元素存儲(chǔ)基址，動(dòng)態(tài)分配數(shù)組 */int count; /* 當(dāng)前數(shù)據(jù)元素個(gè)數(shù) */ }HashTable;int m=0; /* 散列表表長，全局變量 *//* 初始化散列表 */ Status InitHashTable(HashTable *H) {int i;m=HASHSIZE;H->count=m;H->elem=(int *)malloc(m*sizeof(int));for(i=0;i<m;i++)H->elem[i]=NULLKEY; return OK; }/* 散列函數(shù) */ int Hash(int key) {return key % m; /* 除留余數(shù)法 */ }/* 插入關(guān)鍵字進(jìn)散列表 */ void InsertHash(HashTable *H,int key) {int addr = Hash(key); /* 求散列地址 */while (H->elem[addr] != NULLKEY) /* 如果不為空，則沖突 */{addr = (addr+1) % m; /* 開放定址法的線性探測(cè) */}H->elem[addr] = key; /* 直到有空位后插入關(guān)鍵字 */ }/* 散列表查找關(guān)鍵字 */ Status SearchHash(HashTable H,int key,int *addr) {*addr = Hash(key); /* 求散列地址 */while(H.elem[*addr] != key) /* 如果不為空，則沖突 */{*addr = (*addr+1) % m; /* 開放定址法的線性探測(cè) */if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循環(huán)回到原點(diǎn) */return UNSUCCESS; /* 則說明關(guān)鍵字不存在 */}return SUCCESS; }int main() {int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};int i,p,key,result;HashTable H;key=39;InitHashTable(&H);for(i=0;i<m;i++)InsertHash(&H,arr[i]);result=SearchHash(H,key,&p);if (result)printf("查找 %d 的地址為：%d \n",key,p);elseprintf("查找 %d 失敗。\n",key);for(i=0;i<m;i++){key=arr[i];SearchHash(H,key,&p);printf("查找 %d 的地址為：%d \n",key,p);}return 0; }

測(cè)試結(jié)果

查找 39 失敗。 查找 12 的地址為：0 查找 67 的地址為：7 查找 56 的地址為：8 查找 16 的地址為：4 查找 25 的地址為：1 查找 37 的地址為：2 查找 22 的地址為：10 查找 29 的地址為：5 查找 15 的地址為：3 查找 47 的地址為：11 查找 48 的地址為：6 查找 34 的地址為：9

總結(jié)

以上是生活随笔為你收集整理的《大话数据结构》读书笔记-查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。