解晨

摘要：計(jì)算機(jī)最廣為人知的優(yōu)點(diǎn)之一是其能儲(chǔ)存大量的數(shù)據(jù)，如今隨著時(shí)代的發(fā)展，儲(chǔ)存容量更是猶如日進(jìn)千里一般極速擴(kuò)展，大容量的硬盤、U盤早已隨處可見。然而，要在巨大的數(shù)據(jù)中搜索出需要的內(nèi)容卻不是一件容易的事，由此，為了能減少在搜索儲(chǔ)存數(shù)據(jù)上的開銷，各種適應(yīng)于不同訪問搜索背景的數(shù)據(jù)結(jié)構(gòu)應(yīng)運(yùn)而生。樹，便是計(jì)算機(jī)學(xué)科中最基本的數(shù)據(jù)結(jié)構(gòu)之一，提供了快速的儲(chǔ)存和訪問性能。該文探究了帶有平衡條件的二叉查找樹——AVL樹的原理，并對(duì)其使用C語言進(jìn)行了實(shí)現(xiàn)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；平衡二叉查找樹；AVL樹

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）07-1532-04

對(duì)于大量的輸入數(shù)據(jù)，普通的線性數(shù)據(jù)結(jié)構(gòu)訪問時(shí)間太慢，例如，對(duì)于一個(gè)有N個(gè)數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)，假設(shè)對(duì)每個(gè)數(shù)據(jù)的訪問幾率大致相同，每個(gè)數(shù)據(jù)每次訪問有1/N的機(jī)會(huì)被訪問，由于是線性數(shù)據(jù)，因此每個(gè)數(shù)據(jù)的訪問花銷可以經(jīng)過一定的排列，最通常的是訪問第一個(gè)數(shù)據(jù)花銷1個(gè)單位時(shí)間，第二個(gè)2個(gè)單位時(shí)間，第三個(gè)3各單位時(shí)間……第N個(gè)N各單位時(shí)間，于是訪問一次的平均花銷為（N+[N2]）/2N = （1+N）/ 2，用計(jì)算機(jī)專業(yè)的符號(hào)來說，其訪問運(yùn)行時(shí)間可以用O（N）來表示，即訪問一次線性數(shù)據(jù)結(jié)構(gòu)的花銷在N這個(gè)數(shù)量級(jí)上。使用樹這一數(shù)據(jù)結(jié)構(gòu)可將訪問花銷將至logN這個(gè)數(shù)量級(jí)上，也即O（logN），這里logN是以二為底的N的對(duì)數(shù)?？梢詫?duì)比一下，若N=1267650600228229401496703205376，則logN=100。數(shù)字越大，則O（N）與O（logN）相差越大。

一般來說，計(jì)算機(jī)學(xué)科中使用的最基本的樹為二叉查找樹，下圖是一顆二叉樹的簡單示意圖：

圖1 二叉樹示意圖

二叉查找樹則是在二叉樹的基礎(chǔ)上得來。假設(shè)在一顆二叉樹中，每個(gè)節(jié)點(diǎn)都有一個(gè)關(guān)鍵詞值，并且關(guān)鍵詞值都是互異且可以比較，若對(duì)于此二叉樹中的每個(gè)節(jié)點(diǎn)，其左子樹中所有節(jié)點(diǎn)的關(guān)鍵詞值小于其本身關(guān)鍵詞值，其右子樹中所有關(guān)鍵詞值大于其本身關(guān)鍵詞值，則此二叉樹為二叉查找樹。

AVL樹，則是最先發(fā)明的帶有平衡條件的二叉查找樹。

下面，就讓我們來分析一下AVL樹的思想和原理。

1 AVL樹思想和原理

正如上所述，AVL樹是一種帶有平衡條件的二叉查找樹。那么，這個(gè)平衡條件是什么呢？

對(duì)于二叉查找樹這樣的數(shù)據(jù)結(jié)構(gòu)來說，由于其節(jié)點(diǎn)有著按順序排列的性質(zhì)，若有數(shù)據(jù)往此數(shù)據(jù)結(jié)構(gòu)中插入，則可能會(huì)引起樹的高度過高，使得訪問數(shù)據(jù)的花銷可能會(huì)比應(yīng)有的要多。

例如，對(duì)于只有一個(gè)節(jié)點(diǎn)X的二叉查找樹，若此后往樹中插入的元素其關(guān)鍵詞值皆小于X的關(guān)鍵詞值，那么這棵樹的左子樹就會(huì)越來越龐大，最終訪問一個(gè)比X小得多的數(shù)據(jù)可能會(huì)花費(fèi)相當(dāng)多的開銷，而如果在插入數(shù)據(jù)到一定程度時(shí)選擇X的左子樹中適當(dāng)?shù)墓?jié)點(diǎn)作為根節(jié)點(diǎn)，則情況會(huì)好得多。

