平衡二叉樹之一（基本性質、查詢、添加） .

平衡二叉樹（Balanced BinaryTree）又被稱為AVL樹。它具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

一、平衡二叉樹的基本性質

根據二叉樹的性質高度為h的AVL樹，節點數N最多為2h-1；其最少節點樹為(((1 + √5) / 2) h+2 - ((1 - √5) / 2)h+2)/ √5 - 1。

最少節點數n的形式化證明如下：

• 假設Nh-1表示高度為h-1的具有最少節點數的平衡二叉樹的節點總數，即少任意一個節點都無法組成一個平衡二叉樹
• 假設Nh-2表示高度為h-2的具有最少節點數的平衡二叉樹的節點總數，即少任意一個節點都無法組成一個平衡二叉樹
• 則根據平衡二叉樹的性質，為了構造高度為h的具有最少節點的平衡二叉樹
  • 它的兩棵子樹的高度差的絕對值為1，即兩棵子樹一棵高度為h-1，一棵高度為h-2
  • 兩棵子樹都具有最少的節點數
• 因而可得Nh = Nh-1 + Nh-2 + 1 

而且很顯然N0 =0，N1 =1，而斐波那契數列為Fn= Fn-1 + Fn-2，其序列形式為0,1,1,2,3,5...。用數學歸納法很容易證明Nh = Fh + 2- 1，再根據斐波那契數列的值可得高度為h的平衡二叉樹的最少節點數為Fh + 2 - 1 =(((1 + √5) / 2) h+2 - ((1 - √5) / 2) h+2)/ √5 - 1 。由于-1 < (1-√5)/2 < 0，是以:

((1 + √5)/2)h+2=√5 * (Nh  + 1 )  + ((1 - √5) / 2)h+2 < √5 * (Nh  + 1 ) + 1

h < log(√5 * (Nh  + 1 ) + 1) / log((1 + √5)/2) - 2 < 1.5 * log(√5 * (Nh  + 1 ) + 1) - 2 < 1.5 * log(√5 * (Nh  + 2 )) - 2 < 1.5 * 1.16 + 1.5 * log(Nh  + 2)  - 2 < 1.5 * log(Nh  + 2)

是以其高度為O(logn)，可以得到很好的添加、删除、查詢效率。在平衡二叉樹上的插入、删除、以及查詢操作不需要額外的空間。

平衡二叉樹一般是一個有序樹，它具有二叉樹的所有性質，其周遊操作和二叉樹的周遊操作相同。但是由于其對二叉樹施加了額外限制，因而其添加、删除操作都必須保證平衡二叉樹的性子被保持。

平衡二叉樹中引入了一個概念：平衡二叉樹節點的平衡因子，它指的是該節點的兩個子樹，即左子樹和右子樹的高度差，即用左子樹的高度減去右子樹的高度，如果該節點的某個子樹不存在，則該子樹的高度為0。

二、平衡二叉樹的查詢

在有序平衡二叉樹上的查詢操作非常簡單，基本算法為：

1. 和目前節點比較，如果相等則結束
2. 否則根據和目前節點比較的結果查詢目前節點的左子樹或者右子樹（如果下一步要查找的子樹不存在，則查詢結束，不存在要查找的節點）

是以平衡二叉樹的查詢操作的效率取決于平衡二叉樹的高度，即O(logn)。

三、平衡二叉樹的添加

平衡二叉樹的添加操作是比較複雜的，因為添加後，平衡二叉樹的平衡性質可能要被打破，此時就要對樹進行調整以保證平衡二叉樹的性質被保持住。平衡二叉樹的插入操作基本分為以下兩部步：

