STL關聯式容器（二）

平衡二叉搜尋樹

也許因為輸入值不夠随機，也許因為經過某些插入或删除操作，二叉搜尋樹可能會失去平衡造成搜尋效率低落的情況：

所謂樹形平衡與否，并沒有一個絕對的标準。“平衡”的大緻意義是：沒有任何一個節點過深或深度過大。不同的平衡條件，造成不同的效率表現，以及不同的實作複雜度。有數種特殊結構如AVL-tree、RB-tree、AA-tree，均可實作出平衡二叉搜尋樹，它們都比一般的（無法絕對維持平衡的）二叉搜尋樹複雜。是以，插入節點和删除節點的平均時間也比較長，但是它們總是保持某種程度的平衡，是以元素的通路（搜尋）時間平均而言也就比較少。

AVL tree（Adelson-Velskii-Landis tree）

AVL tree是一個“加上了額外平衡條件”的二叉搜尋樹。其平衡條件的建立是為了確定整棵樹的深度為O(log N)。直覺上的最佳平衡條件是每個節點的左右子樹有着相同的高度，但這未免太過嚴苛，我們很難插入新元素而又保持這樣的平衡條件。AVL tree于是退而求其次，要求任何節點的左右子樹高度相差最多1。這是一個較弱的條件，但仍能夠保證“對數深度（logarithmic depth）”平衡狀态。

下圖所示是一個AVL tree，插入節點11後，灰色節點違反AVL tree 的平衡條件。由于隻有“插入點至根節點”路徑上的各節點可能改變平衡狀态，是以，隻要調整其中最深的那個節點，便可使整棵樹重新獲得平衡。

前面說過，隻要調整“插入點至根節點”路徑上，平衡狀态被破壞至各節點中最深的那一個，便可使整棵樹重新獲得平衡。假設該最深節點為X，由于節點多擁有兩個子節點，而所謂“平衡被破壞”意味着X的左右兩棵子樹的高度相差2，是以我們可以輕易将情況分四種：

1. 插入點位于X的左子節點的左子樹——左左；
2. 插入點位于X的左子節點的右子樹——左右；
3. 插入點位于X的右子節點的左子樹——右左；

4. 插入點位于X的右子節點的右子樹——右右；

   情況1、4對稱，稱為外側插入（outside）插入，可以采用單旋轉操作（single rotation）調整解決。情況2,3彼此對稱，稱為内側（inside）插入，可以采用雙旋轉操作（double rotation）調整解決。

   

   單旋轉（Single Rotation）

   在外側插入狀态，k2“插入前平衡，插入後不平衡”的唯一情況如下圖左側所示。A子樹成長了一層，緻使它比C子樹的深度多2.B子樹不可能和A子樹位于同一層，否則k2在插入前就處于不平衡狀态了。B子樹也不可能和C子樹位于同一層，否則第一個違反平衡條件的将是k1而不是k2.

   

   為了調整平衡狀态，我們希望将A子樹提高一層，并将C子樹下降一層。這已經比AVL tree所要求的平衡條件更進一步了，上圖右側為調整後的情況。我們可以這麼想象，把k1提起，使k2自然下滑，并将B子樹挂在k2的左側。這麼做是因為，二叉搜尋樹的規則使我們知道，k2>k1,是以k2必須成為新樹形中的k1的右子節點。二叉搜尋樹的規則也告訴我們，B子樹的所有節點的鍵值都在k1和k2之間，是以新樹形中的B子樹必須落在k2的左側。

   雙旋轉（Double Rotation）

   下圖左側為内側插入所造成的不平衡狀态，單旋轉無法解決這種情況。一是我們不能再以k3為根節點，其次，我們不能将k3和k1做一次單旋轉，因為旋轉之後還是不平衡。唯一的可能是以k2為新的根節點，這使得k1必須為k2的左子節點，k3必須成為k2的右子節點，而這麼一來也就完全決定了四個子樹的位置。新的樹形滿足AVL-tree的平衡條件，并且，就像單旋轉的情況一樣，它恢複了節點插入之前的高度，是以，保證不再需要任何調整：