程式碼實現平衡二叉樹
實現二叉樹對於我們已經算是輕車熟路了。先來定義樹的結點：
class
AVLNode
{
public
int
data
；
public
int
depth
；
public
int
balance
；
public
AVLNode
parent
；
public
AVLNode
left
；
public
AVLNode
right
；
public
AVLNode
（
int
data
）
{
this
。
data
=
data
；
depth
=
1
；
balance
=
0
；
left
=
null
；
right
=
null
；
}
}
按照上一篇文章的分析，我們需要在結點裡定義代表當前子樹深度的 depth，以及表示左右子樹高度之差的 balance。其他的則與普通的二叉樹看上去並沒有什麼區別。
插入的過程，前半部分也和普通的二叉樹沒有什麼區別：
private
void
insert
（
AVLNode
root
，
int
data
）
{
if
（
data
<
root
。
data
）
{
if
（
root
。
left
！=
null
）
insert
（
root
。
left
，
data
）；
else
{
root
。
left
=
new
AVLNode
（
data
）；
root
。
left
。
parent
=
root
；
}
}
else
{
if
（
root
。
right
！=
null
）
insert
（
root
。
right
，
data
）；
else
{
root
。
right
=
new
AVLNode
（
data
）；
root
。
right
。
parent
=
root
；
}
}
/* 這裡要做一些特殊的處理了 */
}
在函式的結尾，我們的註釋裡寫到：要做一些特殊的處理。這些特殊的處理就包括了計算結點的深度以及該結點左右子樹的深度之差，也就是平衡度。
我們來具體看一下，這些處理是什麼：
/* 從插入的過程回溯回來的時候，計算平衡因子 */
root。balance = calcBalance（root）；
/* 左子樹高，應該右旋 */
if （root。balance >= 2） {
/* 右孫高，先左旋 */
if （root。left。balance == -1）
left_rotate（root。left）；
right_rotate（root）；
}
if （root。balance <= -2）
{
if （root。right。balance == 1）
right_rotate（root。right）；
left_rotate（root）；
}
root。balance = calcBalance（root）；
root。depth = calcDepth（root）；
將這一部分程式碼合併到 insert 方法中去，就可以得到完整的實現了。至於這裡面定義的右旋，其過程，我們上一節也已經講解過了。這裡只要實現就可以了。
private
void
right_rotate
（
AVLNode
p
）
{
/* 一次旋轉涉及到的結點包括祖父，父親，右兒子 */
AVLNode
pParent
=
p
。
parent
，
pRightSon
=
p
。
left
；
AVLNode
pLeftGrandSon
=
pRightSon
。
right
；
/* 左子僭為父 */
pRightSon
。
parent
=
pParent
；
if
（
pParent
！=
null
）
{
if
（
p
==
pParent
。
left
）
pParent
。
left
=
pRightSon
；
else
if
（
p
==
pParent
。
right
）
pParent
。
right
=
pRightSon
；
}
pRightSon
。
right
=
p
；
p
。
parent
=
pRightSon
；
/* 右孫變左孫 */
p
。
left
=
pLeftGrandSon
；
if
（
pLeftGrandSon
！=
null
）
pLeftGrandSon
。
parent
=
p
；
/* 重新計算平衡因子 */
p
。
depth
=
calcDepth
（
p
）；
p
。
balance
=
calcBalance
（
p
）；
pRightSon
。
depth
=
calcDepth
（
pRightSon
）；
pRightSon
。
balance
=
calcBalance
（
pRightSon
）；
}
左旋程式碼就不再給出了，請讀者自行補充。
另外，還有計算平衡度的程式碼：
private
int
calcBalance
（
AVLNode
p
）
{
int
left_depth
；
int
right_depth
；
if
（
p
。
left
！=
null
）
left_depth
=
p
。
left
。
depth
；
else
left_depth
=
0
；
if
（
p
。
right
！=
null
）
right_depth
=
p
。
right
。
depth
；
else
right_depth
=
0
；
return
left_depth
-
right_depth
；
}
private
int
calcDepth
（
AVLNode
p
）
{
int
depth
=
0
；
if
（
p
。
left
！=
null
）
depth
=
p
。
left
。
depth
；
if
（
p
。
right
！=
null
&&
depth
<
p
。
right
。
depth
）
depth
=
p
。
right
。
depth
；
depth
++；
return
depth
；
}
這樣，一個完整的平衡二叉樹才算完成了。
今天的作業：
1。 補充左旋程式碼。
2。 平衡二叉樹的刪除操作與插入操作很相似。在真正地刪除一個結點以後，沿著查詢路徑向上回溯，並且檢查路徑上的每一個結點，看它是否平衡，如果不平衡，仍然按照上述規則進行調整。請自己實現平衡二叉樹的刪除。
課外閱讀：
有一道這樣的題目，問高度為h的平衡二叉樹最少有多少個結點。 解答這個題目，可以從樹的構造出發，如果我們能構造出具有最少結點的高度為h的平衡二叉樹，就相當於解決了這道題目。先從最結點數目比較少的情況出發。容易想象，當高度為1時，最少的結點個數是1，我們記這種樹為T1，當高度為2時，最少的結點個數為2，記 這種樹為T2，並且，我們知道，T2有兩種形態，分別是隻有一個左孩子結點和只有一個右孩 子結點。要構造有3層的最少結點的平衡二叉樹T3，只需要新增一個根結點 root ，令root的 左子樹為T1，右子樹為T2。構造4層的平衡二叉樹時，同樣地，新增一個根結點，然後令左 子樹為T2，右子樹為T3，依次類推。再記Tn的結點個數為Fn，就可以得到公式：
然後再得到通項公式：
對上式求逆函式，可以得到有n個結點的平衡二叉樹最多有多少層。
平衡二叉樹的插入，刪除操作都僅和樹的高度h有關，它們的時間複雜度是O（h）的。（如何得到這個通項公式，先不用管，這個是組合數學裡的內容。很多計算機專業的本科階段的課程都還沒有涉及。我們這裡先記住結論，以後如果有機會的話，我可能會介紹一部分組合數學的知識）