1. 插入：這個操作很容易立即，就是要插入節點，該操作就是找到插入點并把節點插入到樹中
2. 根據高度變化進行調整：很明顯插入一個節點（假設為new），至少會影響以插入節點的父節點（假設為p）為根節點的樹的高度，根據樹高度的定義，可以知道這又會進一步影響到以從”樹的根節點（假設為root）到p的路徑上的所有節點“為根節點的子樹的高度。另一方面，如果new被插入到節點a的子樹中，但是該節點的高度在new被插入後并沒有變化，則以從”root到a的路徑上的所有節點“為根的子樹的高度也不會變化。因而在new被插入後，隻需要沿着”樹的根節點（假設為root）到p的路徑“的反向路徑依次處理各個節點，找到第一個高度不滿足平衡二叉樹要求的節點，然後對其進行調整，使其高度不再發生變化。

插入操作通常很簡單，就是找到插入點，然後将新的節點插入到樹中。

在平衡二叉樹的插入中，最繁瑣的、最難的就是在找到某個節點，以該節點為根節點的子樹不滿足平衡二叉樹的要求，使得調整後的以該節點為根節點的子樹滿足平衡二叉樹的要求。樹的調整分以下幾種情況（假設以a為根節點的子樹在插入新節點後不滿足平衡二叉樹的要求了）：

2.1 LL型

LL型指的是由于在a的左子樹的根節點的左子樹上添加了節點而導緻a的平衡因子從1變成了2。這時需要對樹進行一次調整使得平衡二叉樹的要求得以滿足，這個操作通常稱為左旋。如圖所示

在調整後，還需要相應的更新調整操作涉及到的節點的平衡因子，同時還要分析下調整對以各個節點為根節點的子樹的高度的影響。以上圖為例，假設添加新節點前節點10,6,12,4,7的高度分别為h1,h2,h3,h4,h5，則在添加前：

1. 由于添加新節點前以節點10為根節點的子樹的高度為1，因而h2 = h3 + 1，h1=h2+1
2. 由于新節點被添加在節點6的左子樹，并且添加新節點後以節點6為根的子樹的高度增高，是以添加新節點前節點6的平衡因子為0，h4=h5，h2=h4+1

在添加完一個節點後，按照前邊的分析會沿着”樹的根節點（假設為root）到p的路徑“的反向路徑依次處理各個節點，直到找到了一個由于添加動作而導緻其左右子樹高度差不滿足平衡二叉樹的節點（在該例子中即為節點10），然後對以該節點為根的子樹進行調整。在找到該節點之前對其它節點的處理比較簡單，具體的過程是依據如下幾個參數：

• 插入到本節點的哪個子樹
• 被插入到的子樹的高度是否改變
• 該節點的原有平衡因子

來決定以該節點為根的子樹的高度是否改變，以及該節點的新的平衡因子。簡單的算法描述如下（以插入到左子樹為例，插入到右子樹的情形與它對稱）：

1. 如果插入到該節點的左子樹但左子樹高度不變，則該節點的平衡因子不變，以該節點為根節點的子樹的高度不變，否則
2. 如果插入到該節點的左子樹且左子樹高度增高，則：

• • 如果該節點原有平衡因子為1，則需要進行調整
  • 如果該節點原有平衡因子為0，則以該節點為根節點的子樹的高度增高，該節點的新的平衡因子為1
  • 如果該節點的原有平衡因子為-1，則以該節點為根節點的子樹的高度不變，該節點的新的平衡因子為0

在經過上述的處理并找到以其為根節點的不滿足平衡二叉樹要求的節點後（上圖中即為節點10），除了該節點外，其它節點的資訊都已經根據插入的節點做了相應的更新。現在需要對以該節點為根的子樹進行調整以使得新得到的樹是一棵平衡二叉樹。此時關鍵在于分析調整對節點平衡因子的影響，以及對以其為根節點的子樹的高度的影響。

以上圖為例，很顯然參與調整的節點包括節點6,7,12，因而隻需要分析這三個幾點即可。在調整後，節點6替換了節點10的位置（指的是稱為了節點10的父節點的子節點），隻要它的高度與原來處于該位置的節點10的高度相比不發生變化，則添加新節點對原樹高度的影響到此就結束了。

