這篇將是最有難度和挑戰(zhàn)性的一篇，做好心理準(zhǔn)備！

十、二叉查找樹（BST）

前一篇介紹了樹，卻未介紹樹有什么用。但就算我不說(shuō)，你也能想得到，看我們Windows的目錄結(jié)構(gòu)，其實(shí)就是樹形的，一個(gè)典型的分類應(yīng)用。當(dāng)然除了分類，樹還有別的作用，我們可以利用樹建立一個(gè)非常便于查找取值又非常便于插入刪除的數(shù)據(jù)結(jié)構(gòu)，這就是馬上要提到的二叉查找樹（Binary Search Tree），這種二叉樹有個(gè)特點(diǎn)：對(duì)任意節(jié)點(diǎn)而言，左子（當(dāng)然了，存在的話）的值總是小于本身，而右子（存在的話）的值總是大于本身。

這種特性使得我們要查找其中的某個(gè)值都很容易，從根開始，小的往左找，大的往右找，不大不小的就是這個(gè)節(jié)點(diǎn)了；插入一樣的道理，從根開始，小的往左，大的往右，直到葉子，就插入，算法比較簡(jiǎn)單，不一一列了，它們的時(shí)間復(fù)雜度期望為Ο(logn)。（為什么是“期望”，后面會(huì)講）

刪除則稍微麻煩點(diǎn)，因?yàn)槲覀儎h的不一定是葉子，如果只是葉子，那就好辦，如果不是呢？我們最通常的做法就是把這個(gè)節(jié)點(diǎn)往下挪，直到它變?yōu)槿~子為止，看圖。

也許你要問(wèn)，如果和左子樹最大節(jié)點(diǎn)交換后，要?jiǎng)h除的節(jié)點(diǎn)依然不是葉子，那怎么辦呢？那繼續(xù)唄，看圖：

那左子樹不存在的情況下呢？你可以查找右子樹的最小節(jié)點(diǎn)，和上面是類似的，圖我就不畫了。

十一、平衡二叉查找樹（AVL）

前面說(shuō)了，二叉查找樹方便查找取值插入刪除，其復(fù)雜度不過(guò)為Ο(logn)，但這是個(gè)“期望值”，因?yàn)槲覀円灿斜容^差的情況，比如下面這棵樹：

說(shuō)是樹，其實(shí)已經(jīng)退化為鏈表了，但從概念上來(lái)說(shuō)它依然是一棵二叉查找樹，這棵樹怎么形成的呢？很簡(jiǎn)單，我們只要按著1，2，3，4，5，6，7這樣的順序往一個(gè)空的二叉查找樹里添加元素，就形成了。這樣我們?cè)偬砑?，9，10……那真的就變成了一個(gè)鏈表結(jié)構(gòu)，那插入的復(fù)雜度也就變成了Ο(n)。導(dǎo)致這種糟糕的原因是這棵樹非常不平衡，右樹的重量遠(yuǎn)大于左樹，所以我們提出了一種叫“平衡二叉查找樹”的結(jié)構(gòu)，平衡二叉查找樹英文叫AVL，而不是我本來(lái)以為的什么Balance BST，AVL來(lái)自于人名，我這里就不追究了。

平衡，顧名思義，就是兩邊看起來(lái)比較對(duì)稱，但很多時(shí)候我們是做不到絕對(duì)的對(duì)稱（絕對(duì)對(duì)稱即對(duì)任意子樹而言，左右節(jié)點(diǎn)的數(shù)量都相等），因?yàn)橹挥?2^n-1)元素?cái)?shù)目的二叉樹才能做到絕對(duì)對(duì)稱，所以我們使用了“高度”（height）這么個(gè)概念，某節(jié)點(diǎn)的高度指的是它離它的子樹的葉子的最遠(yuǎn)距離：

那么我再引申出兩個(gè)概念，左高和右高：
左高 = 左節(jié)點(diǎn)空 ? 0 : (左節(jié)點(diǎn)高+1)
右高 = 右節(jié)點(diǎn)空 ? 0 : (右節(jié)點(diǎn)高+1)

那我們就可以給AVL下個(gè)定義了，對(duì)AVL的任意節(jié)點(diǎn)而言：

ABS(左高 - 右高) <= 1

