Jiang's C++ Space

這篇將是最有難度和挑戰性的一篇，做好心理準備！

十、二叉查找樹（BST）

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

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

刪除則稍微麻煩點，因為我們刪的不一定是葉子，如果只是葉子，那就好辦，如果不是呢？我們最通常的做法就是把這個節點往下挪，直到它變為葉子為止，看圖。

也許你要問，如果和左子樹最大節點交換后，要刪除的節點依然不是葉子，那怎么辦呢？那繼續唄，看圖：

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

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

前面說了，二叉查找樹方便查找取值插入刪除，其復雜度不過為Ο(logn)，但這是個“期望值”，因為我們也有比較差的情況，比如下面這棵樹：

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

平衡，顧名思義，就是兩邊看起來比較對稱，但很多時候我們是做不到絕對的對稱（絕對對稱即對任意子樹而言，左右節點的數量都相等），因為只有(2^n-1)元素數目的二叉樹才能做到絕對對稱，所以我們使用了“高度”（height）這么個概念，某節點的高度指的是它離它的子樹的葉子的最遠距離：

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

那我們就可以給AVL下個定義了，對AVL的任意節點而言：

ABS(左高 - 右高) <= 1

做到了這點，這棵樹看起來就比較平衡了，如何生成一棵AVL樹呢？算法十分不簡單，那我們先通過圖來獲得一些最直觀的認識，就先按1，2，3，4……這樣的自然數順序加入到樹中，下圖體現出了樹的構造變化：

隨著新節點的加入，樹自動調整自身結構，達到新的平衡狀態，這就是我們想要的AVL樹。我們先要分析，為什么樹會失衡？是由于插入了一個元素，對吧，那我們能不能把不同的插入情況全部概括起來并作出統一的調整來使得樹重新平衡？答案是肯定的，也有人幫我們研究好了，只是證明這個過程需要一些數學功底，我是不行的了，所以直接給出算法示意圖和范例。

LL型調整：

再給一個LL型調整的實例：

RR型調整，其實就是LL型調整的鏡像而已：

這是一個RR型調整的實例：

接下去就是LR型調整：

這是一個LR型調整的實例：

RL型調整是LR型調整的鏡像，所以不再畫圖了。

至于如何選擇不同的調整類型，我后面將給出代碼，看“DoBalance”這個函數的實現，很清晰的。那接下去我們還要面臨一個比較困難的問題，就是刪除及刪除平衡，因為不光是插入元素可能導致不平衡，刪除也會。不過我們都有個同樣的前提，就是無論是插入前還是刪除前的二叉樹，都是平衡的。

我參考的書上說刪除和插入其實是很類似的，具體實現卻沒說，我后來寫代碼蠻辛苦的，最后發現確實差別不大，但在調整相關節點高度的時候確實有點細微上的差別，這個在我的代碼里也能看得出來。下面我就給出我的代碼，我已經通過了初步的測試，不過也許代碼還有bug，如果發現了，請留言。

代碼比較長，其中還利用了之前的堆棧和隊列結構，可以算是復習，如果覺得代碼晦澀難懂，也可以跳過，有些怕自己的代碼寫得不夠好……

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