1.    先分析節點6的左子樹，即節點4。很明顯該調整不影響其左右子樹，因而其平衡因子以及以其為根的子樹的高度在調整前後不發生變化。但是需要注意的是以幾點4為根節點的子樹的高度在添加完新節點後變成了h4 + 1。

2.    再分析節點6的右子樹，即節點10的情形。由于該節點的左孩子發生了變化，因而需要進一步分析其左孩子的變化（即節點7的變化），以及其新的左右子樹的高度差。

• 很明顯該調整不影響節點7的左右子樹，因而其平衡因子以及以其為根的子樹的高度在調整前後不發生變化。以節點其為根節點的子樹在插入新節點前後高度也沒有發生變化，仍為h5。

由于節點10的右子樹在插入前後以及調整前後都沒有發生任何變化，因而節點12的平衡因子不變，以其為根節點的子樹的高度仍為h3。則調整後節點10的新的平衡因子為（h5 - h3） = h2 -1 - （h2 - 1）= 0。以節點10為根節點的子樹的高度為h3 + 1 = h2

3.    則調整後節點6的新的平衡因子為 h4 + 1 - h2 = 0，以節點6為根節點的子樹的高度為h2 + 1，與原來處于該位置的節點10的高度相同，因而在調整完畢後插入即可結束

從上述分析可以看出，對于該種類型的調整，在調整完後，僅需要修改節點6和節點10的平衡因子為0即可。

2.2  RR型

RR型指的是由于在a的右子樹的根節點的右子樹上添加了節點而導緻a的平衡因子從-1變成了-2。此時隻需要一次向左的旋轉操作即可。如圖所示

該類型實際上是和LL型對稱的，因而不再具體分析。

2.3 LR型

LR型指的是由于在a的左子樹的根節點的右子樹上添加了節點而導緻a的平衡因子從1變成了2。此時需要兩次旋轉操作，先左旋後右旋。

在該種類型中假設找到的以其為根節點的子樹不滿足平衡二叉樹要求的節點為x，x的左子樹的根節點為y，y的右子樹的根節點為z，則x，y，z以及z的左（右）孩子都需要參與調整，因而根據z在插入節點後的平衡因子的三種情形分别進行處理，這三種情形分别為（在找到x節點時）：

• z的平衡因子為0
• z的平衡因子為1
• z的平衡因子為-1

上圖中的情形對應于z的平衡因子為-1的情形。具體的分析過程可以參考LL型的分析過程。調整後的最終結果：

• 節點z處于節點x原來的位置（指的是稱為了節點x的父節點的子節點），以節點z為根節點的子樹的高度等于插入前以節點x為根節點的子樹的高度，節點z的平衡因子為0
• 節點x的新的平衡因子為0
• 節點y的新的平衡因子為1

下圖對應z的平衡因子為1的情形：

調整後的最終結果：

• 節點z處于節點x原來的位置（指的是稱為了節點x的父節點的子節點），以節點z為根節點的子樹的高度等于插入前以節點x為根節點的子樹的高度，節點z的平衡因子為0
• 節點x的新的平衡因子為-1
• 節點y的新的平衡因子為0

下圖對應z的平衡因子為0的情形：

調整後的最終結果：

• 節點z處于節點x原來的位置（指的是稱為了節點x的父節點的子節點），以節點z為根節點的子樹的高度等于插入前以節點x為根節點的子樹的高度，節點z的平衡因子為0
• 節點x的新的平衡因子為0
• 節點y的新的平衡因子為0

2.4 RL型

RL型指的是由于在a的右子樹的根節點的左子樹上添加了節點而導緻a的平衡因子從-1變成了-2。此時需要兩次旋轉操作，先右旋後左旋。

RL型與LR型是對稱的，也分三種情形。

是以平衡二叉樹的插入分為兩步，第一步找到插入點，時間複雜度為O(logn)，第二步找到需要調整的子樹進行最多兩次調整，時間複雜度也為O(logn)，因而它的插入操作的時間複雜度為O(logn)。

http://blog.csdn.net/goodluckwhh/article/details/11693451