做到了這點(diǎn)，這棵樹看起來(lái)就比較平衡了，如何生成一棵AVL樹呢？算法十分不簡(jiǎn)單，那我們先通過(guò)圖來(lái)獲得一些最直觀的認(rèn)識(shí)，就先按1，2，3，4……這樣的自然數(shù)順序加入到樹中，下圖體現(xiàn)出了樹的構(gòu)造變化：

隨著新節(jié)點(diǎn)的加入，樹自動(dòng)調(diào)整自身結(jié)構(gòu)，達(dá)到新的平衡狀態(tài)，這就是我們想要的AVL樹。我們先要分析，為什么樹會(huì)失衡？是由于插入了一個(gè)元素，對(duì)吧，那我們能不能把不同的插入情況全部概括起來(lái)并作出統(tǒng)一的調(diào)整來(lái)使得樹重新平衡？答案是肯定的，也有人幫我們研究好了，只是證明這個(gè)過(guò)程需要一些數(shù)學(xué)功底，我是不行的了，所以直接給出算法示意圖和范例。

LL型調(diào)整：

再給一個(gè)LL型調(diào)整的實(shí)例：

RR型調(diào)整，其實(shí)就是LL型調(diào)整的鏡像而已：

這是一個(gè)RR型調(diào)整的實(shí)例：

接下去就是LR型調(diào)整：

這是一個(gè)LR型調(diào)整的實(shí)例：

RL型調(diào)整是LR型調(diào)整的鏡像，所以不再畫圖了。

至于如何選擇不同的調(diào)整類型，我后面將給出代碼，看“DoBalance”這個(gè)函數(shù)的實(shí)現(xiàn)，很清晰的。那接下去我們還要面臨一個(gè)比較困難的問(wèn)題，就是刪除及刪除平衡，因?yàn)椴还馐遣迦朐乜赡軐?dǎo)致不平衡，刪除也會(huì)。不過(guò)我們都有個(gè)同樣的前提，就是無(wú)論是插入前還是刪除前的二叉樹，都是平衡的。

我參考的書上說(shuō)刪除和插入其實(shí)是很類似的，具體實(shí)現(xiàn)卻沒(méi)說(shuō)，我后來(lái)寫代碼蠻辛苦的，最后發(fā)現(xiàn)確實(shí)差別不大，但在調(diào)整相關(guān)節(jié)點(diǎn)高度的時(shí)候確實(shí)有點(diǎn)細(xì)微上的差別，這個(gè)在我的代碼里也能看得出來(lái)。下面我就給出我的代碼，我已經(jīng)通過(guò)了初步的測(cè)試，不過(guò)也許代碼還有bug，如果發(fā)現(xiàn)了，請(qǐng)留言。

代碼比較長(zhǎng)，其中還利用了之前的堆棧和隊(duì)列結(jié)構(gòu)，可以算是復(fù)習(xí)，如果覺得代碼晦澀難懂，也可以跳過(guò)，有些怕自己的代碼寫得不夠好……

另附帶一些代碼說(shuō)明：
1，TreeNode目前只帶一個(gè)“數(shù)據(jù)”，就是iData，所以交換節(jié)點(diǎn)位置時(shí)候，為了方便，只需要交換這個(gè)數(shù)據(jù)；
2，代碼中的pMinBST指向的是“最小不平衡樹”，即：從插入或刪除的位置開始往上查找出現(xiàn)的第一個(gè)不平衡的節(jié)點(diǎn)；
3，“往上查找”就需要借助一個(gè)Stack結(jié)構(gòu)；
4，AVL樹的析構(gòu)采用了后序遍歷，由于是析構(gòu)，之后不再用到，所以后序遍歷時(shí)候改變了節(jié)點(diǎn)指針的值，后續(xù)遍歷使用了Queue結(jié)構(gòu)；
5，刪除節(jié)點(diǎn)時(shí)候，尋找并交換葉子節(jié)點(diǎn)的操作有些晦澀，往左尋找最大節(jié)點(diǎn)，為什么找到了最大并交換，而它還不是葉子的時(shí)候，我只需要再往左找并交換一次就可以了呢？因?yàn)槲覄h除到時(shí)候有個(gè)前提：這棵樹是平衡的，往右尋找最小節(jié)點(diǎn)的道理跟這個(gè)一樣的；
6，有什么問(wèn)題請(qǐng)留言。