如上所述的即是平衡條件，即使得樹的深度不致過于深，讓左子樹和右子樹的高度相差不宜過大。同時(shí)，從應(yīng)用的角度來說，這個(gè)平衡條件必須容易實(shí)現(xiàn)，并且應(yīng)該允許能夠易如反掌地對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行如插入數(shù)據(jù)、刪除數(shù)據(jù)這樣的常見操作。

1.1 AVL樹的思想與原理

對(duì)于一顆AVL樹來說，其平衡條件是要求其每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度最多差一。例如，在圖2中，左邊的樹為AVL樹，右邊的則不是：

據(jù)資料顯示，一個(gè)AVL樹的高度平均來說只有1.44log（N+2） – 1.328，并且其實(shí)際上的高度只比logN多一點(diǎn)，這樣的訪問花銷是比較高效的。

那么，AVL樹是如何實(shí)現(xiàn)這個(gè)平衡條件的呢？很幸運(yùn)，這個(gè)解決方法并不難。事實(shí)上，我們是可以通過足夠簡單的對(duì)樹的修改來做到。

1.2 AVL樹的旋轉(zhuǎn)操作

在對(duì)一顆AVL樹進(jìn)行插入數(shù)據(jù)或者刪除數(shù)據(jù)的操作時(shí)，我們通過一種稱之為“旋轉(zhuǎn)”的操作來保持樹的左右子樹之差。由于對(duì)像二叉查找樹這樣本身已經(jīng)包含排列性質(zhì)的數(shù)據(jù)結(jié)構(gòu)的修改，一般來說只有插入數(shù)據(jù)和刪除數(shù)據(jù)是常用的，所以在這作者只使用插入數(shù)據(jù)來分析AVL樹的旋轉(zhuǎn)操作，刪除數(shù)據(jù)可以依理推知。

同時(shí)，由于插入節(jié)點(diǎn)后，只有那些從插入點(diǎn)到根節(jié)點(diǎn)路徑上的節(jié)點(diǎn)的平衡性會(huì)改變，所以在對(duì)樹進(jìn)行操作以更新平衡時(shí)，能找到這樣一個(gè)節(jié)點(diǎn)，它破壞了平衡性，但是可以對(duì)它進(jìn)行操作使得樹重新變得平衡。

現(xiàn)在假設(shè)這個(gè)破換平衡的節(jié)點(diǎn)為W?？芍鶕?jù)AVL樹的定義可知，此時(shí)W的左子樹和右子樹的高度差為二，并且這種造成不平衡的插入操作會(huì)有如下四種情況：

1）對(duì)W的左兒子的左子樹進(jìn)行一次插入；

2）對(duì)W的右兒子的右子樹進(jìn)行一次插入；

3）對(duì)W的左兒子的右子樹進(jìn)行一次插入；

4）對(duì)W的右兒子的左子樹進(jìn)行一次插入。

可以看出，1）和2）是一個(gè)鏡像關(guān)系，3）和4）也是一個(gè)鏡像關(guān)系，因此，從理論的角度來說實(shí)際上只有兩種情況。

對(duì)于1）和2）的情形，可以使用“單旋轉(zhuǎn)”來恢復(fù)平衡。

單旋轉(zhuǎn)的操作示意圖如下：

可以看到，在這個(gè)示意圖中，節(jié)點(diǎn)k2扮演著W的角色，其左子樹與右子樹的高度差為2，并且再插入包含新數(shù)據(jù)的新節(jié)點(diǎn)之前，k2滿足AVL樹的平衡條件。于是為了恢復(fù)平衡，對(duì)k1和k2及其左右子樹進(jìn)行操作。在示意圖中，是以k1取代k2作為根節(jié)點(diǎn)，將Y變成了k2的左子樹，并將此時(shí)的k2作為k1的右兒子。

對(duì)于其鏡像情形的操作也是一樣，在此就不贅述。

而對(duì)于3）和4）的情形，則必須使用雙旋轉(zhuǎn)操作來保持樹的平衡。例如，可以根據(jù)如下示意圖來說明：

在這個(gè)情形中，對(duì)于以k1為根節(jié)點(diǎn)的樹來說，其高度比樹D多二，問題發(fā)生在k1的右子樹，更準(zhǔn)確的說，是發(fā)生在B或C，具體哪個(gè)不要緊，因?yàn)槎加锌赡埽源颂帉和C畫得一樣高。

對(duì)于這種情形，可以像示意圖那樣改變根節(jié)點(diǎn)，并且將k1、k2、k3的左右子樹進(jìn)行交換而使樹重新得到平衡。

對(duì)于其鏡像情況也可以使用相同的技巧使樹的平衡得到保持，在此就不贅述。

可以看出，對(duì)于這兩種情況，一次旋轉(zhuǎn)足以解決問題，因此，其效率能夠在接受的范圍之內(nèi)，并且易于實(shí)現(xiàn)。

