（1）樹高和性能的關系

二叉查找樹的查找，插入，刪除的時間復雜度為O(logn),但這是在期望的情況下。最好的情況和最壞情況差別較大。

（2）理想平衡和適度平衡

首先分析在最好的情況下，每次一分為二，左右子樹的結點數(shù)均為n/2, 左右子樹的高度也一樣，也就是說如果把左右子樹放到天平上，是平衡的，如下圖所示：

在理想狀態(tài)下，數(shù)的高度為logn,左右子樹的高度一樣，稱為理想平衡，但是理想平衡需要大量時間調(diào)整平衡以維護其嚴格的平衡性。

那么可以適度放松平衡的標準，大致平衡就可以了，稱為適度平衡。

平衡二叉查找樹（Balanced Binary Search Tree,BBST），簡稱平衡二叉樹，由前蘇聯(lián)數(shù)學家Adelson-Velskii 和Landis提出，所以又稱為AVL樹。

平衡二叉樹或者為空樹，或者為具有以下性質(zhì)的平衡二叉樹：

1）左右子樹高度差的絕對值不超過1；

2）左右子樹也是平衡二叉樹；

結點為左右子樹的高度之差稱為平衡因子。二叉查找樹中，每一個結點的平衡因子絕對值不超過1即為二叉樹。例如，一個平衡二叉樹及其平衡因子，如下圖所示：

那么在這顆平衡二叉樹中插入20，結果會怎么樣？如下圖所示。插入20后，從該葉子到樹根路徑上的所有結點，平衡因子都有可能改變，出現(xiàn)不平衡，有可能有多個結點平衡因子絕對值超過1。從新插入結點向上，找距離新插入結點最近的不平衡結點，以該結點為根的子樹稱為最小不平衡子樹。只需要將最小不平衡子樹調(diào)整為二叉樹即可，其他結點不變。

平衡二叉樹除了適度平衡性還有局部性：

1）單次插入，刪除后，至多有O(1)處出現(xiàn)不平衡；

2）總可以在O(logn)時間內(nèi)，使這O(1)處不平衡重新調(diào)整為平衡。

平衡二叉樹在動態(tài)修改后出現(xiàn)的不平衡，只需要局部（最小不平衡樹）調(diào)平衡即可，不需要整棵樹調(diào)整。

那么如何局部調(diào)平衡呢？

?調(diào)整平衡的方法：以插入操作為例，調(diào)整平衡可以分為四種情況：LL型，RR型，LR型，RL型。（L和R分別代表左右子樹）

補：判斷不平衡類型時，沿著高度大的子樹走

每次旋轉總有一個子樹被拋棄，一個指針空閑，它們正好配對。旋轉之后，是否平衡呢？旋轉之后，A,B兩個結點的左右子樹高度之差均為0，滿足平衡條件，C的左右子樹未變，仍然平衡。代碼實現(xiàn)：

代碼實現(xiàn)：

代碼實現(xiàn)：

代碼實現(xiàn)：

1.平衡二叉樹的插入

在平衡二叉樹上插入新的數(shù)據(jù)元素x，首先查找其插入位置，查找過程中，用p指針記錄當前結點，f指針記錄p的雙親，其算法描述如下。

算法步驟：

1）在平衡二叉樹查找x，如果查找成功，則什么也不做，返回p；如果查找失敗，則執(zhí)行插入操作。

2) 創(chuàng)建一個新結點p存儲x,該結點的雙親為f,高度為1。

3）從新結點之父f出發(fā)，向上尋找最近的不平衡結點。逐層檢查各代祖先結點，，如果平衡，則更新其高度，繼續(xù)向上尋找；如果不平衡，則判斷失衡類型（沿著高度大的子樹判斷，剛插入新結點的子樹必然高度大），并作相應的調(diào)整，返回p。

2.平衡二叉樹的創(chuàng)建

平衡二叉樹的創(chuàng)建和二叉查找樹的創(chuàng)建類似，只是插入操作多了調(diào)平衡而已。可以從空樹開始，按照輸入關鍵字的順序依次進行插入操作，最終得到一顆平衡二叉樹。

算法步驟：

1）初始化平衡二叉樹為空，T = NULL;

2) 輸入一個關鍵字x,將x插入到平衡二叉樹T中；

3） 重復步驟2）,直到關鍵字輸入完畢。

3.平衡樹的刪除

平衡二叉樹的插入只需要從插入結點之父向上檢查，發(fā)現(xiàn)不平衡立即調(diào)整，一次調(diào)平衡即可。而刪除操作則需要一直從刪除結點之父向上檢查，發(fā)現(xiàn)不平衡立即調(diào)整，然后繼續(xù)向上檢查，檢查到樹根為止。

算法步驟：

1）在平衡二叉樹查找x,如果查找失敗，則返回；如果查找成功，則執(zhí)行刪除操作（同二叉查找樹的刪除）;

2) 從實際被刪除結點之父g出發(fā)（當被刪除結點有左右子樹時，令其直接前驅（或直接后繼）代替其位置，刪除其直接前驅，實際被刪結點為其直接前驅（或直接后繼）），向上尋找最近的不平衡結點。逐層檢查各代祖先結點，如果平衡，則更新其高度，繼續(xù)向上尋找；如果不平衡，則判斷失衡類型（沿著高度大的子樹判斷），并作相應的調(diào)整。

3）繼續(xù)向上檢查，一直到樹根。