下面，作者使用C語言對(duì)AVl樹這一數(shù)據(jù)結(jié)構(gòu)進(jìn)行了實(shí)現(xiàn)。

2 AVL樹的C語言實(shí)現(xiàn)

作者使用C語言對(duì)AVL樹的節(jié)點(diǎn)、獲取節(jié)點(diǎn)所在高度函數(shù)、數(shù)據(jù)節(jié)點(diǎn)的插入函數(shù)、左右單旋轉(zhuǎn)函數(shù)、左右雙旋轉(zhuǎn)函數(shù)以及以中序遍歷在屏幕上顯示節(jié)點(diǎn)信息函數(shù)等進(jìn)行了實(shí)現(xiàn)。

2.1 AVL樹節(jié)點(diǎn)實(shí)現(xiàn)

由前文分析可知，要實(shí)現(xiàn)的AVL樹節(jié)點(diǎn)包含四個(gè)元素，即節(jié)點(diǎn)的關(guān)鍵詞值，指向左兒子的指針以及指向右兒子的指針，此外，還需有一個(gè)記錄節(jié)點(diǎn)高度的元素用以判斷平衡狀態(tài)?？梢允褂靡粋€(gè)結(jié)構(gòu)來表示節(jié)點(diǎn)，其源代碼如下：

2.2 AVL樹獲取節(jié)點(diǎn)高度函數(shù)實(shí)現(xiàn)

獲取節(jié)點(diǎn)的高度比較容易，只需返回節(jié)點(diǎn)中保存的高度信息即可，唯一要注意的是若是一顆空樹，則返回-1這個(gè)高度。源代碼如下：

2.3 AVL樹插入元素函數(shù)實(shí)現(xiàn)

向AVL樹中插入元素即使用一般的向二叉查找樹中插入元素的操作即可，唯一要注意的是需修改節(jié)點(diǎn)高度信息，若平衡被破壞則使用兩種旋轉(zhuǎn)對(duì)樹進(jìn)行修改。其源代碼如下：

2.4 左右單旋轉(zhuǎn)函數(shù)實(shí)現(xiàn)

左右單旋轉(zhuǎn)函數(shù)的過程可以按上文所分析的來實(shí)現(xiàn)，左右單旋轉(zhuǎn)只是互為鏡像。

右單旋轉(zhuǎn)的源代碼如下：

2.5 左右雙旋轉(zhuǎn)函數(shù)實(shí)現(xiàn)。

從上文中的分析可知，雙旋轉(zhuǎn)可以看成兩次使用單旋轉(zhuǎn)，因此，雙旋轉(zhuǎn)函數(shù)可以調(diào)用兩次相對(duì)應(yīng)的單旋轉(zhuǎn)函數(shù)來實(shí)現(xiàn)。

右雙旋轉(zhuǎn)函數(shù)源代碼如下：

2.6 中序遍歷函數(shù)實(shí)現(xiàn)

中序遍歷是一種常用的遍歷樹這一數(shù)據(jù)結(jié)構(gòu)的方法。此順序先訪問節(jié)點(diǎn)中的信息，再遞歸訪問節(jié)點(diǎn)左子樹中節(jié)點(diǎn)的信息，最后遞歸訪問右子樹節(jié)點(diǎn)中的信息。

其源代碼如下：

以上，便是作者使用C語言實(shí)現(xiàn)的有關(guān)AVL樹的所有源代碼，其他操作如刪除元素等可以依原理推知。

3 總結(jié)

本文分析了AVL樹的思想與原理，并根據(jù)其特點(diǎn)，結(jié)合C語言的特性，對(duì)AVL樹和一系列的操作進(jìn)行了實(shí)現(xiàn)。

AVL樹是最早出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)之一，大大提高了訪問數(shù)據(jù)的效率，也為以后數(shù)據(jù)結(jié)構(gòu)的發(fā)展起著開拓性的作用。雖然如今計(jì)算機(jī)的性能越來越匪夷所思，計(jì)算速度簡直無法想象，訪問速度早已大有提升，但毫無疑問，使用良好的數(shù)據(jù)結(jié)構(gòu)依然對(duì)提高訪問速度有著舉足輕重的作用。

參考文獻(xiàn)：

[1] Robert Sedgewick.算法：C語言實(shí)現(xiàn)[M].北京：機(jī)械工業(yè)出版，2009.

[2] Ellis Horowitz，Sartaj Sahni，Susan Anderson-Freed.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：機(jī)械工業(yè)出版社，2006.

[3] Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析[M]. 北京：人民郵電出版社，2005.

[4] Sesh Venugopal.數(shù)據(jù)結(jié)構(gòu)：從應(yīng)用到實(shí)現(xiàn)（Java版）[M]. 北京：機(jī)械工業(yè)出版社，2008.

[5] Adam Drozdek.數(shù)據(jù)結(jié)構(gòu)與算法：Java語言版 [M]. 2版.北京：機(jī)械工業(yè)出版社，2006.